Understanding B+ Tree in Computer Science

1. Introduction and Core Concepts

A B+ Tree is a self-balancing, multi-way search tree specifically optimized for systems that read and write large blocks of data, such as disks and storage engines. It is a variant of the B-Tree, but with a critical structural difference: all data records (or pointers to records) are stored exclusively in the leaf nodes, while internal nodes store only keys for routing. This design makes B+ Trees exceptionally efficient for range queries, sequential access, and high-throughput database operations, which is why they serve as the default index structure in most relational databases and file systems.

To understand why the b+ tree matters, consider the memory hierarchy of modern computers. Accessing data from main memory is fast, but accessing data from disk or SSD is orders of magnitude slower. Disk access is not byte-addressable; data is transferred in large blocks or pages, typically 4KB to 16KB in size. A binary search tree, which has a height of O(log n), may require many random disk accesses to find a single key. A B+ Tree, with its high branching factor (often 100 to 1000), dramatically reduces tree height. A tree of height 3 or 4 can index millions to billions of records, meaning any search requires only 3-4 disk I/O operations.

The core properties that define a B+ Tree of order m (also called branching factor or fanout) are strict and guarantee balance and efficiency. Every internal node except the root must have between ceil(m/2) and m children. The root may have as few as 2 children if it is not a leaf. All leaves must be at the same depth, ensuring the tree remains perfectly balanced. Crucially, leaf nodes are linked together via a singly or doubly linked list, forming a sequential chain that allows for rapid in-order traversal without ever backtracking to internal nodes.

Key Terminology

Understanding a b+ tree requires familiarity with its specific vocabulary. The order or branching factor determines the maximum number of children a node can have and directly impacts node size and disk page utilization. Keys are the values used for searching and routing, while values or payloads are the associated data records. In internal nodes, keys act as separators: a key k in an internal node indicates that all keys in the left subtree are less than k and all keys in the right subtree are greater than or equal to k.

Another essential concept is fill factor or occupancy. Because nodes are required to be at least half full, the tree guarantees excellent space utilization, typically 50% at worst and around 67-75% on average in practice. This prevents wasted disk space and keeps the tree shallow. The linked leaf level is often called the sequence set, while the internal nodes form the index set. This separation is the fundamental innovation of the B+ Tree.

2. How It Works

The mechanism of a B+ Tree revolves around three primary operations: search, insertion, and deletion. All operations begin at the root and proceed downwards, leveraging the sorted keys within each node to choose the correct child pointer. Because internal nodes contain only routing keys and not data, they can store many more keys per disk page than a standard B-Tree, which increases the fanout and decreases the height.

Search in a b+ tree is straightforward. Starting from the root, the algorithm performs a binary or linear search within the node's sorted keys to find the interval containing the search key. It then follows the corresponding child pointer. This process repeats until a leaf node is reached. In the leaf, it searches for the key; if found, it returns the associated value, otherwise it reports a miss. For range queries, such as finding all keys between 20 and 50, the tree locates the leaf containing 20 and then simply traverses the leaf linked list sequentially until it exceeds 50, which is vastly more efficient than performing an in-order traversal of a B-Tree.

Insertion maintains balance through node splitting. The tree first searches for the appropriate leaf node where the new key belongs. If the leaf has space (fewer than m-1 keys), the key is inserted in sorted order. If the leaf is full, it is split into two nodes, each containing roughly half the keys. The smallest key of the new right node is copied up to the parent as a separator. If the parent is also full, it splits as well, propagating upwards. Splitting may cascade all the way to the root; if the root splits, a new root is created and the tree height increases by one. This bottom-up splitting guarantees all leaves remain at the same depth.

Deletion and Rebalancing

Deletion is the most complex operation because it must handle underflow. The key is first removed from its leaf. If the leaf still satisfies the minimum occupancy (at least ceil(m/2)-1 keys), the operation is complete, though the separator key in the parent may need updating if the deleted key was the smallest in the leaf. If the leaf underflows, the tree attempts to rebalance by borrowing a key from a sibling. If a left or right sibling has more than the minimum number of keys, a key can be redistributed via the parent.

If borrowing is not possible because both siblings are minimally full, the leaf must be merged with a sibling. The two leaves are combined, and the separator key in the parent is removed. This may cause the parent to underflow, triggering further borrowing or merging up the tree. If merging propagates to the root and the root is left with only one child, the root is removed and its child becomes the new root, decreasing the tree height by one. This careful rebalancing ensures the tree never degenerates.

