Sequential Index §
- Can be dense or sparse
- Primary Index: Key indices are often sparse, because the rows are ordered using the key index
- Secondary Index: Index on other attributes are often dense b/c/ v.v.
- You can manually create indexes in SQL:
{postgresql}CREATE INDEX indexname ON tablename(columnname)
- Multi-column index: Index (A,B) on R(A,B,C) has keys that have A,B concatenated and sorted together.
Index Sequential Access Method (ISAM) §
- Lookup:
- Insert / Delete:
B+ Trees §
- Architectural Improvement on ISAM
- Each block can fan-out a specific amount n
- Each block containes n−1 entries to indicate ranges
- Example:
- Leaves are sequential → Range queries are possible:
- Guaranteed to be well-balanced (=all nodes are at least half-full)
- Guaranteed by recursive node splitting (on insert) and recursive node coalescing or entry stealing (on delete)
- Example:
- Performance: access time is O(height)=O(logfanout#Tuples)
- → You can fit this in memory (4-level B+ Trees are often good enough)
- …recall you also need to node-split of node-coalesce sometimes too