5
\$\begingroup\$

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
      \global\advance\pointerCounter by 1%
    }%
  }%

  % 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
    \global\advance\pointerCounter by 1%
  }%

  % 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%
    \advance\nodeNumber by #5%

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

    % 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
    \global\advance\tempCounter by 1%
  }%
}%

%%
%   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%
    \advance\nextNodeNumber by 1%

    % 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
    \global\advance\nodeNumber by 1%
  }%
}%

\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): Simple example

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

\$\endgroup\$
  • 4
    \$\begingroup\$ 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? \$\endgroup\$ – coderodde Apr 13 '16 at 9:10
  • 1
    \$\begingroup\$ @coderodde I've added pictures now \$\endgroup\$ – SX. Apr 13 '16 at 12:40
  • \$\begingroup\$ 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. \$\endgroup\$ – TeXnician Jan 18 '18 at 14:04
  • \$\begingroup\$ The example doesn't even compile. \$\endgroup\$ – Ryan Rosario May 5 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.