The leaf linked list must be maintained during all structural changes. When a leaf splits, the next pointers are updated to preserve the chain. When leaves merge or redistribute, the linked list is similarly adjusted. This extra pointer maintenance is a small price to pay for the enormous benefit of O(k + log n) range queries, where k is the number of results.

3. Implementation

Implementing a b+ tree in Python requires careful handling of node types, splitting logic, and leaf linkage. While production database engines implement B+ Trees on disk with page management and concurrency control, an in-memory Python implementation clearly illustrates the core algorithms. The order of the tree is a crucial tuning parameter; for in-memory simulation we use a small order like 4 for clarity, but on-disk systems use orders of 100 or more.

The following implementation defines two types of nodes implicitly through a flag. Internal nodes store keys and child pointers, while leaf nodes store keys, values, and a next pointer. This simplified version supports search, insertion, and range queries.

class BPlusTreeNode:
    def __init__(self, order, is_leaf=False):
        self.order = order
        self.keys = []
        self.is_leaf = is_leaf
        # Internal node: children are BPlusTreeNodes
        # Leaf node: values are payloads and next is leaf link
        self.children = []
        if is_leaf:
            self.values = []
            self.next = None  # Pointer to next leaf node

    def is_full(self):
        return len(self.keys) >= self.order - 1

    def find_insert_position(self, key):
        # Return index where key should be inserted to keep sorted order
        for i, k in enumerate(self.keys):
            if key < k:
                return i
        return len(self.keys)

class BPlusTree:
    def __init__(self, order=4):
        self.order = order
        self.root = BPlusTreeNode(order, is_leaf=True)

    def search(self, key):
        node = self.root
        # Traverse down to leaf level
        while not node.is_leaf:
            idx = node.find_insert_position(key)
            # If key equals separator, go to right child
            if idx < len(node.keys) and key == node.keys[idx]:
                idx += 1
            # Clamp index to valid child range
            if idx >= len(node.children):
                idx = len(node.children) - 1
            node = node.children[idx]
        # Search within leaf
        for i, k in enumerate(node.keys):
            if k == key:
                return node.values[i]
        return None

    def range_query(self, start_key, end_key):
        result = []
        node = self.root
        # Find leaf containing start_key
        while not node.is_leaf:
            idx = node.find_insert_position(start_key)
            if idx < len(node.keys) and start_key == node.keys[idx]:
                idx += 1
            if idx >= len(node.children):
                idx = len(node.children) - 1
            node = node.children[idx]
        # Traverse leaf chain
        while node is not None:
            for i, k in enumerate(node.keys):
                if start_key <= k and k <= end_key:
                    result.append((k, node.values[i]))
                elif k > end_key:
                    return result
            node = node.next
        return result

def split_leaf(self, leaf, parent, parent_index):
    # Split a full leaf into two leaves
    mid = len(leaf.keys) // 2
    new_leaf = BPlusTreeNode(self.order, is_leaf=True)
    
    # Move upper half to new leaf
    new_leaf.keys = leaf.keys[mid:]
    new_leaf.values = leaf.values[mid:]
    leaf.keys = leaf.keys[:mid]
    leaf.values = leaf.values[:mid]
    
    # Maintain leaf linked list
    new_leaf.next = leaf.next
    leaf.next = new_leaf
    
    # Copy up separator key to parent
    separator = new_leaf.keys[0]
    parent.keys.insert(parent_index, separator)
    parent.children.insert(parent_index + 1, new_leaf)
    return separator

def split_internal(self, node, parent, parent_index):
    mid = len(node.keys) // 2
    separator = node.keys[mid]
    
    new_internal = BPlusTreeNode(self.order, is_leaf=False)
    new_internal.keys = node.keys[mid + 1:]
    new_internal.children = node.children[mid + 1:]
    
    node.keys = node.keys[:mid]
    node.children = node.children[:mid + 1]
    
    parent.keys.insert(parent_index, separator)
    parent.children.insert(parent_index + 1, new_internal)

def insert(self, key, value):
    # Handle root split as special case
    if self.root.is_full():
        new_root = BPlusTreeNode(self.order, is_leaf=False)
        new_root.children.append(self.root)
        if self.root.is_leaf:
            self.split_leaf(self.root, new_root, 0)
        else:
            self.split_internal(self.root, new_root, 0)
        self.root = new_root

    self._insert_non_full(self.root, key, value)

