B+trees suck

[sans-hubris]

Well, at least writing the code for them does, especially deletion. AARGH!!!! I hate B+trees right now.

[stuka]

heh...if they were easy, Oracle would have a ton more competition!

[jemfinch]

Can you link me to a good description of their implementation?

What language are you implementing them in?

Jeremy

[sans-hubris]

Originally posted by jemfinch
Can you link me to a good description of their implementation?

What language are you implementing them in?

Jeremy It's in C++, but does it really matter? It would be difficult to implement in any language. It's difficult enough just to understand how deletion works.

[jemfinch]

Originally posted by sans-hubris
It's in C++, but does it really matter? It would be difficult to implement in any language. It's difficult enough just to understand how deletion works.

In my experience, it matters quite a bit what language you're implementing it in. Compilers can do a lot to check the correctness of code, and having a powerful typesystem at my disposal lets use the compiler to assure a great many invariants in my code.

Jeremy

[sans-hubris]

Originally posted by jemfinch
In my experience, it matters quite a bit what language you're implementing it in. Compilers can do a lot to check the correctness of code, and having a powerful typesystem at my disposal lets use the compiler to assure a great many invariants in my code.

Jeremy See, it's not that that's making the implementation of a b+tree hard. For one thing, you're dealing with binary files that are being read from, and written to disk (secondary memory.) When you do any sort of modification to the tree, the tree must always end up balanced, which is what makes deletion from the tree really nasty. It's the logic, it really is!

[jemfinch]

When my computer comes back from the dead, I think I'll implement these in SML to see what the code looks like.

It seems to me, though, that the difficulty of making it handle binary files and whatnot can be abstracted out. I'll probably write a module that handles the logic that's functorized (specialized, much like C++'s templates) by the code that actually handles the in-memory or on-disk representation. The logic code doesn't need to know how to get the nodes, for instance -- it just needs a module that has a function to call to get the next node. I'd like to see how such an implementation would work.

Can you give me a few more details on your assignment?

Jeremy