21

Is there some way to draw a B+ tree in latex? It would look something like the picture below (ignoring the animations)

Animation linked here: https://i.stack.imgur.com/JRcmY.gif

Screenshot of the start of the animation:

Screenshot of a B+ tree

2
  • As you'll soon see in the answers below - the package tikz is great resource for drawing graphs when you know the absolute positions of the nodes.
    – Hooked
    May 4, 2011 at 4:22
  • Welcome to TeX.sx, DamonKashu! I've added a screenshot of the animation you linked to. I hope this image captures what you are trying to achieve.
    – Jake
    May 4, 2011 at 4:24

3 Answers 3

22

I would do this in TikZ. Section 18.1 of the version 2.10 manual shows how to make trees. The nodes on the trees are a little nonstandard, but perhaps section 16.3 on multi-part nodes would be helpful.

Here's a quick mockup:

\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{shapes}
\begin{document}
\begin{center}
\begin{tikzpicture}
\tikzstyle{bplus}=[rectangle split, rectangle split horizontal,rectangle split ignore empty parts,draw]
\tikzstyle{every node}=[bplus]
\tikzstyle{level 1}=[sibling distance=60mm]
\tikzstyle{level 2}=[sibling distance=15mm]
\node {15} [->]
  child {node {3 \nodepart{two} 7}
    child {node {1 \nodepart{two} 2}}
    child {node {4 \nodepart{two} 6}}
    child {node {8 \nodepart{two} 9}}    
  } 
  child {node {21 \nodepart{two} 28 \nodepart{three} 32 \nodepart{four} 50}
    child {node {17 \nodepart{two} 20}}
    child {node {22 \nodepart{two} 25}}
    child {node {28 \nodepart{two} 30}}    
    child[sibling distance=25mm] {node {34 \nodepart{two} 38 \nodepart{three} 44 \nodepart{four} 47}}    
    child[sibling distance=25mm] {node {53 \nodepart{two} 54 \nodepart{three} 60 \nodepart{four} 88}}    
  }
;\end{tikzpicture}
\end{center}

\end{document}

sample code output

It's going to be more work to get the vertical lines doubled like in your example. The code for the rectangle split shape may need to be altered.

5
  • 2
    In the US B+ is a grade students might receive if they do "good" work in a course. So "B+ tree" sounds to me a little strange. Couldn't I have an "A- tree" instead? :-) May 4, 2011 at 16:47
  • This is the most comprehensive result when searching for "draw b+ tree in latex" so I figured I'd add a tip for styling each node to look more like a B+ tree. Suppose your B+ tree has 2 keys per node. To create the little empty rectangles surrounding each node, you can add the options rectangle split parts = 5, rectangle split empty part width=0.01mm, rectangle split every empty part={} to tikzstyle. Then you can create a function \newcommand \bpformat [2] {node{ \nodepart{two} #1 \nodepart{four} #2 }} & fill nodes with \child {\bpformat{3}{7}} and so on. ex: i.imgur.com/noeD0.png
    – maksim
    May 10, 2012 at 1:50
  • @maksim: Thanks for the contribution. I feel like the "TikZ way" would be to create a new node shape like rectangle that drew the extra vertical lines. May 10, 2012 at 13:08
  • I see what you're saying. If we made a new shape, how could we control the way individual cells overlapped, so that the extra vertical lines would be in the correct spots?
    – maksim
    May 13, 2012 at 23:23
  • The trouble is that even rectangle shapes are very complicated to define. The rectangle split shape is in pgflibraryshapes.multipart.code.tex. Perhaps a decoration can be applied to the background path to double vertical segments but not horizontal? May 8, 2013 at 16:29
11

I found an .sty file by Prof. Wei Wang from University of New South Wales which seems pretty nice:

http://www.cse.unsw.edu.au/~weiw/tools.html

Example