def _insert_non_full(self, node, key, value):
    if node.is_leaf:
        idx = node.find_insert_position(key)
        node.keys.insert(idx, key)
        node.values.insert(idx, value)
    else:
        idx = node.find_insert_position(key)
        # Adjust for equality to go right
        if idx < len(node.keys) and key >= node.keys[idx]:
            idx += 1
        child = node.children[idx]
        if child.is_full():
            if child.is_leaf:
                self.split_leaf(child, node, idx)
                # Decide which child to descend into after split
                if key >= node.keys[idx]:
                    idx += 1
            else:
                self.split_internal(child, node, idx)
                if key > node.keys[idx]:
                    idx += 1
        self._insert_non_full(node.children[idx], key, value)

This implementation omits deletion for brevity, but the search and insertion logic demonstrates the essential principles: top-down traversal, lazy splitting, and the critical distinction between copying up a separator from a leaf versus moving up a separator from an internal node. In a leaf split, the separator remains in the leaves; in an internal split, it is removed from the original node.

4. Step-by-Step Example

To solidify understanding, let us walk through inserting keys into a b+ tree of order m=4. This means each node can hold at most 3 keys and 4 children, and each node except the root must hold at least 1 key (for leaves) or 2 children (for internal nodes). We will insert keys in the order: 10, 20, 5, 6, 12, 30, 7, 17.

Initial State: The tree starts as a single empty leaf node which is also the root.

Insert 10, 20, 5: All three keys fit into the root leaf. The leaf now contains [5, 10, 20] in sorted order. No splits are needed.

Insert 6: The leaf is full (3 keys). It must split. The sorted keys [5, 6, 10, 20] are divided at mid = 2. The left leaf retains [5, 6] and the new right leaf gets [10, 20]. The smallest key of the right leaf, 10, is copied up to a new root. The tree now has height 2: Root [10] with two leaf children [5, 6] -> [10, 20]. The leaves are linked.

Continuing Insertions

Insert 12: Traverse from root. Since 12 >= 10, go to the right leaf [10, 20]. It has space, so insert 12 to get [10, 12, 20].

Insert 30: Again go to right leaf [10, 12, 20]. It is full, so it splits. Sorted keys [10, 12, 20, 30] split into [10, 12] and [20, 30]. The separator 20 is copied up to the root, which becomes [10, 20] with three leaf children: [5, 6] -> [10, 12] -> [20, 30].

Insert 7: Traverse: 7 < 10, so go to leftmost leaf [5, 6]. It has space, becomes [5, 6, 7].

Insert 17: Traverse: 10 <= 17 < 20, so go to middle leaf [10, 12]. It has space, becomes [10, 12, 17]. The final tree structure is:

• Root (internal): keys [10, 20]
• Leaf 1: [5, 6, 7] -> Leaf 2: [10, 12, 17] -> Leaf 3: [20, 30]

Notice how all data resides in the leaves and the leaves form a sorted linked list. A range query for keys between 6 and 17 would find the leaf containing 6, then scan forward: 6, 7, 10, 12, 17, requiring only leaf-level traversal after the initial descent.

If we were to next insert 8, the leftmost leaf [5, 6, 7] would be full and split into [5, 6] and [7, 8], pushing separator 7 up to the root, which would then become [7, 10, 20] — still not full. The next insertion that causes the root to split would increase the tree height to 3.

5. Complexity Analysis

The performance of a b+ tree is dominated by its height, which is logarithmic but with a very large base. For a tree storing n keys with order m, the height h is bounded by O(log_{ceil(m/2)} n). Because m is typically large (100-1000 for disk-based trees), the height remains extremely small even for massive datasets. A B+ Tree indexing 100 million records with m=200 has a height of only 3-4.

Search, insertion, and deletion all require traversing from root to leaf, performing a search within each node. If binary search is used within nodes, the cost per node is O(log m), but since m is constant relative to n, this is often treated as O(1) for asymptotic analysis. The dominant cost in external memory models is the number of disk I/O operations, which is exactly h, or O(log_m n).

Range queries are where B+ Trees excel. Finding the start of the range costs O(log_m n), and then scanning k successive elements via the leaf chain costs O(k). In contrast, a B-Tree would require an in-order traversal that repeatedly goes up and down the tree, costing O(k log_m n). This makes B+ Trees ideal for database range scans, ORDER BY queries, and prefix searches.

