Multiple-Key Index

This is a very simple conventional Multi-Dimensional Index Structure


The main idea is a nested index:

  • the index on indexes
  • index could be anything: B-Tree or Hash-Based one-dimensional index


  • in this case we have a tree
  • nodes at each level of this tree are also indexes
  • so for this example we have an index on the first attribute that points to an index on 2nd attribute



Types of Queries

  • partial match queries
    • easy if first attribute is specified
    • otherwise must look through every subindex
  • range queries
    • easy - provided individual indexes support range queries