Part 7 - Introduction to the B-Tree

The B-Tree is the data structure SQLite uses to represent both tables and indexes, so it’s a pretty central idea. This article will just introduce the data structure, so it won’t have any code.

Why is a tree a good data structure for a database?

• Searching for a particular value is fast (logarithmic time)
• Inserting / deleting a value you’ve already found is fast (constant-ish time to rebalance)

|

Unlike a binary tree, each node in a B-Tree can have more than 2 children. Each node can have up to m children, where m is called the tree’s “order”. To keep the tree mostly balanced, we also say nodes have to have at least m/2 children (rounded up).

Exceptions:

• Leaf nodes have 0 children
• The root node can have fewer than m children but must have at least 2

Until we get to implementing indexes, I’m going to talk solely about B+ trees, but I’ll just refer to it as a B-tree or a btree.

Nodes with children are called “internal” nodes. Internal nodes and leaf nodes are structured differently:

• up to 3 children per internal node
• up to 2 keys per internal node
• at least 1 key per internal node
  An empty B-tree has a single node: the root node. The root node starts as a leaf node with zero key/value pairs:

|

If we insert a couple key/value pairs, they are stored in the leaf node in sorted order.

|

Let’s say that the capacity of a leaf node is two key/value pairs. When we insert another, we have to split the leaf node and put half the pairs in each node. Both nodes become children of a new internal node which will now be the root node.

|

The internal node has 1 key and 2 pointers to child nodes. If we want to look up a key that is less than or equal to 5, we look in the left child. If we want to look up a key greater than 5, we look in the right child.

Now let’s insert the key “2”. First we look up which leaf node it would be in if it was present, and we arrive at the left leaf node. The node is full, so we split the leaf node and create a new entry in the parent node.

|

|

The solution is to split the root node into two internal nodes, then create new root node to be their parent.

|

The depth of the tree only increases when we split the root node. Every leaf node has the same depth and close to the same number of key/value pairs, so the tree remains balanced and quick to search.

I’m going to hold off on discussion of deleting keys from the tree until after we’ve implemented insertion.

When we implement this data structure, each node will correspond to one page. The root node will exist in page 0. Child pointers will simply be the page number that contains the child node.

Next time, we start implementing the btree!