Basic Concepts

• Search Key: attribute to set of attributes used to look up records in a file
• An index file consists of records (called index entries) of the form
  • (search-key, pointer)
• Index files are typically much smaller than the original file
• Two basic kinds of indices:
  • Ordered indices: search keys are stored in sorted order
  • Hash indices: search keys are distributed uniformly across “buckets” using a “hash function”

Ordered Indices

• Clustering index (primary index): in a sequentially ordered file, the index whose search key specifies the sequential order of the file
  • The search key of a primary index is usually but not necessarily the primary key
• Secondary index (nonclustering index): an index whose search key specifies an order different from the sequential order of the file
• Secondary index → Dense index
• Sparse Index → clustering index

Hash Indices

• linear probe: (key, page id)
• chained hashing: (key, pointer)
• Cuckoo Hashing: (key, pointer), more than one hash function and table

Extendible Hashing

• 计算哈希值 h(k)；
• 取前 global_depth 位，定位到对应的目录项；
• 插入到对应 bucket；
• 若 bucket 满了：
  • 若 local_depth < global_depth：
    • 分裂该 bucket；
    • 将其中一半数据移动到新桶；
    • 更新目录中相应指针；
    • local_depth += 1
  • 若 local_depth == global_depth：
    • 目录扩展（global_depth + 1，目录容量×2）；
    • 然后再执行分裂。

Linear Hashing