B-trees are a data structure designed to take advantage of the block structure of memory devices, particularly disks.

1. The memory hierarchy

Most of the time, programmers will assume that memory is flat, meaning that all memory references are equally expensive. While hardware designers work very hard to make memory references cheap, they are not all equally cheap.

Typical CPUs implement several layers of caching backed by system memory and then virtual memory. The cache layers are very fast memory (typically on the same die as the CPU); system memory is slower; virtual memory is slower by 6 orders of magnitude. Typically data is moved to the fastest available level of the cache when it is accessed; data that hasn't been accessed in a while is pushed out to slower levels to make room. To amortize the overhead costs of this process, data is managed in blocks, which may range from as little as 64 bytes for the on-chip caches to as much as 4096 bytes or more for the virtual memory system.

The effect of storing data in caches is that it's cheaper—sometimes much cheaper—to access data at an address close to other addresses you've looked at recently than to access data far away.

2. Caching and data structures

The structure of the cache system means that, all else being equal, a data structure will run faster if it has good locality, which means that pieces of the data structure accessed around the same time tend to be in about the same place. For example, given the choice between searching through an unsorted array and an unsorted linked list, you are better off searching the array: each position you look at in the array comes right after the previous position, so is likely to be stored in the same block. In contrast, the elements of the linked list will be wherever malloc managed to scrounge up space: in the worst case, one element per virtual memory block, each of which needs to be paged in from disk if you are running low on space. The disadvantage of the array over the linked list is that calling realloc may be expensive; one way to avoid this is to build a linked list of large nodes each of which holds an array, as done in this sample code: stackBlockList.c. This is actually slightly slower than just building a stack as an array (stackArray.c) but much faster than the simple linked-list approach (stackList.c).

A similar issue arises with binary search trees. Because we are only jumping through O(log n) nodes, the added cost of bad locality is not as noticeable as with linked lists, but we'd like to reduce it, especially if we expect our tree nodes to be stored on a slow device like a disk.

3. B-trees

B-trees solve this problem by grouping what would be many nodes together into a single giant node. The idea is that each node contains an array k keys and pointers to k+1 children, for a value of k that lies somewhere between m/2 and m (except for the root) where m is a parameter of the tree called the order. Searching a B-tree consists of finding the child in between the two keys that our target lies between. A picture of one node in a B-tree:

 14 38 57
A  B  C  D

Here there are three keys and four children A, B, C, and D. Node A is the root of a B-tree holding all keys less than 14, B the root of a B-tree holding all keys strictly between 14 and 38, etc.

At the bottom of the tree are leaf nodes that don't hold any pointers. A sophisticated implementation of a B-tree may take advantage of this to pack more keys into the leaves while still keeping the size of each node fitting neatly inside the block size (the implementation given below is not that sophisticated). At the top is a root node, which is just like any other internal node except that it may contain fewer than m/2 keys.

3.1. Insertions

To insert a key, we start by inserting it at the leaf, by moving any larger keys up to make room and then writing it into the sorted array. If the leaf becomes full, this may require some rebalancing.

B-trees are always completely balanced, with each leaf the same distance from the root. The mechanism for balancing a B-tree is that when a node becomes full, it splits into two nodes and pushes a key up into its parent. For example, we might split a three-key node into two one-key nodes like this:

 14 38 57
A  B  C  D
    
    (38)
 14      57
A  B    C  D

Pushing the key up into the parent will increase the number of keys in the parent and may force the parent to split as well. If we find ourselves splitting the root, we create a new root with one key and two children. This is the only way the height of the tree can increase.

3.2. Deletions

Deletion is mostly just the reverse of insertion, but has a lot of messy special cases. As in a binary search tree, it's complicated to delete a key from an internal node; the solution is to delete a key from a nearby leaf instead. We do not implement deletion in the code below, but you can read about it in HorowitzEtAl §11.2.4.

4. Implementation

