| Can anybody point to some good references on designing indexes using binary trees with non-unique values? Here's the issue I'm trying to understand: if you build a binary tree of unique record values, that's easy. Each node in the tree points to its own parent, to a lesser-than node, and a greater-than node. Now, suppose you want to organize a bunch of records in a binary tree, but the key for each record isn't necessarily unique. For example, you might have a dozen Smith's and two dozen Browns. How do you arrange those records in a binary tree?
I briefly considered just changing the greater-than pointer to greater-than-or-equal-to, but then you have to cycle through every redundant value, which defeats the purpose of an index. What the usual algorithm for this situation?
-Miko |
