CODEWITHSUNDEEP
databasedata-structuresfile-structure
simplfuzz
simplfuzz

Reputation: 12905

B+ trees, choosing the order

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.

Upvotes: 1

Views: 1307

Answers (2)

dmeister
dmeister

Reputation: 35614

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.

Upvotes: 4

bdonlan
bdonlan

Reputation: 231163

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.

Upvotes: 1

Related Questions