Space complexity is O(n) overall, as every key is stored once in a leaf plus separators in internal nodes. However, internal nodes store only keys and pointers, not full records, so the constant factor is small. The worst-case space utilization is 50%, but with random insertions it typically stabilizes around 69% due to the properties of node splitting, a result known from Yao's analysis. Bulk loading can achieve over 90% occupancy.

It is important to distinguish between in-memory time complexity and I/O complexity. In the external memory model where a disk block transfer is the unit cost, B+ Tree operations are optimal for comparison-based dictionaries that support ordered iteration. No other comparison-based structure can achieve fewer I/Os for search and range queries.

6. Variations and Optimizations

Several important variations of the basic b+ tree have been developed to improve performance for specific workloads. The most common is the B* Tree, which improves space utilization by requiring nodes to be at least 2/3 full instead of 1/2 full. When a node overflows in a B* Tree, it first attempts to redistribute keys with a sibling before splitting. Only when both siblings are full does it split two nodes into three, leading to higher average occupancy (around 80%) and a slightly shallower tree.

Prefix B+ Trees and Prefix Compression optimize internal nodes by storing only the shortest prefix needed to distinguish separators. For example, instead of storing full string keys like "database" and "datafile" in an internal node, it might store just "datab" and "dataf". This allows more keys per page, increasing fanout and reducing height. Similarly, Suffix Truncation stores only the minimal separator needed to route correctly.

For write-heavy workloads, the B^link Tree (B-link Tree) adds right-link pointers to internal nodes as well as leaves, enabling highly concurrent operations without locking the entire path from root to leaf. This latch-coupling technique allows one thread to traverse down the tree while another is splitting nodes, which is critical for multi-core database engines. Modern systems like PostgreSQL's B-Tree implementation use a variant of this approach.

Bulk Loading and Buffering

Inserting keys one-by-one into an empty B+ Tree is inefficient due to repeated splits. Bulk Loading (or bulk insertion) sorts the keys first and then builds the tree bottom-up, filling leaves to near 100% and then constructing internal levels. This is typically 10-100x faster and produces a more compact tree. Most databases provide a bulk load utility for initial data import.

The Buffered B+ Tree or B^ε Tree adds buffers to internal nodes to batch updates. Small inserts are buffered in internal nodes and flushed downwards in batches, converting many small random I/Os into fewer large sequential I/Os. This is particularly effective for SSDs and write-optimized storage engines like those based on Log-Structured Merge (LSM) trees, which can be seen as an extreme form of buffering.

Other optimizations include Covering Indexes, where leaf nodes store additional non-key columns to answer queries without accessing the heap table, and Clustered vs. Unclustered B+ Trees, where a clustered index stores the actual table rows in the leaves (as in InnoDB), while an unclustered index stores pointers (RIDs) to heap rows.

7. Real-World Applications

The b+ tree is arguably the most important data structure in modern data systems. Its dominance stems from its predictable performance, excellent range query support, and alignment with block-oriented storage. Nearly every major relational database management system uses B+ Trees as its primary index structure.

Relational Databases: In MySQL's InnoDB storage engine, the primary key index is a clustered B+ Tree where leaf nodes contain the full row data. Secondary indexes are also B+ Trees that store the primary key as the payload. PostgreSQL, Oracle, and SQL Server all use B+ Trees for their default B-Tree indexes (the name B-Tree in these systems almost always refers to a B+ Tree implementation). These indexes accelerate WHERE clauses, JOINs, ORDER BY, and GROUP BY operations. A query like SELECT * FROM orders WHERE order_date BETWEEN '2024-01-01' AND '2024-01-31' is executed as a B+ Tree range scan over an index on order_date.

File Systems: Many file systems use B+ Trees to manage metadata. NTFS (Windows), ext4 (Linux), XFS, and HFS+ (macOS) use B+ Trees or B* Trees to store directory entries, file extents, and free space maps. When you list a directory with thousands of files, the file system performs a range scan over a B+ Tree. The ReiserFS file system was famously built entirely around a B+ Tree (actually a B* Tree) for all storage. Modern copy-on-write file systems like Btrfs use B+ Trees extensively.

