Take the 2-minute tour ×
TeX - LaTeX Stack Exchange is a question and answer site for users of TeX, LaTeX, ConTeXt, and related typesetting systems. It's 100% free, no registration required.

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: http://i.stack.imgur.com/JRcmY.gif

Screenshot of the start of the animation:

Screenshot of a B+ tree

share|improve this question
    
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
add comment

2 Answers 2

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.