Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

So I've created (and I'm sure someone else has come up with this before - I'm not claiming to have invented it) a data structure which consists of a binary search tree, only instead of each node having a single left and right child, they have two Map<string, Node> for the left and right, and the parent has a similar Map<string, Node> for the roots. When you create the tree, you give it a list of strings, which are the names of fields on the object you are storing on the tree. It creates one empty root for each name. When you insert an object, it is placed in each of the trees and sorted based on the data in that field. (The language in this case is C#, but it could be done in any OOP language. Storage should be by reference, so each object exists only once, but is referenced in multiple trees) So if I had an object like so:

class myObject
    Map<string, object> attributes;

And the map has one object (which must implement IComparable) for every string in the list of keys the tree uses. The benefit is that I can now choose a string as my sort-key, and quickly traverse through my tree in sorted order based on any of the sortable attributes. Likewise, I can perform a search on the tree based on any of the sortable attributes in O(log n) time. (A standard BST would allow this only on the single sort-key.)

I've called mine a MultiTree, but I looked it up and that has another meaning which seems to be entirely unrelated. But I can't come up with a better name for it. Does this structure have an established name already?

share|improve this question

closed as primarily opinion-based by durron597, MichaelT, Snowman, GlenH7, Bart van Ingen Schenau Aug 14 at 8:20

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question.

So it's basically just multiple BST's, correct? One for each field definition. –  Robert Harvey Jul 20 '13 at 2:10
Internally, yes. But from the user's side, they'd see it as just a single structure. Create once, insert each item once, and then you can iterate or search just like a single BST, only you have to provide a key. (Or not - it actually defaults to the first key in the list if you don't, but that's trivial.) Plus the items it stores must have a given structure so that it can search for named keys, but I'd already built that. –  Darrel Hoffman Jul 20 '13 at 2:52

1 Answer 1

The Boost library for C++ provides a data structure it calls multi_index_container which offers iteration and queries based on several keys.

The name kind of works, as it's a set with multiple indexes, each accelerating a different kind of query. This is not too different from the typical RDBMS table which also has indexes to improve query and iteration cost for different columns and queries.

share|improve this answer
-1 this really didn't answer the question of "What is a known name for this data structure (provided it's a known structure)", you just provided an alternative structure he could use instead... –  Jimmy Hoffa Jul 20 '13 at 1:24
@JimmyHoffa Which I can't even use because Boost is C++ and I'm using C#. Mind you, C# does have this kind of thing via Linq expressions, but I'm mainly creating a library here for self-improvement and practice, even though I know that better implementations exist already. However, it is helpful to know what name other libraries have used for this structure. –  Darrel Hoffman Jul 20 '13 at 1:35
The intent was never to recommend another structure. It was evidence to an existing name for a similar concept. –  Lars Viklund Jul 20 '13 at 1:57
I have to side with Lars on this one. He pointed to another data structure with a given name, and demonstrated its similarity by describing how it works. In other words, he didn't just say "Oh, it's called ______", he cited proof. Anyway, I doubt you're going to get any closer than this. –  Robert Harvey Jul 20 '13 at 2:07
+1 as the first thing I imagined up was "multi-index tree" while reading the OP's question, so this makes perfect sense as a suggestion. –  Izkata Jul 20 '13 at 2:22

Not the answer you're looking for? Browse other questions tagged or ask your own question.