Variable-Order Simple-Prefix B+ Tree

Bonus marks in university course. Database file systems. And it''s not something that we learned, otherwise it would have been mandatory.

In case you''re interested, the insane professor has asked us to make a very simple database server that would support addition/deletion of song records and searching for artists/albums/genres

The primary key index is kept in a B+ Tree and the secondary key indices are kept in separate hash tables.

We were able to make an incremental hashing scheme for our secondary keys (dynamic hashing). But we couldn''t figure out what a variable-order simple-prefix B+ Tree would be like, so we just stick to a normal B+ Tree


------------------------

Do you know about separators? Instead of storing every key in a relation in the B+ tree, you just find a key which is enough to distiguish between two blocks. Say you have two blocks like this (I only show the keys for brevity):

Block 1: Adam, Andrew, Anne, Beth
Block 2: Britany, Charles, David, Erin

In this case, the separator would be "Britany". If you''re searching for a key, the way you go is "Key < separator, go left", "key >= separator, go right".

Now, a simple-prefix B+ Tree stores the shortest possible separator that is enough to distinguish two blocks. In the example above, the shortest separator would be "Br".

As for variable-order, I believe that refers to the way the separators are stored in the blocks (since you store your B+ in a block structure as well, to facilitate large indices). Since the prefix B+ tree has variable-length keys (and in fact, most keys that are not integers are variable length), it''s difficult to store them efficiently in a fixed-size block structure. I''m not sure how the variable-order B+ tree helps, but I''m sure a search on google would turn up something.

Man, my database course only had me writing PHP applications! I envy you!

---

codeka.com - Just click it.