Select Git revision
btreevis.sty
-
Patrick Gustav Blaneck authoredPatrick Gustav Blaneck authored
Code owners
Assign users and groups as approvers for specific file changes. Learn more.
btreevis.sty 17.27 KiB
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Author: Daniel Kocher
% Email: Daniel.Kocher@stud.sbg.ac.at
% Github: www.github.com/danielkocher
% Institute: University of Salzburg
% Department of Computer Sciences
% Database Research Group (dbresearch.uni-salzburg.at)
%
% Project: www.github.com/danielkocher/btreevis
% License: MIT license
% Description: Drawing B+ trees is a usual task when teaching and/or working on
% database index structures (and other algorithms and data
% structure stuff). The default TikZ features do not provide a
% good and uncomplicated way to draw such a B+ tree. Furthermore
% they do not look 'good'. 'Good' in the sense that they do not
% look like real B+ tree. This package tackles this problem.
%
% It provides macros to simplify and beautify the drawing of a B+
% tree in LaTeX using TikZ. To keep drawing the trees simple, the
% standard tree environment of TikZ is used. So, all the nodes
% are placed by this environment in a tree-like way. The content
% of the nodes is a matrix of nodes, generated by a macro, which
% generates key and pointer nodes alternating (starting with a
% pointer node) - see \CreateBTreeNode[4] for further details.
% The TikZ tree environment connects the nodes of tree by default.
% This feature is disabled by a default style (BTreeDefault)
% because these connections do not correspond to the connections
% we want for a realistic B+ tree visualization. To accomplish
% such a realistic B+ tree visualization, this package provides
% two macros: one to draw connections between inner nodes
% (vertically) and one to draw connections between leaf nodes
% (horizontally). See \ConnectBTreeNodes[5] and
% \ConnectBTreeLeaves[2] for further information. To simplify the
% macros, a global number of pointers per node is used. This is
% necessary because the \Connect* macros need to know how many
% keys can be stored in a B+ tree node at most in order to allow
% proper arrow drawing (the source of every arrow has to be an
% an arrow field of the B+ tree node and the destination of every
% arrow has to be in the middle of the .north of a B+ tree node.
% The package also provides two default tikzstyles, one for the
% B+ tree node and one for the whole tikzpicture of the B+ tree.
% Those styles also contain useful information when creating own
% tikzstyles (see tikzstyles BTreeDefault and BTreeNodeDefault for
% further information).
%
% There are two macros for internal usage which may be used
% outside this package but at your own risk.
%
% Please contact me using the email at the top of this header for
% bugs, criticism and comments.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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 = height("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmopqrstuvwxyz0123456789"),
text depth = depth("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=blue!20]| {\vphantom{1}} \&%
% check presence of argument #1
\ifx&%
% 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=blue!20]| {\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