索引和访问方法

索引和访问方法是辅助数据结构——主要是B+树和哈希索引——它们允许数据库在不扫描整个表的情况下定位匹配的元组，提供了优化器所依赖的快速访问路径。

Definition

索引是关系的一个或多个属性上的辅助数据结构，它将键值映射到匹配元组的位置，从而实现亚线性于表大小的时间检索；访问方法是查询读取数据的机制，例如全表扫描或索引扫描。

Scope

本主题涵盖了数据访问路径背后的结构和概念：聚集索引和非聚集索引、主索引和辅助索引之间的区别；作为支持等值和范围搜索的主力有序索引的B+树；用于等值搜索的基于哈希的索引；以及索引在选择、连接和排序避免中的作用。它讨论了索引选择如何影响查询成本和更新开销。它不包括基于成本的优化器的整体计划选择，这是一个单独的主题。

Core questions

• B+树如何有效地支持等值查询和范围查询？
• 聚集索引和非聚集索引、主索引和辅助索引之间有什么区别？
• 什么时候哈希索引优于树索引？
• 索引如何加速选择、连接和有序检索？
• 在插入、更新和删除操作下维护索引的成本是多少？

Key concepts

• B+树索引
• 哈希索引
• 聚集索引与非聚集索引
• 主索引和辅助索引
• 稠密索引和稀疏索引
• 范围搜索和等值搜索
• 可扩展哈希和线性哈希
• 索引维护成本

Key theories

B+树索引

B+树是一种平衡的、高扇出的搜索树，它以排序顺序存储键，所有数据引用都在叶子中；它支持等值和范围查询以及有序扫描，I/O呈对数级，并在插入和删除操作下保持平衡。

聚集索引与非聚集索引

聚集索引根据索引键物理排序表的行，使得范围扫描非常高效，而非聚集（辅助）索引指向一个无序文件，因此检索许多匹配行可能每行需要一次I/O。

哈希索引

基于哈希的索引将键映射到桶，以实现预期的常数时间等值查找，但不支持范围查询；可扩展哈希和线性哈希等动态方案使其能够随着数据的增长而平稳扩展。

Clinical relevance

索引是数据库性能最常见的实用杠杆：选择正确的索引可以将全表扫描转换为事务和分析查询的毫秒级查找，而过度索引会减慢更新速度，因此索引设计是操作实际系统中的一个反复出现的决策。

History

Bayer和McCreight于1972年引入了B树，用于维护磁盘上的大型有序索引；B+树变体将所有数据保存在叶子中，成为标准的数据库索引，正如Comer在1979年的《无处不在的B树》中所述。基于哈希的访问方法和动态哈希方案并行发展，这两个家族仍然是每个关系型引擎的核心。

Key figures

• Rudolf Bayer
• Edward McCreight
• Douglas Comer

Seminal works

• bayer1972
• comer1979
• ramakrishnan2003

Frequently asked questions

为什么数据库中使用B+树而不是二叉搜索树？

数据库将数据存储在磁盘上，成本主要由页面读取次数决定。B+树具有高扇出，因此每个节点都填充一个磁盘页面，并且树非常浅，只需几次I/O即可到达任何记录。二叉树会深得多，并导致更多的磁盘访问。

什么时候应该使用哈希索引而不是B+树？

当您只需要等值查找（例如，查找具有给定ID的行）并希望获得预期的常数时间访问时，请使用哈希索引。当您还需要范围查询、有序扫描或前缀匹配时，请使用B+树，因为哈希索引不保留键顺序，无法有效地回答范围条件。