I am trying to implement a BTree in a pointer-free language as a proof-of-concept. However, a question came to my mind: every time I need to split a node, I need to do a deep copy of all the nodes in the (new) left sub-tree and right sub-trees, thus (I think) destroying the advantages of using a BTree. If I had pointers, I would just point the new root to each of the new half nodes. Is that correct?

Also, I thought about trying to replicate the pointer behavior by having keys to be integers which are a list index, and that list would contain all nodes, representing a disk, for example. Although that would also destroy the advantages of a BTree, I could implement some data type that is equivalent to a list, but is written on the disk, and then everything would be ok. Is that right?

  • $\begingroup$ I have made the question language-agnostic since we like to deal with principles, not programming here. If you need specific advice on how to do things in Python, please head over to Stack Overflow. $\endgroup$ – Raphael Aug 6 '14 at 16:36
  • 1
    $\begingroup$ As for your question: 1) List lookup can be bad; how it the list implemented? If you have linear search time, you can use lists in the first place. Also, the advantages B-trees have w.r.t. memory usage are certainly gone. 2) Check out functional implementations of search trees, e.g. in Okasaki ("Purely Functional Data Structures"). $\endgroup$ – Raphael Aug 6 '14 at 16:39
  • 4
    $\begingroup$ When you say a pointer-free language, do you mean one which is pass-by-value or pass-by-reference? Remember that lots of languages, like Python, pass around references, so it's more like "everything is a pointer" rather than "nothing is a pointer" $\endgroup$ – jmite Aug 6 '14 at 19:39
  • $\begingroup$ Yes, jmite, i am talk talking about Python, which is pass-by-reference. Does that mean that i could implement it in Python without any performance penalties? $\endgroup$ – alansammarone Aug 6 '14 at 23:06

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.