Two-tier Index Structure
First tier
- System of n PEs
- Partitioning vector: n-1 values, n “pointers”
- Directs search to appropriate PE
- Cached in main memory
- Replicated in all PEs
Second tier
- One B+-tree per PE
- Independent indexes at each PE
- Need not have the same height