B+Tree Page Math

Before implementing search or insertion, estimate why B+Trees are shallow.

A B+Tree node is a page. The page has a fixed size, a header, and then entries.

Implement:

type PageConfig struct {
    PageSize          int
    HeaderBytes       int
    KeyBytes          int
    PointerBytes      int
    ValueBytes        int
    FillFactorPercent int
}

type Estimate struct {
    LeafCapacity  int
    InternalFanout int
    Height        int
}

func EstimateBTree(cfg PageConfig, rows int) Estimate

Definitions

Usable bytes:

usable = floor((PageSize - HeaderBytes) * FillFactorPercent / 100)

Clamp FillFactorPercent into this range:

• if FillFactorPercent <= 0, use 100,
• if FillFactorPercent > 100, use 100.

Leaf entry cost:

KeyBytes + ValueBytes

Leaf capacity:

floor(usable / leafEntryCost)

Internal node with m children stores:

m child pointers + (m - 1) separator keys

Internal fanout is the largest m such that:

m * PointerBytes + (m - 1) * KeyBytes <= usable

Height

If rows <= 0, height is 0.

If all rows fit in one leaf, height is 1.

Otherwise:

1. compute number of leaf pages,
2. repeatedly group pages by InternalFanout,
3. count how many internal levels are needed until one root remains.

Invalid config

Return a zero Estimate{} if any required byte size is impossible, for example:

• PageSize <= HeaderBytes,
• KeyBytes <= 0,
• ValueBytes <= 0,
• PointerBytes <= 0,
• computed leaf capacity is 0,
• computed internal fanout is less than 2.

Example

With:

PageSize = 128
HeaderBytes = 16
KeyBytes = 8
ValueBytes = 8
PointerBytes = 8
FillFactorPercent = 100

Usable bytes are 112.

Leaf capacity is:

112 / (8 + 8) = 7

Internal fanout is 7 because:

7 pointers + 6 keys = 7*8 + 6*8 = 104 bytes
8 pointers + 7 keys = 8*8 + 7*8 = 120 bytes too large