algorithm - Fan out in B+ trees -

how fan out affects split , merge in b+ trees?

if have 1024 bytes page , 8 byte key, , maybe 8 byte pointer, can store around 64 keys in 1 page. considering 1 page node, if have fan out of 80%, mean split happen after node 80% full after 52 keys inserted or after node overflows.

same merge, when merge nodes if have 80% fan out, when keys go less half size of node or 80% has it.

splits , merges in b-trees of kinds driven policies based on fullness criteria. best think fullness in terms of node space utilisation instead of key counts; fixed-size structures - space utilisation measured in terms of key counts , equivalent fanout - tend occur in academia , special contexts in-memory b-trees on integers or hashes. in practice there variable-size elements involved, beginning variable-size keys subject further size variation via things prefix/suffix truncation , compression.

splits invariably occur when update operation result in overflowed node. difference between policies lies in how hard try shift keys neighbouring nodes in order avoid split (looking @ 1 sibling or @ both) , in how many keys try offload (one or several). locking strategies require preventive splitting/merging during initial descent, guarantee no splits or merges can occur on way up. in case decision must made based on minimum/maximum possible key sizes instead of looking @ sizes of actual keys.

some strategies split when have 2 full neighbouring nodes split 3 nodes, , merge if have 3 neighbouring nodes on verge of underflow (resulting in 2 full nodes). net result high minimum utilisation of 2/3, average utilisation of 3/4 or higher. however, increased complexity of update algorithms worth candle.

on whole, criteria can summarised thus: split when node threatens overflow , offloading of keys neighbours not possible, merge when node threatens underflow , none of neighbours can donate key.