# How do I draw a B+ tree in latex?

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

Screenshot of the start of the animation:

-
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 '11 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 '11 at 4:24

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}


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.

-
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? :-) –  Matthew Leingang May 4 '11 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 '12 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. –  Matthew Leingang May 10 '12 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 '12 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? –  Matthew Leingang May 8 '13 at 16:29