# How to draw a B-Tree using Dot

B-Trees are a really cool data structure. Basically, B-Trees are a special form of search trees, where a node contains multiple keys. A B-Tree has the following properties (where *g* is a parameter that has to be chosen):

- Each node contains at least
*g*keys. Only the root of the tree is allowed to have less than*g*keys. - Each node contains at most
*2*g*keys. - All leaves are at the same "level", i.e. a B-Tree is always balanced (resulting in logarithmic complexity for the access).
- An inner node with
*k*keys has exactly*k+1*children. - Let
*s*,_{1}*s*...,_{2}*s*denote the keys of a node. The following properties hold:_{k} *s*<_{1}*s*< ... <_{2}*s*._{k}- The subtree rooted at the left-most child of the node contains only keys <
*s*._{1} - The subtree rooted at the right-most child of the node contains only keys >
*s*._{k} - The subtree rooted at the
*i*th child of the node contains only keys between*s*and_{i-1}*s*._{i}

Recently, I needed to draw B-Trees for a presentation. I have often used the Dot tool from the GraphViz package to draw graphs and trees. Unfortunately, Dot does not support drawing B-Trees directly. After some googling and some experiments, however, I found a solution which produces pretty neat results:

```
digraph {
graph [margin=0, splines=line];
edge [penwidth=2];
node [shape = record, margin=0.03,1.2, penwidth=2, style=filled, fillcolor=white];
node0[label = "<f0> • | 2 | <f1> • | 6 | <f2> • | 15 | <f3> •"];
node1[label = "<f0> • | 0 | <f1> • | 1 | <f2> •"];
node2[label = "<f0> • | 3 | <f1> • | 4 | <f2> •"];
node3[label = "<f0> • | 7 | <f1> • | 8 | <f2> • | 9 | <f3> • | 12 | <f4> •"];
node4[label = "<f0> • | 16 | <f1> • | 17 | <f2> •"];
node0:f0 -> node1;
node0:f1 -> node2;
node0:f2 -> node3;
node0:f3 -> node4;
}
```

The code shown above produces the following output:

I thinks this looks preety good and the cool thing is that you can generate the Dot description automatically if you have a working implementation of a B-Tree.