Here is a basic implementation, not-very-tuned implementation of a B-tree. Despite the horrendous amount of copying in btInsert, the test program runs about four times faster with this implementation than an adapted version runs on the AVL tree code from C/AvlTree. There are many possible reasons for this (the AVL tree code is not very optimized), but cache performance and avoiding malloc overhead are probably the big factors.

   1 /* implementation of a B-tree */
   2 typedef struct btNode *bTree;
   3 
   4 /* create a new empty tree */
   5 bTree btCreate(void);
   6 
   7 /* free a tree */
   8 void btDestroy(bTree t);
   9 
  10 /* return nonzero if key is present in tree */
  11 int btSearch(bTree t, int key);
  12 
  13 /* insert a new element into a tree */
  14 void btInsert(bTree t, int key);
  15 
  16 /* print all keys of the tree in order */
  17 void btPrintKeys(bTree t);

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <assert.h>
   4 #include <string.h>
   5 
   6 #include "bTree.h"
   7 
   8 #define MAX_KEYS (1024)
   9 
  10 struct btNode {
  11     int isLeaf;     /* is this a leaf node? */
  12     int numKeys;    /* how many keys does this node contain? */
  13     int keys[MAX_KEYS];
  14     struct btNode *kids[MAX_KEYS+1];  /* kids[i] holds nodes < keys[i] */
  15 };
  16 
  17 bTree
  18 btCreate(void)
  19 {
  20     bTree b;
  21 
  22     b = malloc(sizeof(*b));
  23     assert(b);
  24 
  25     b->isLeaf = 1;
  26     b->numKeys = 0;
  27 
  28     return b;
  29 }
  30 
  31 void
  32 btDestroy(bTree b)
  33 {
  34     int i;
  35 
  36     if(!b->isLeaf) {
  37         for(i = 0; i < b->numKeys + 1; i++) {
  38             btDestroy(b->kids[i]);
  39         }
  40     }
  41 
  42     free(b);
  43 }
  44 
  45 /* return smallest index i in sorted array such that key <= a[i] */
  46 /* (or n if there is no such index) */
  47 static int
  48 searchKey(int n, const int *a, int key)
  49 {
  50     int lo;
  51     int hi;
  52     int mid;
  53 
  54     /* invariant: a[lo] < key <= a[hi] */
  55     lo = -1;
  56     hi = n;
  57 
  58     while(lo + 1 < hi) {
  59         mid = (lo+hi)/2;
  60         if(a[mid] == key) {
  61             return mid;
  62         } else if(a[mid] < key) {
  63             lo = mid;
  64         } else {
  65             hi = mid;
  66         }
  67     }
  68 
  69     return hi;
  70 }
  71 
  72 int
  73 btSearch(bTree b, int key)
  74 {
  75     int pos;
  76 
  77     /* have to check for empty tree */
  78     if(b->numKeys == 0) {
  79         return 0;
  80     }
  81 
  82     /* look for smallest position that key fits below */
  83     pos = searchKey(b->numKeys, b->keys, key);
  84 
  85     if(pos < b->numKeys && b->keys[pos] == key) {
  86         return 1;
  87     } else {
  88         return(!b->isLeaf && btSearch(b->kids[pos], key));
  89     }
  90 }
  91 
  92 /* insert a new key into a tree */
  93 /* returns new right sibling if the node splits */
  94 /* and puts the median in *median */
  95 /* else returns 0 */
  96 static bTree
  97 btInsertInternal(bTree b, int key, int *median)
  98 {
  99     int pos;
 100     int mid;
 101     bTree b2;
 102 
 103     pos = searchKey(b->numKeys, b->keys, key);
 104 
 105     if(pos < b->numKeys && b->keys[pos] == key) {
 106         /* nothing to do */
 107         return 0;
 108     }
 109 
 110     if(b->isLeaf) {
 111 
 112         /* everybody above pos moves up one space */
 113         memmove(&b->keys[pos+1], &b->keys[pos], sizeof(*(b->keys)) * (b->numKeys - pos));
 114         b->keys[pos] = key;
 115         b->numKeys++;
 116 
 117     } else {
 118 
 119         /* insert in child */
 120         b2 = btInsertInternal(b->kids[pos], key, &mid);
 121         
 122         /* maybe insert a new key in b */
 123         if(b2) {
 124 
 125             /* every key above pos moves up one space */
 126             memmove(&b->keys[pos+1], &b->keys[pos], sizeof(*(b->keys)) * (b->numKeys - pos));
 127             /* new kid goes in pos + 1*/
 128             memmove(&b->kids[pos+2], &b->kids[pos+1], sizeof(*(b->keys)) * (b->numKeys - pos));
 129 
 130             b->keys[pos] = mid;
 131             b->kids[pos+1] = b2;
 132             b->numKeys++;
 133         }
 134     }
 135 
 136     /* we waste a tiny bit of space by splitting now
 137      * instead of on next insert */
 138     if(b->numKeys >= MAX_KEYS) {
 139         mid = b->numKeys/2;
 140 
 141         *median = b->keys[mid];
 142 
 143         /* make a new node for keys > median */
 144         /* picture is:
 145          *
 146          *      3 5 7
 147          *      A B C D
 148          *
 149          * becomes
 150          *          (5)
 151          *      3        7
 152          *      A B      C D
 153          */
 154         b2 = malloc(sizeof(*b2));
 155 
 156         b2->numKeys = b->numKeys - mid - 1;
 157         b2->isLeaf = b->isLeaf;
 158 
 159         memmove(b2->keys, &b->keys[mid+1], sizeof(*(b->keys)) * b2->numKeys);
 160         if(!b->isLeaf) {
 161             memmove(b2->kids, &b->kids[mid+1], sizeof(*(b->kids)) * (b2->numKeys + 1));
 162         }
 163 
 164         b->numKeys = mid;
 165 
 166         return b2;
 167     } else {
 168         return 0;
 169     }
 170 }
 171 
 172 void
 173 btInsert(bTree b, int key)
 174 {
 175     bTree b1;   /* new left child */
 176     bTree b2;   /* new right child */
 177     int median;
 178 
 179     b2 = btInsertInternal(b, key, &median);
 180 
 181     if(b2) {
 182         /* basic issue here is that we are at the root */
 183         /* so if we split, we have to make a new root */
 184 
 185         b1 = malloc(sizeof(*b1));
 186         assert(b1);
 187 
 188         /* copy root to b1 */
 189         memmove(b1, b, sizeof(*b));
 190 
 191         /* make root point to b1 and b2 */
 192         b->numKeys = 1;
 193         b->isLeaf = 0;
 194         b->keys[0] = median;
 195         b->kids[0] = b1;
 196         b->kids[1] = b2;
 197     }
 198 }

See also testBTree.c and Makefile.