Multi key balanced trees

I am looking for a data structures that is like an AVL tree but with multiple keys.

I want a balanced tree to prevent skewing average lookup time. I have a situation where a node can have multiple keys so I want to specify one of the keys for lookup and wildcard the other.

Before, thinking of making a composite key based on the other keys, I want to c开发者_JAVA百科heck out if there are other ways to do it.

Any papers, suggestions?

Thanks in advance

---

A kd tree is useful when the number of dimensions is <= 5 (around). As dimensions increase, it gets less efficient.

---

Update: Mostly a k-d tree or R-Tree should do the job.

Cheers