ization of binary trees. They come in
many variations and are used in many
databases (including MySQL InnoDB7
and PostgreSQL10) and even file systems (HFS+, 1 HTrees in ext46). The B in
B-tree stands for Bayer, the author of
the original data structure, or Boeing,
where he worked at that time.
In a binary tree every node has two
children (referred as a left and a right
child). Left and right subtrees hold the
keys that are less than and greater than
the current node key, respectively. To
keep the tree depth to a minimum, a binary tree has to be balanced: when randomly ordered keys are being added to
the tree, it is natural that one side of
the tree will eventually get deeper than
the other.
One way to rebalance a binary tree
is to use so-called rotation: rearrange
nodes, pushing the parent node of the
longer subtree down below its child
and pulling this child up, effectively
placing it in its parent’s position. Figure 1 is an example of rotation used for
balancing in a binary tree. On the left,
a binary tree is unbalanced after adding node 2 to it. In order to balance the
tree, node 3 is used as a pivot (the tree
is rotated around it). Then node 5, previously a root node and a parent node
for 3, becomes its child node. After the
rotation step is done, the height of the
left subtree decreases by one and the
height of the right subtree increases by
one. The maximum depth of the tree
has decreased.
Binary trees are most useful as in-memory data structures. Because
of balancing (the need to keep the
depth of all subtrees to a minimum) and low fanout (a maximum
of two pointers per node), they do
not work well on disk. B-trees allow
for storing more than two pointers
per node and work well with block
devices by matching the node size
to the page size (for example, 4KB).
Some implementations today use
larger node sizes, spanning across
multiple pages in size.
B-trees have the following properties:
˲ Sorted. This allows sequential
scans and simplifies lookups.
˲ Self-balancing. There is no need to
balance the tree during insertion and I M
A
G
E
B
Y
D
A
R
I
U
S
H
M
/
S
H
U
T
T
E
R
S
T
O
C
K
