Per Vognsen on Nostr: PSA: If you construct a B-tree with splitting-based inserts then constructing the ...
PSA: If you construct a B-tree with splitting-based inserts then constructing the tree from items in key-sorted order is actually the worst case for packing efficiency. Every node/leaf ends up exactly 50% full except for the right spine. When you bulk-construct a tree from scratch from sorted items, you want to do the construction bottom up and you don't want to use splits. That's linear time and yields an optimally packed tree (everything full excerpt for a partially packed right spine).
Published at
2024-05-16 19:57:37Event JSON
{
"id": "8b7e192677c13589e45265f20475400edab52a0d6944a623ccda777a210243c6",
"pubkey": "a297d2ef6a36a76aa5241cfc4c0ab5ab13e37ab15aaa46b48dabd8cc3ace895c",
"created_at": 1715889457,
"kind": 1,
"tags": [
[
"proxy",
"https://mastodon.social/users/pervognsen/statuses/112452531494944497",
"activitypub"
]
],
"content": "PSA: If you construct a B-tree with splitting-based inserts then constructing the tree from items in key-sorted order is actually the worst case for packing efficiency. Every node/leaf ends up exactly 50% full except for the right spine. When you bulk-construct a tree from scratch from sorted items, you want to do the construction bottom up and you don't want to use splits. That's linear time and yields an optimally packed tree (everything full excerpt for a partially packed right spine).",
"sig": "d2faf44bdf239c0ad475a30adcb6ea07205db625e0dfc6b79350aed8a6147c8bd0f3c115af4fd1690795e41b100ab67a390981fbe667a9b8590c6c680c27d591"
}
