Fanout and tree depth

How it behaves

One input on the horizontal axis, the others held fixed.

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

• 16-byte entries, fanout ≈ 500 → 3.3 levels
• 64-byte entries, fanout ≈ 125 → 4.3 levels
• 16 KB page, 16-byte keys, 8-byte pointers → f ≈ 683
• a billion keys at f ≈ 680 → depth ≈ 3.2
• random inserts leave pages ≈ 69% full → 1.45× the pages
• HAMT: four levels at a million entries
• HAMT: six levels at a billion
• a million entries → depth ≈ 20 in a binary tree
• binary search over a billion keys → ≈ 30 steps
• M = 10,000, f = 100 → a 2-level tree

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

• Core Data Structures

  How do we choose a data structure when the real cost is set by the hardware, not by Big-O?

  $$f=\text{page size}÷(\text{key size}+\text{pointer size})$$

  Read it in place →

• Core Data Structures

  How do we choose a data structure when the real cost is set by the hardware, not by Big-O?

  $${\log }_{32}(n)$$

  32-way branching = $f$

  Read it in place →

• Indexing

  When does a separate "where is it?" structure pay for itself, and what does it cost to keep it true?

  $$\text{fanout}=\frac{\text{page size}}{\text{entry size}},\text{height}={\log }_{\text{fanout}}N$$

  Read it in place →