Take the 2-minute tour ×

I'm investigating the possibility of putting together a custom storage scheme for my application. It's worth the effort of potentially reinventing the wheel, I think, because both performance and storage efficiency are a main objective and the data and operations on it are far simpler than everything provided by an RDBMS (no updates, no deletes, predefined set of queries).

I'm using just a small handful of web resources I've found about B-Trees and B+-Trees - Wikipedia, http://www.bluerwhite.org/btree/, http://slady.net/java/bt/view.php, http://www.brpreiss.com/books/opus6/html/page342.html (the last one is the most valuable).

Duplicate keys

The first problem I'm trying to solve is how to deal with duplicate keys - this tree will be acting as a DB index and for example there won't just be one 'thing' with 'color=red', so looking up 'red' in this tree should yield many results.

There are two solutions I have come up with so far. The first is simply having multiple entries in the tree for each of these. But when there are 100,000 or 1,000,000 'red' things in the tree.. is that very efficient for a tree structure? The second was to have just one entry for each key, but the 'payload' associated with each key points to a different block of data, which is a linked list pointing to all instances of items that are 'red'.

Is there a common / better option?

B+Tree nodes changing types

I wanted to check an assumption I'm making. Say you have a B+-Tree, height 2 - the external (leaf) nodes at level 2 hold 'actual data'. Then an insertion necessitates a split of a leaf node - the leaf node no longer holds 'actual data'. Am I right in thinking that in implementation terms because the data might be of a substantial size that you would instead store a kind of 'pointer' as the 'actual data' - so if a leaf node becomes a branch node, that pointer (of the same size) is instead updated to point to the new subtree?

By that I mean, internal and external nodes, they should be the same size really since external nodes might become internal ones, and shuffling data around isn't a good idea?

(Added the C# tag since I'm implementing this from scratch in C#.)

share|improve this question
Yes, and the implementations I have looked at so far have not been appropriate. There is another big advantage for the app if I can very specifically control the storage mechanism and partition data in a particular way. Thanks for the comment but I would rather discuss the data structures and associated issues in this case :) –  Kieren Johnstone Aug 3 '11 at 8:28
sorry if this may seem to be offtop. But usually reinventing a wheel ends badly (from my practise). What I am trying to say, is that you may underestimate the effort that you are about to take to implement and test the storage. Why have you chose C# instead of C/C++ (performance). Have you considered other data structures? Do you have testing facilities that will make sure you solution is stable, reliable, efficient and doesn't loose data? To me such effort counts in years for a dedicated team. –  oleksii Aug 3 '11 at 8:39
I know it's usually a bad idea, which is why I qualified it so fully in the question. The language is irrelevant, as a good algorithm will make massive difference vs a few milliseconds here are there in processing overhead from using a different language. This will be scaled out across multiple machines which would negate that anyway. Of course I have researched other data structures, and this is a part of my ongoing research. Yes, there is an extensive testing framework I have started to build. No, it will not take years or a dedicated team. Any more questions? –  Kieren Johnstone Aug 3 '11 at 8:43
You seem to have clear understanding of what you are about to do. Will be nice to see if anyone can answer this. :) –  oleksii Aug 3 '11 at 11:18
Here's some insight to whoever looks at 'NoSQL' and keeps voting it up - if you don't know the answer to the specific questions I am asking, don't assume I don't know what I am talking about, and suggest the only thing you can think of. Instead have 'good faith' and try to answer the actual question. This is not a meta-question, this is a question, and I would love some answers :) –  Kieren Johnstone Aug 3 '11 at 17:25

2 Answers 2

up vote 4 down vote accepted

Attempting to answer my own question.. I would welcome other answers too.

Duplicate Keys

The tree will store a reference to a list (memory) or linked-list (disk) of items with the given key, if duplicate entries for the same key is a possibility.

B+Tree nodes, changing types

In-memory, my nodes have an object reference, which can point to another node (in itself another valid B+Tree) in the case of an internal/branch node, or indeed data directly in the case of an external/leaf node. On disk, this would work in a very similar way: a 64-bit value for each 'link slot', as I have chosen to name them - either an offset in the file if pointing at a sub-node, or a block number if pointing to data directly (or the head of a linked-list in the case mentioned in the first part of the question).

share|improve this answer

Kieren, I'm sure you figured out by now that B+ trees grow by splitting upwards, so that a leaf node is always a leaf node, and internal nodes are always internal nodes. Eventually, you must split the root node, which turns that into two internals, and you define a new root. So to answer the second part of your question, you don't change node types.

Regarding the first part of your question, when you delete a data record from the DB, you will need to find all the keys that point to that particular record, and remove them. If you have to look through long linear lists to do that, deleting will be slow. I am assuming you are using a binary search within a node in order to quickly find the correct node element (key + pointer), so if you make that "node searching" mechanism include the ability to ask for a particular key + pointer combination, you can quickly find the correct key element to remove. In other words, make the data record pointer part of the search (only when searching for a particular data record's key). This does mean that the duplicate keys will be stored in the nodes in "data pointer" order, so as long as ordering of the duplicate keys is not important, this mechanism will work.

share|improve this answer

Your Answer


