B+ Tree Fanout Calc

Problem

Compute B+ tree node capacities from storage sizes.

block_size is the node size, key_size is the size of a key, and pointer_size is the size of a pointer. An internal node with m pointers also stores m-1 keys, so fanout is (block_size + key_size) // (key_size + pointer_size); a leaf entry is a key plus a record pointer, so leaf capacity is block_size // (key_size + pointer_size).

Return [internal_fanout, leaf_capacity].

Hint

Internal nodes store one more pointer than the keys they hold.

Test cases

case 1

in: [4096,8,8]

expected: [256,256]

case 2

in: [1024,4,4]

expected: [128,128]

case 3

in: [512,8,4]

expected: [43,42]

case 4

in: [64,4,4]

expected: [8,8]

Starter codePython

def bplus_fanout(block_size, key_size, pointer_size):
    # Your code here
    pass

4 test cases · run your code against them in the editor