I am studying B+ trees for the first time. I just want to know, on what basis should a developer choose the order of the B+ tree?
Also, is there something like, B+ trees for the dummies tutorial? I desperately need it.
+1
A:
Ideally you'll want to pick an order that has good locality of reference to help with caching. An order which encourages sequential scans over the keys can also be helpful. In general it will depend on your data.
bdonlan
2009-05-15 17:36:06
I believe s?he means the order of the tree, not an order imposed on the items.
Joey
2009-05-15 17:42:15
You guessed it right Rössel. - he
dta
2009-05-15 17:53:48
The order of the tree imposes an order on the items. The two problems are thus one and the same :)
bdonlan
2009-05-15 17:55:07
Not ... really. The order of the tree is how many items fit into each node. Which will directly affect the tree's height. dta: I usually use the regex with the optional s at the start for genders here as sometimes it's not clear.
Joey
2009-05-18 08:04:56
Ah, I see what you mean... I had interpreted it as the ordering over the keys, yeah.
bdonlan
2009-05-18 22:08:19
+3
A:
If you mean with "order" the number of outgoing pointers in a B+-tree node, you should consider an order k so that the node on disk is a multiple of the disk sector size or the file system block size, e.g. 4 KB.
If you read a node from disk, the disk (I assuming disks here and not SSDs) must seek to the position of the node and reading the node. Seek time is much larger than the actual transfer time for the node on disk for node with the size of a some KB. So also picking an order so that the node has an on disk size of 64 KB might be a good choice.
dmeister
2009-05-16 17:28:01