This article gives an insight into file persistence of B-Tree Index.
A node with null parent is called root node.
As we create a B-Tree index, it is initialized with a root node and stored in file.
Node data will contain following components:
- 2 bytes for key count
- Each key will be written based on the configured key’s marshaller
- 1 byte for knowing whether the node is branch or leaf
- If branch, each child’s node ID will be written, which will be of type long, so 8 bytes
- If leaf, each value will be written based on the configured value’s marshaller
- Next node’s ID will be written which will be of type long, so 8 bytes
Following is a simple example of a B-Tree index.
We allow page overflow if there are <= 3 keys in the node. Otherwise a split will occur on overflow. The limit of page size is set to 51 bytes.
We add 25 to the index. Since the index is empty it will be initiated with a root node and 25 will get added to the root node. The root node will be stored in page 0.
Next add 50 to the index. Since the no. of leaves are still less than four, it will get added to the root node. Now the root node will have two two leaves – 50 and 25. The data (56) exceeds the allocated page size (51) so some part of the data (51) will sit in page 0 and remaining (Page Header + 5) in page 1. Page 0 next pointer links to page 1.
Next we add 75 to the index. The no. of leaves are still less than four so it will get added to the root node.
The root node will have three leaves – 50, 25 and 75. The data exceeds the allocated page size so some part of the data will sit in page 0 and remaining in page 1. Page 0 next pointer links to page 1.Next we add 5 to the index. The no. of leaves (5, 25, 50, 75) exceed three so in case of any overflow, the root node will split into two. The left node will have two leaves 5 and 25. The right node will have 50 and 75. The middle leaf (50) will be promoted as root node to the leaves. The root node will be stored in page 0. It doesn’t need extra page so page 1 will be freed and will be added to the free list. The left node is stored in page 2 and page 4. The right node will be stored in page 3 and page 5.
Since the no. of leaves exceed 3, the left node will be split into a new node. 25 and 30 will be move into the new node. The new node becomes right node to the current left node and the previous right node becomes right node to the new node. 25 is promoted to the parent. The parent node will need an extra page as one page is not sufficient so a new page is allocated.
Add 20. Since it is less than 25, it will add to the left most child. The size exceeds the allocated pages. The no. of leaves exceed 3 so the node will split into two and 15 will be promoted to root node. For the node, having 15 and 20 as leaves, pages 9 and 10 will be allocated to store it.
The second child will have leaves 15, 20, 22, 23 but the allocated pages won’t be sufficient to store the node. The node will be split into two. Node holding 22 and 23 will be allocated new pages 11 and 12.
22 from the new node will be promoted to the root node. The root node will have leaves 15,22,25 and 50. The data will exceed the pages allocated so the root node will be split and the middle leaf 25 will be promoted to new root node.
The new root node has only one leaf 25 so it doesn’t need two pages and page 8 will be freed.
Another view of nodes and the pages.