Key-Value Stores and NoSQL: While many NoSQL systems use LSM trees for write optimization, several still rely on B+ Trees for read-heavy workloads. MongoDB's WiredTiger storage engine, CouchDB, and Berkeley DB offer B+ Tree storage. Even LSM-based systems like RocksDB and Cassandra use B+ Tree-like structures (SSTables with block indexes) that borrow heavily from B+ Tree principles for their on-disk sorted string tables.

Web Servers, Networks, and Beyond

Beyond databases, B+ Trees appear in surprising places. Web servers and operating systems use them to manage sparse data. For example, some in-memory databases and caches use B+ Trees to implement ordered maps that support both point lookups and ordered iteration, such as in network routing tables where IP prefix lookups benefit from range scans.

In information retrieval, B+ Trees index posting lists for search engines, allowing fast retrieval of documents containing a term and efficient merging of posting lists for Boolean queries. Geographic Information Systems (GIS) use B+ Trees combined with space-filling curves (like Z-order) to index spatial data. The combination of B+ Tree ordering with sequential leaf access makes it ideal for time-series databases (e.g., InfluxDB, TimescaleDB) where data is naturally ordered by timestamp and range queries over time windows are the dominant access pattern.

Even in main-memory systems where disk I/O is not the bottleneck, cache-conscious B+ Trees (like the CSS-Tree and CSB+-Tree) are used because their node size can be tuned to match CPU cache lines (64 bytes), minimizing cache misses. This shows the enduring relevance of the B+ Tree's core idea: organizing data into pages with high fanout to minimize expensive memory transfers, whether those transfers are from disk to RAM or from RAM to CPU cache.

8. Comparison with Alternatives

Choosing the right index structure depends on workload characteristics. While the b+ tree is the best all-rounder for ordered data, other structures excel in specific scenarios. Understanding the trade-offs is essential for system design and database tuning.

Compared to a standard B-Tree, the B+ Tree stores all records in leaves, while a B-Tree stores records in both internal and leaf nodes. This means B-Tree internal nodes are larger (storing payloads), reducing fanout and increasing height. B-Trees can answer point queries slightly faster if the key happens to be in an internal node, but they are significantly slower for range queries and have more complex deletion logic.

Hash Indexes provide O(1) average point lookups, far faster than B+ Trees, but they do not support range queries, prefix searches, or ORDER BY at all. Hash collisions and resizing can also cause latency spikes. Databases often offer both: use hash for exact match lookups and B+ Tree for ordered access.

Log-Structured Merge Trees (LSM Trees) are optimized for write-heavy workloads. Instead of updating a tree in place, they buffer writes in memory and flush them as sorted runs to disk, merging them in the background. This yields much higher write throughput and better sequential I/O, but reads must check multiple levels and may require Bloom filters, making point queries slower and range queries more complex than in a B+ Tree.

For in-memory workloads with no disk I/O, balanced binary search trees like AVL or Red-Black Trees have lower constant factors for small n due to simpler nodes, but their low fanout (2) means they have much greater height and poor cache locality compared to a B+ Tree with fanout 64 or 128. This is why many high-performance in-memory ordered maps (e.g., in SAP HANA) use B+ Trees even when data fits in RAM.

9. Common Mistakes and Best Practices

Implementing and using B+ Trees effectively requires avoiding several common pitfalls that can degrade performance or correctness. One of the most frequent mistakes is choosing an inappropriate order. A very small order (e.g., m=3 or 4) creates a tall, skinny tree with many levels, negating the I/O benefits. A very large order that does not align with the underlying page size (e.g., 4KB or 16KB) causes nodes to span multiple disk pages, doubling I/O cost. Best practice is to size nodes to exactly one page or a small multiple, accounting for key size, pointer size, and page header overhead.

Another critical error is misunderstanding the difference between copying up and moving up during splits. When a leaf splits, the separator key must be copied up to the parent (it remains in the right leaf). When an internal node splits, the separator is moved up (it is removed from the child). Confusing these leads to duplicate keys or missing separators and breaks search correctness. Similarly, failing to maintain the leaf linked list during splits, merges, and redistributions silently breaks range queries, which may appear to work for point queries but return incomplete results for scans.

In database usage, a common anti-pattern is creating B+ Tree indexes on low-cardinality columns (e.g., gender with two values) or on columns that are never used in WHERE, JOIN, or ORDER BY clauses. Each index adds overhead to every INSERT, UPDATE, and DELETE because all indexes must be maintained. Indexing a column with poor selectivity wastes disk space and slows writes without accelerating reads. Conversely, failing to create a composite index with the correct column order is another mistake; a B+ Tree index on (last_name, first_name) can efficiently answer queries on last_name or last_name + first_name, but not on first_name alone.