\NeedsTeXFormat{LaTeX2e}
\ProvidesPackage{weiwBTree}
\typeout{Document Style `weiw_BTree - Support drawing B+-Tree (ver 0.999)}

\RequirePackage{tikz}
\RequirePackage{ifthen}

% use libraries
\usetikzlibrary{arrows,shapes,snakes,matrix}


%% global declaration
\tikzstyle{btreeptr} = [draw, semithick, fill=blue!50, minimum height=2em]
\tikzstyle{btreeval} = [draw, semithick, fill=yellow!30, minimum size=2em]
\tikzstyle{btreevale} = [draw,semithick, fill=green!30, minimum size=2em]
\tikzstyle{btlink} = [draw, semithick, ->, >=triangle 45]

%% macro
%% helper macros
\newcommand{\suppressemptystr}[1]{% leave blank for entries in leaf nodes
  \ifthenelse{\equal{#1}{}}%
  {%
    \relax%
  }%
  % Else
  {%
    #1\textsuperscript{*}%
  }%
}%

\newcommand{\xyshift}[3]{% help to place the nodes
  \begin{scope}[xshift=#1, yshift=#2]
    #3
  \end{scope}%
}

%% Common btree macros
\newcommand{\btreelink}[2]{% #1: src node; #2: dest node; 
  \draw[btlink] ([yshift=3pt] #1.south) -- (#2-b.north);
}

\newcommand{\btreelinknorth}[2]{% #1: src node; #2: dest node; 
  \draw[btlink] ([yshift=3pt] #1.south) -- (#2.north);
}

\newcommand{\btreetriangle}[2]{% #1: node name; #2 text inside
  \node[anchor=north, regular polygon, regular polygon sides=3, draw] (#1) {#2};
}

%%======================================================================
%% btree with capacity = 4
\newcommand{\btreeinodefour}[5]{%
  \matrix [ampersand replacement=\&] (#1)
  {
    \node[btreeptr] (#1-1) {\vphantom{1}}; \& \node[btreeval] (#1-a) {#2}; \&
    \node[btreeptr] (#1-2) {\vphantom{1}}; \& \node[btreeval] (#1-b) {#3}; \&
    \node[btreeptr] (#1-3) {\vphantom{1}}; \& \node[btreeval] (#1-c) {#4}; \&
    \node[btreeptr] (#1-4) {\vphantom{1}}; \& \node[btreeval] (#1-d) {#5}; \&
    \node[btreeptr] (#1-5) {\vphantom{1}}; \\
  };
}
\newcommand{\btreelnodefour}[5]{%
  \matrix [ampersand replacement=\&, outer sep=0pt, matrix anchor=north] (#1)
  {
    \node[btreevale] (#1-a) {\suppressemptystr{#2}}; \&
    \node[btreevale] (#1-b) {\suppressemptystr{#3}}; \&
    \node[btreevale] (#1-c) {\suppressemptystr{#4}}; \&
    \node[btreevale] (#1-d) {\suppressemptystr{#5}}; \\
  };
}

%%======================================================================
%% btree with capacity = 3
\newcommand{\btreeinodethree}[4]{%
  \matrix [ampersand replacement=\&] (#1)
  {
    \node[btreeptr] (#1-1) {\vphantom{1}}; \& \node[btreeval] (#1-a) {#2}; \&
    \node[btreeptr] (#1-2) {\vphantom{1}}; \& \node[btreeval] (#1-b) {#3}; \&
    \node[btreeptr] (#1-3) {\vphantom{1}}; \& \node[btreeval] (#1-c) {#4}; \&
    \node[btreeptr] (#1-4) {\vphantom{1}}; \\
  };
}
\newcommand{\btreelnodethree}[4]{%
  \matrix [ampersand replacement=\&, outer sep=0pt, matrix anchor=north] (#1)
  {
    \node[btreevale] (#1-a) {\suppressemptystr{#2}}; \&
    \node[btreevale] (#1-b) {\suppressemptystr{#3}}; \&
    \node[btreevale] (#1-c) {\suppressemptystr{#4}}; \\
  };
}
%%======================================================================






%% simple example
%  \begin{center}
%    \scalebox{0.7}{
%      \begin{tikzpicture}
%        % 
%        \btreeinodefour{root}{13}{17}{24}{30};
%        \xyshift{-40mm}{-20mm}{\btreelnodefour{n1}{2}{3}{5}{7}}
%        \xyshift{-0mm}{-20mm}{\btreelnodefour{n2}{14}{16}{}{}}
%        \xyshift{40mm}{-20mm}{\btreelnodefour{n3}{19}{20}{22}{}}
%        \xyshift{80mm}{-20mm}{\btreelnodefour{n4}{24}{27}{29}{}}
%        \xyshift{120mm}{-20mm}{\btreelnodefour{n5}{33}{34}{38}{39}}
%        %
%        \foreach \x in {1,2,...,5} { \btreelink{root-\x}{n\x} }
%      \end{tikzpicture}
%    }
%  \end{center}
4
  • This should be the top answer. This package is very neat. (+1)
    – Columbo
    Feb 22, 2016 at 17:06
  • Does anyone know how to add the arrows between neighbours?
    – Parth
    Oct 8, 2016 at 20:57
  • The link here is broken and I can't find a current webpage for Dr. Wei Wang. Does anyone know where one can find this now?
    – Kyle
    Apr 16, 2023 at 15:09
  • As my student pointed out, use the Wayback Machine: web.archive.org/web/20120430233547/http://www.cse.unsw.edu.au/…
    – Kyle
    Apr 18, 2023 at 1:08
2

http://tug.org/PSTricks/main.cgi?file=pst-tree/pst-tree#binary can be modified to your needs

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .