B-Trees #

• Preferred structure to store indexes in disk
• Balanced tree

Metrics #

Depth for a tree of n keys it is O(log N)

Branching factor #

• Number of child references from each node of the Tree

Write amplification #

A write request that can amplify due to SSTable merge, WAL writes, Split of B-Tree node etc.

Usages #

• Used in Berkley DB [Initial version of chubby depended on it]

Optimisations #

• Using WAL (Write ahead log) to survive crash if tree is being updated