What is a good metric to pick the degree of a B-Tree? I assume this depends on the number of expected elements? Degree 2 gives us a 2-3-4 tree (each node contains 1-3 items and 2-4 children).

How can I decide this? I am looking to store a couple of thousand keys in it.

  • 1
    $\begingroup$ Regarding speed, it really depends completely on the relative speeds of random access vs. "local" (cached or sequential) access in whatever medium (RAM, disk, etc.) you are storing the data structure. (If not for the locality-improving effect of B-trees, there would be no reason (other than saving some pointers) to prefer them over a binary tree for items much larger than a pointer.) $\endgroup$ Nov 30, 2016 at 16:07
  • $\begingroup$ @j_random_hacker that sounds like an interesting fact, even if the different is negligible, feel free to add it as an answer what the difference would be in terms of RAM vs. Disk. Happy to accept $\endgroup$
    – Mahoni
    Nov 30, 2016 at 16:14


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.