Best Practices for Production Systems

For production deployments, always consider bulk loading for initial population rather than row-by-row insertion. Bulk loading sorts data and builds the tree bottom-up, achieving near 100% page occupancy and avoiding the 50% fragmentation that can result from random inserts. Periodically rebuilding or reorganizing fragmented indexes (e.g., via REINDEX or OPTIMIZE TABLE) can reclaim space and improve scan performance.

Implement proper concurrency control if the tree will be accessed by multiple threads. Simple coarse-grained locking (locking the entire tree) kills throughput. Use latch coupling (crabbing) where you hold a latch on a parent while acquiring a latch on a child, then release the parent. For even better concurrency, adopt B^link techniques with right-links and version numbers to allow lock-free reads.

Finally, monitor fill factor and page splits. Excessive page splits indicate random insert patterns that fragment the tree. Some systems allow tuning the fill factor (e.g., FILLFACTOR in SQL Server) to leave free space in pages for future inserts, trading off initial space usage for reduced future splits. For sequential inserts (like auto-increment keys), pages will naturally fill to 100% and splits are rare, so a high fill factor is optimal.

10. Interview Questions

Technical interviews frequently probe deep understanding of B+ Trees because they test knowledge of data structures, disk I/O, and database internals simultaneously. Below are common questions with guidance on what interviewers expect.

Q1: Why does a B+ Tree store all data in leaf nodes while a B-Tree stores data in both internal and leaf nodes? What are the advantages?

This question tests your understanding of the core design trade-off. A strong answer should mention three points: First, internal nodes become smaller because they store only keys and pointers, not payloads, so more keys fit per page, increasing fanout and reducing height. Second, all queries have the same cost (root to leaf), making performance more predictable. Third, and most importantly, range queries and sequential scans become O(k + log n) via the leaf linked list, whereas B-Trees require expensive in-order traversals. Mention that this also simplifies deletion and makes the structure more suitable for block storage.

Q2: What is the height of a B+ Tree with n keys and order m? How many disk I/Os does a point search require?

Interviewers want to see if you can derive the height bound. Explain that each internal node has at least ceil(m/2) children, so the number of leaves is at least 2 * ceil(m/2)^(h-1). Since leaves hold at least ceil(m/2)-1 keys, n is bounded, leading to h = O(log_{ceil(m/2)} n). For disk I/O, emphasize that each level corresponds to one page read, so search requires h I/Os (plus one more if the payload requires a heap lookup for an unclustered index). Give a concrete example: with m=100 and n=1,000,000, h is about 3, so only 3 I/Os.

Q3: Walk me through what happens when you insert a key into a full leaf node. How does splitting propagate?

This is a hands-on algorithm question. Describe the steps: find the leaf, detect it is full, split it into two nodes with roughly half the keys each, copy the smallest key of the new right node up to the parent as a separator, and update the leaf next pointers. Then explain the recursive case: if the parent is also full, it splits (moving its middle key up), and this can propagate to the root. If the root splits, create a new root and increase height by one. Be sure to distinguish leaf split (copy up) from internal split (move up). Drawing a small example with m=4 is often expected.

Q4: When would you choose a B+ Tree over a Hash Index or an LSM Tree?

This tests system design judgment. Answer that you choose B+ Tree when you need ordered operations: range queries, prefix searches, ORDER BY, and min/max. Hash indexes are only for exact equality lookups and cannot support ordering. Choose LSM Trees when the workload is write-heavy (e.g., high-ingest logging, time-series writes) because LSM buffers writes and has much lower write amplification, but at the cost of slower reads and more complex compaction. B+ Trees are better for read-heavy or balanced OLTP workloads requiring strong consistency and predictable read latency. Mention that many modern systems actually use both.

Q5: How does deletion handle underflow? Explain borrowing vs. merging.

Expect to explain rebalancing after deletion. After removing a key from a leaf, if occupancy falls below ceil(m/2)-1, first try to borrow (redistribute) from a sibling that has extra keys, updating the parent separator. If no sibling can spare a key, merge the underfull node with a sibling, removing the separator from the parent. This may cause the parent to underflow, so the process recurses upward. If the root is left with one child, it is removed. Emphasize that borrowing is preferred because it avoids reducing the number of nodes and keeps utilization higher.