B-Tree Alternatives

For decades, the B-tree has been the backbone of database indexing, enabling efficient lookups, inserts, and range queries in block-oriented storage systems. For more information, please see my post on B-Trees:

What are B-Trees?

Its balanced structure and high fanout made it the perfect match for spinning disks and later SSDs, ensuring minimal I/O operations. But as workloads, hardware, and data access patterns have evolved, cracks have started to show. Modern systems now demand faster lookups, better write performance and structures optimized for in-memory operations or large-scale distributed systems.

B-Trees and those listen below are relatively simple constructs but do take a certain amount of mental gymnastics to fully understand.

While B-trees are the default index structure in most general-purpose databases, there are several alternatives designed for specific access patterns, data shapes, or performance trade-offs.

---

B+ Trees

A refinement of the B-tree where all actual data entries are in leaf nodes; internal nodes store only keys and pointers. Leaf nodes are linked for efficient range scans.

B+ trees differ from B trees in that interior nodes carry only keys and references, not the underlying records. By freeing up that space, each node can support a greater branching factor, which shortens the tree’s height. The trade-off is that searches always descend fully to the leaves; there is no chance of completing early at an internal level. But, because the branching factor is so large, nearly all searches would reach the leaves in either structure, and on balance the B+ design tends to be faster.

A B+ tree is a data structure designed for fast storage and retrieval in databases and filesystems. It’s a variant of the B-tree where all actual records live in the leaf nodes, while internal nodes only store keys to guide searches. The leaves are linked, making it easy to scan ranges of data in order.

Because each node can branch to many children (high fan-out), a B+ tree stays shallow even with millions of records, so searches, inserts, and deletions all run in O(log n) time. Its balance and disk-friendly layout make it the backbone of indexing in most modern databases.

B Tree

• Stores keys and values in every node (both internal and leaves).
• Good for direct lookups since data can be found higher up the tree.
• Range scans are slower because you must traverse node by node.

B+ Tree

• Stores only keys in internal nodes; all actual data records are in the leaves.
• Leaves are linked together for efficient sequential access.
• Better for range queries and ordered scans, since you can walk the leaf chain.
• Internal nodes are smaller (keys only), so the tree has a higher branching factor, meaning it’s shallower and faster to traverse.

---

---

Binary Search Trees (BST) & Variants (AVL, Red-Black, Splay)

• Description: Each node stores one key and up to two children. Balanced variants ensure logarithmic height.
• Example Databases:
  • SQLite (WITHOUT ROWID tables) can internally use AVL trees.
  • Berkeley DB offers multiple balanced tree types.
• Why used: Simpler node structure, suited to in-memory indexing.

---

ISAM (Indexed Sequential Access Method)

ISAM is an old but influential indexing technique introduced by IBM in the 1960s for fast access to large volumes of data on disk. It’s not a “tree” in the same dynamic sense as a B-tree or B+ tree, but rather a static, prebuilt index structure.

• Description: Static, sorted index structure with fixed leaf pages; overflow areas handle inserts but no rebalancing.
• Example Databases:
  • IBM Informix
  • MyISAM in MySQL
• Why used: Efficient for mostly read-only datasets, low update cost.

---

LSM Trees (Log-Structured Merge Trees)

A LSM Tree is a data structure designed to handle high write throughput efficiently, especially on disk. Instead of updating records in place, new writes go into an in-memory structure (usually a balanced tree like a red-black tree, called a memtable). Once the memtable fills, it’s flushed to disk as a sorted file (called an SSTable). Over time, multiple SSTables accumulate, so the system periodically performs compaction (merging and re-sorting files) to keep lookup performance manageable.

• Description: Append-only storage with data kept in sorted runs (memtables → SSTables), merged periodically.
• Example Databases:
  • Apache Cassandra
  • RocksDB
  • LevelDB
• Why used: Excellent for high write throughput and sequential disk I/O.

---

Trie (Prefix Tree)

• Description: Each node represents part of a key (e.g., a character); traversal follows key prefixes.
• Example Databases:
  • Redis (Radix tree implementation for autocomplete/search)
  • Apache Lucene (FST-based tries for term dictionaries)
• Why used: Perfect for prefix search, IP routing, and autocomplete.

---

Hash Indexes

• Description: Direct mapping of keys to locations via a hash function.
• Example Databases:
  • PostgreSQL Hash Indexes
  • MongoDB Hashed Indexes
• Why used: O(1) lookups for exact matches; no ordering for range queries.

---

T-Trees

• Description: Hybrid of AVL trees and B-trees, designed for in-memory databases with multiple keys per node.
• Example Databases:
  • SAP HANA (historically used T-trees, now columnar)
  • TimesTen (legacy use)
• Why used: Suited for RAM-resident data where disk I/O minimization isn’t needed.

---

---