# B+ Tree Visualization in LaTeX/TikZ

I have written a LaTeX package to visualize B+ trees.

The main purpose is to provide a simple but powerful package which provides a convenient interface.

However, this is my first LaTeX package and I would also like to know where I can do better.

So I'd like to get reviews from these two points of view:

• Simplicity of the implementation and convenience of the interface
• Improvements/Criticism from a LaTeX point of view

Here's my package code and an example of how to use it.

btreevis.sty

\NeedsTeXFormat{LaTeX2e}
\ProvidesPackage{btreevis}[2015/06/24 B+ Tree Visualization Package]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PACKAGES
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\RequirePackage{tikz}
\RequirePackage{ifthen}
\RequirePackage{etoolbox}
%\RequirePackage{calc}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% LIBRARIES
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% TikZ
\usetikzlibrary{arrows, matrix, calc}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% COUNTERS (GLOBAL)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% The number of pointers per node (often referred to as m in B+ tree context)
\newcount\noOfPointersPerNode%

% Used to number pointers and keys consecutively inside a B+ tree node
\newcount\pointerCounter%

% Used in the connect macros to know where the arrows have to start
\newcount\pointerNumber%

% Used in the connect macros to hold the number of the current (source) node to
% connect to
\newcount\nodeNumber%

% Used in the connect macros to hold the number of the next (destination) node
% to connect to
\newcount\nextNodeNumber%

% Used temporarily in the connect macros
\newcount\tempCounter%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% DEFAULT STYLES (GLOBAL)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Default style of a B+ tree node. Provides all important properties a B+ tree
% node should have such that the resulting B^+ tree looks beautiful.
% May be overridden by an own style.
\tikzstyle{BTreeNodeDefault} = [
draw,
matrix,
matrix of nodes,
% must be used; otherwise the matrix content generation does not work
ampersand replacement=\&,
% if inner sep != 0, there is a border around the matrix of nodes
inner sep = 0,
nodes = {
draw,
rectangle,
% better readability; otherwise node border and content do overlay
inner sep = 1mm,
% workaround to make nodes look better;
% better in the sense that all nodes in the matrix of nodes have the same
% height and depth independent of their content
text height = \heightof{ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmopqrstuvwxyz0123456789},
text depth = \depthof{ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmopqrstuvwxyz0123456789},
% scaling factor of nodes; nodes have to be scaled independently from the
% whole tikzpicture (at least in some cases)
scale = 1
}
]

