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 on has keys that have 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
    • Each block containes 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
    • → 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