B-tree index

Hash indexes perform well only when all keys fit in memory. As the number of keys grows and memory becomes insufficient, a different indexing approach is needed.

One early solution is to divide a large hash index into smaller, manageable chunks. Each chunk can be stored on disk and loaded only when necessary.

To find a specific key, this approach requires iterating through every index chunk. This is inefficient and slows down lookups.

Each key is assigned a unique identifier. We use sequential numbers starting from 0, though any random numbers work. These are called primary keys.

A new index is created that defines the range of primary keys each hash chunk stores. This allows us to quickly locate the correct chunk.

We use binary search on the range index to identify which hash index contains the target primary key.

If the range index itself is too large to fit in memory, we apply the same strategy: create a broader range index.

This creates a cascade of indexes, each storing a wider range of primary keys. All indexes are stored on disk.

To find a record with primary key 5:

• Load the entire top-level index into memory.
• Perform binary search to find the correct child index.
• Load that index chunk from disk.
• Perform binary search again to find the next reference.
• Load the final chunk and locate the record in the data file.
• Retrieve the record bytes from disk.

The resulting structure resembles a tree. The design principles used here form the foundation of a B-tree.

A B-tree is a self-balancing tree data structure. When nodes are added or removed, the tree adjusts its shape to maintain small height.

This balancing ensures that searches, insertions, and deletions occur in logarithmic time.

B-tree indexes divide data into fixed-size blocks called pages. Each page is typically several kilobytes.

Each page manages a continuous range of keys. It contains either data or references to data files.

Non-leaf pages store keys and references to child pages. Leaf pages contain data or point to data files.

One page is designated as the root. All lookups begin from this page.

Lookups proceed by loading one page at a time, starting from the root, and following references to the next page.

Almost all relational databases use B-tree indexes.

A database table generates a unique random primary key for each record and creates a B-tree index to enable fast record identification.

Leaf nodes contain record information and reference the next leaf node in the tree.

When a database performs a lookup by key, it starts at the root of the B-tree and traverses down to the appropriate leaf node.

When searching by a column like last name, the database performs a sequential search across all leaf nodes. This process is slow because it must examine each node individually.

To speed up searches by last name, a separate B-tree index must be created. In this index, last name becomes the key, and each node stores a reference to the primary key.

To find Chandler Bean, the database first queries the second B-tree index. It locates the primary key associated with Chandler’s last name—value 15. Then, it uses that primary key to retrieve the full record from the primary B-tree index.

ActiveMQ, an open-source messaging system, uses CajaDB as its file-based message store.

CajaDB consists of three components: datalog files, metadata cache, and metadata store.

Datalog files store messages. New messages are appended to the end of these files. Messages are stored in no fixed order.

To enable fast access and preserve message order, CajaDB constructs a metadata index. This index maps message IDs to specific offsets in datalog files.

The metadata index is a B-tree structure.

The B-tree index is updated whenever a new message arrives or is consumed.

In ideal conditions, the metadata cache must be large enough to hold all B-tree index pages in memory.

If the cache is too small, it must swap index pages between memory and the persistent metadata store.

The B-tree index and cache are periodically written to the metadata store on disk.

In case of system failure or service restart, the B-tree index can be quickly restored from disk.

To rebuild the index after a restart, the system must iterate over all messages and all datalog files.