% Default style of a B+ tree.
% May be overriden by own styles but has all important properties.
\tikzstyle{BTreeDefault} = [
% scaling factor of the whole picture
scale = 1,
% must be used; otherwise the tree environment draws its own connecting arrows
edge from parent/.style = {}
]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% MACROS (PACKAGE INTERNAL)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%
% Helper macro (only for package internal usage).
% Creates the content for two nodes (to be used in a matrix of nodes).
% One with a given content (a key node) and one corresponding pointer node
% (left of the key node). The naming of both key and pointer nodes is done
% automatically. This macro is used to generate the content of the matrix of
% nodes for a B+ tree node in the macro \CreateBTreeNode[4].
%
% Be careful when modifying this macros: Because the content just generates a
% part of a matrix no blank lines should be inserted in this macros (this may
% causes strange errors when compiling).
%
% Naming schema: l#3-n#4-k#2 for search keys and l#3-n#4-p#2 for pointers.
%
% Arguments:
%   #1 ...  The value to be inserted into the node. If empty an empty node is
%           generated.
%   #2 ...  The pointer/key number, e.g. if #2 is 2, the pointer nodes third
%           part of the name is '-p2' and the value nodes third part of the name
%           is '-k2'
%   #3 ...  The level number, e.g. if #3 is 3, the nodes first part of the name
%           is 'l3'
%   #4 ...  The node number, e.g. if #4 is 4, the nodes second part of the name
%           is '-n4'
%
% Example of the usage:
%   \@create@key@matrix@node{3}{1}{2}{1}
%
%   (Never needed because it is more of an internal macro to draw the B+ tree).
%   Generates two nodes: the left (pointer) node named 'l2-n1-p1' containing no
%   value and a node right of it named 'l2-n1-k1' containing the value '3'. So
%   if the initial matrix was an empty matrix of nodes [], the subsequent matrix
%   contains two nodes [| 3].
%%
\newcommand{\@create@key@matrix@node}[4] {%
% empty pointer node (left)
|(l#3-n#4-p#2) [fill=gray!50]| {\vphantom{1}} \&%
% check presence of argument #1
\ifx&#1&%
% empty key node (right)
|(l#3-n#4-k#2)| {\hphantom{1}} \&%
\else%
% key node with value (right)
|(l#3-n#4-k#2)| {#1} \&%
\fi%
}%

%%
% Helper macro (only for package internal usage).
% Creates the content for an empty node (to be used in a matrix of nodes).
% The naming of this node is done automatically. This macro is used to generate
% the content of the matrix of nodes for a B+ tree node in the macro
% \CreateBTreeNode[4].
%
% Naming schema: l#2-n#3-p#1
%
% Arguments:
%   #1 ...  The pointer number, e.g. if #1 is 2, the pointer nodes third part of
%           the name is '-p2'
%   #2 ...  The level number, e.g. if #2 is 3, the nodes first part of the name
%           is 'l3'
%   #3 ...  The node number, e.g. if #3 is 4, the nodes second part of the name
%           is '-n4'
%
% Example of the usage:
%   \@create@key@matrix@node{5}{2}{1}
%
%   (Never needed because it is more of an internal macro to draw the B+ tree).
%   Generates a single empty node named 'l2-n1-p5' (which is in most cases is
%   the rightmost part of a B+ tree node). So if the initial matrix is
%   [| 3 | 5], the subsequent matrix is [| 3 | 5 |].
%%
\newcommand{\@create@pointer@matrix@node}[3] {%
% empty pointer node
|(l#2-n#3-p#1) [fill=gray!50]| {\vphantom{1}} \&%
}%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% MACROS (GLOBAL)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%
% Just a setter to set the \noOfPointersPerNode variable.
%
% Arguments:
%   #1 ...  The value to be assigned to \noOfPointersPerNode
%
% Example of the usage:
%   \setNoOfPoinersPerNode{4}
%
%   Sets \noOfPointersPerNode to 4.
%%
\newcommand{\SetNoOfPoinersPerNode}[1]{%
\noOfPointersPerNode = #1%
}%

%%
% Generates the content of a complete B+ tree node (matrix of nodes) for given
% values supplied as comma-separated list. This generated content is stored into
% a variable supplied as argument. If the comma-separated list contains less
% than (\noOfPointersPerNode - 1) elements, the remaining nodes are left empty
% but are generated to be visualized. Hence, if \noOfPointersPerNode is set to 4
% and only a list of 2 elements is supplied as key list, the node contains of
% the two keys and two empty nodes ([| key1 | key2 |  |  |]).
% The other way round, if the comma-separated list contains more than
% \noOfPointersPerNode elements, the oversupplied elements are simply ignored
% and thus are not contained in the matrix of nodes.
% The generated matrix of nodes is not named because this is not needed to
% connect the nodes. However, the nodes inside this matrix of nodes are named
% (see macros \@create@key@matrix@node and \@create@key@matrix@node).
%
% Todo: Encapsulate the part inside the \whiledo and \ifthenelse, respectively,
%       into an own macros (if possible; may not be possible because of the
%       expanding of the arguments/counters). By now this is more or less
%       duplicated code.
%
% Arguments:
%   #1 ...  The level of the node (used for naming in called macros)
%   #2 ...  Number of the node of level #1
%   #3 ...  Values as comma-separated list
%   #4 ...  Name of the variable the B+ tree node content is stored to
%
% Example of the usage:
%   \SetNoOfPoinersPerNode{4}
%   \CreateBTreeNode{0}{1}{{5}}{\levelZeroNodeOne}
%   \node[BTreeNodeDefault] {\levelZeroNodeOne};
%
%   The first line set the number of pointers per node to a maximum of 4. The
%   second line generates the content of the matrix of nodes, stored in
%   \levelZeroNodeOne. \levelZeroNodeOne afterwards contains of a matrix of
%   nodes [| 5 | | |]. So \levelZeroNodeOne can be used as content for the
%   subsequent call of node, which then has to be a matrix of nodes
%   (\levelZeroNodeOne is a matrix content separated by & and \\).
%%
\newcommand{\CreateBTreeNode}[4] {%
% initialize pointer counter (is then incremented for each pointer generated)
\pointerCounter = 1%

% initialize variable the node content is stored into (set it empty)
\let#4\empty%

% for each value of the comma-separated list
\foreach \x in #3 {%
% only insert until the maximum number of pointers per node is reached
\ifthenelse{\not{\the\pointerCounter < \noOfPointersPerNode}}{\breakforeach}{%
% expand first two arguments upfront (necessary)
\edef\tmpexpand{{\x}{\the\pointerCounter}}%
% the \@create@key@matrix@node macros generates a part of the whole node
% matrix and this content is then appended here
% also the arguments are expanded accordingly
\expandafter\gappto\expandafter#4\expandafter{%
\expandafter\@create@key@matrix@node\tmpexpand{#1}{#2}%
}%
% increment pointer counter
}%
}%

% here the remaining empty key nodes of the matrix are produced (if there are
% less keys than (number of pointers per node - 1) supplied)
\whiledo{\the\pointerCounter < \noOfPointersPerNode}{%
% expand first two arguments upfront (necessary)
\edef\tmpexpand{{}{\the\pointerCounter}}%
% the \@create@key@matrix@node macros generates a part of the whole node
% matrix and this content is then appended here (in essence, here the empty
% nodes are generated and appended).
% also the arguments are expanded accordingly
\expandafter\gappto\expandafter#4\expandafter{%
\expandafter\@create@key@matrix@node\tmpexpand{#1}{#2}%
}%
% increment pointer counter
}%

% here the last pointer node is appended to the matrix
\expandafter\gappto\expandafter#4\expandafter{%
\expandafter\@create@pointer@matrix@node%
\expandafter{\the\pointerCounter}{#1}{#2}%
}%

% append the line of the matrix of nodes is finished (with \\)
\gappto#4{\\}%
}%

%%
% Connects all pointers of a given node on a given (source) level to all its
% children of a given (destination level) with an arrow (solid). This only works
% if the nodes of the B+ tree are named like mentioned in the
% \@create@key@matrix@node and \@create@pointer@matrix@node, respectively.
%
% Arguments:
%   #1 ...  Number of source (tree) level
%   #2 ...  Number of source node (parent node)
%   #3 ...  Number of destination (tree) level
%   #4 ...  Number of (child) nodes to be connected with parent
%   #5 ...  Number of the first (child) node to be connected with parent
%
% Example of the usage:
%   \ConnectBTreeNodes{0}{1}{1}{2}{1}
%
%       Generates arrows from node 1 of the top level (0) to 2 child nodes of the
%   subsequent level (1) of the tree. We have 2 children on the subsequent level
%   and the first node to be connect (on the subsequent level) is node 1. A node
%   contains 3 search keys, hence it has 4 pointers. The incoming arrows on any
%   node on the subsequent level arrives at the north center of the node.
%%
\newcommand{\ConnectBTreeNodes}[5] {%
% initialize temporary counter (just used to iterate)
\tempCounter = 0%

% draw a vertical arrow (connect) from the source node to each child node
\whiledo{\the\tempCounter < #4} {%
% compute current node number:
% temporary counter + the number of the node to start with
\nodeNumber = \the\tempCounter%

% compute current pointer number: temporary counter + 1
\pointerNumber = \the\tempCounter%

% draw an arrow from south of the computed pointer number to middle of the
% north of the node with the previously computed number
\draw[->, >=stealth] (l#1-n#2-p\the\pointerNumber.south) --
($(l#3-n\the\nodeNumber-p1.north)!0.5!(l#3-n\the\nodeNumber-p\the\noOfPointersPerNode.north)$);%

% increment temporary counter
}%
}%

%%
%   Connects all leaf nodes of a given (leaf) level with a dotted arrow. The arrow
% starts at .east of the rightmost node inside the leaf and ends at .west
% of the leftmost node inside the next leaf. This only works if the nodes of the
% B+ tree are named like mentioned in in the \@create@key@matrix@node and
% \@create@pointer@matrix@node, respectively.
%
% Arguments:
%   #1 ... Number of the (tree) level of the leaves
%   #2 ... Number of leaf nodes to be connected
%
% Example of the usage:
%   \ConnectBTreeLeaves{2}{5}
%
%   Generates arrows between 5 nodes of the leaf level (here 2).
%%
\newcommand{\ConnectBTreeLeaves}[2] {%
% initialize node number (used to iterate)
\nodeNumber = 1%

% draw horizontal, dotted arrows (connect) between all leaf nodes
% arrows are drawn from left to right
\whiledo{\the\nodeNumber < #2} {%
% compute next node number: current node number + 1
\nextNodeNumber = \nodeNumber%

% draw a dotted arrow between two leaf nodes (from left to right)
\draw[->, >=stealth, dotted]
(l#1-n\the\nodeNumber-p\the\noOfPointersPerNode.east) --
(l#1-n\the\nextNodeNumber-p1.west);%

% increment node number
}%
}%

\endinput


example-simple.tex

\documentclass{article}

% Use btreevis package
\usepackage{btreevis}

\begin{document}
\begin{center}
\begin{tikzpicture}[
% Use default B+ tree style
BTreeDefault,
% Sibling and level distance for 1 level.
% These have to be adapted for almost every B+ tree if
%   - the number of pointers per node and/or
%   - the matrix content and/or
%   - the number of levels and/or
%   - the number of children
% changes.
level 1/.style = {
sibling distance = 8em,
level distance = 6em
}
]

% Set number of pointers per node (this should be done always upfront)
\SetNoOfPoinersPerNode{4}

% Generate content of (tree) level 0 (root level)
\CreateBTreeNode{0}{1}{{3, 9}}{\levelZeroNodeOne}

% Generate content of (tree) level 1
\CreateBTreeNode{1}{1}{{1, 2}}{\levelOneNodeOne}
\CreateBTreeNode{1}{2}{{3, 4, 6}}{\levelOneNodeTwo}
\CreateBTreeNode{1}{3}{{9, 10}}{\levelOneNodeThree}

% Generate B+ tree nodes using the previously generated node contents
\node[BTreeNodeDefault] {\levelZeroNodeOne}
child { node[BTreeNodeDefault] {\levelOneNodeOne} }
child { node[BTreeNodeDefault] {\levelOneNodeTwo} }
child { node[BTreeNodeDefault] {\levelOneNodeThree} };

% Connect B+ tree nodes (vertical, solid arrows)
\ConnectBTreeNodes{0}{1}{1}{3}{1}

% Connect B+ tree leaf nodes (horizontal, dotted arrows)
\ConnectBTreeLeaves{1}{3}
\end{tikzpicture}
\end{center}
\end{document}


If necessary, I could also provide an advanced example, but the code is quite long (although most of the lines are explanatory comments).

Simple example (code above):

Advanced example (as mentioned, I could provide the code for this too):

• We are lazy people, and some of us does not have a TeX distribution in the first place. Could you consider adding an image of your visualisation? – coderodde Apr 13 '16 at 9:10
• @coderodde I've added pictures now – SX. Apr 13 '16 at 12:40
• If you still want feedback, just two hints (haven't extensively tried it yet): You might prefer \tikzset over \tikzstyle to create styles and concerning the user interface needing a special group around the comma-separated list seems tedious. – TeXnician Jan 18 '18 at 14:04
• The example doesn't even compile. – Ryan Rosario May 5 at 20:27