• Table of contents

Most mutable storage engines use an in-place update mechanism; the most dominant one being B-Trees.

Binary Search Trees

In-memory tree structures like Binary Search Tree (BSTs), 2-3 trees, and AVL trees were not designed in mind for disk (hence the name “in-memory”) [explanation of binary search tree, this, this, this].

Problems in disk-based storage [this]

⮑ Frequent rebalancing and pointer updates.

⮑ Poor locality

Nodes are scattered randomly across disk pages.

A parent and a child can be stored in different disk pages.

⮑ High height

BSTs have fanout = 2, so even balanced trees are tall.

• fanout = maximum number of children (per node) = number of keys + 1 (per node).
• Height = log₂(N).
• Searching requires O(log N) disk seeks*.*

<aside> <img src="/icons/exclamation-mark_yellow.svg" alt="/icons/exclamation-mark_yellow.svg" width="40px" />

↑ Fanout → ↓ Height → Fewer disk seeks → Faster lookups.

</aside>