索引与哈希

在数据库系统的实际运维与设计过程中，数据集规模常常达到百万甚至千万级别。如果对这样的数据表执行诸如“筛选居住地为北京且年龄为25岁的用户”或“查询订单金额大于5000元的交易记录”之类的操作时采用全表扫描（即逐行读取匹配），其性能开销极大且不可接受。 这类似于在厚重的专业词典中查找某个词汇，如果没有条目索引只能顺序翻页，效率极低。为优化此类访问，数据库系统引入了索引机制以加速数据检索。

索引本质上是一类辅助数据结构，存储在主数据之外，通过维护键值到物理存储位置（如行号、指针或块地址）的映射，极大减少了查询所需的磁盘I/O操作和CPU扫描时间。 因此，我们将系统性探讨数据库索引与哈希两大技术体系，分析其数据组织形式与工程实践中的性能优势。

索引的基本原理

以图书电商平台为例，设有一张包含数十万条图书记录的“图书”表。当需要检索“作者为张三的所有图书”时，若没有索引，必须对每一条记录读取并逐条比对（全表扫描），这一算法的复杂度为$O(n)$，难以满足高并发大数据量环境的性能要求。

数据库索引构建了“键-位置”映射表，可快速（如$O(\log n)$或$O(1)$）定位到目标数据位置。当我们以“作者”为搜索条件进行查询时，系统直接访问索引结构，获取相关数据块或记录位置指针，实现磁盘I/O次数的数量级减少。

索引的设计体现“以空间换时间”，即通过额外存储开销获得显著的查询性能提升。合理的索引设计可使特定查询的响应时间从秒级甚至更高缩短至毫秒级，实现高效数据服务能力。

索引的类型

数据库索引主要包括两类：有序索引（Ordered Index）和哈希索引（Hashed Index）。

• 有序索引：基于索引键的有序排列（如升序或降序），典型实现为B+树等数据结构。其优势在于高效支持范围查询，例如筛选某个取值区间的数据记录。当数据有序存储时，能利用树型结构进行高效的区间定位和顺序访问。
• 哈希索引：利用哈希函数将索引键映射为哈希桶（bucket）或物理位置，典型实现如哈希表（Hash Table）。哈希索引对于等值查询（exact match）操作性能极高（理论复杂度$O(1)$），但不适用于范围型检索。哈希索引常见于实现主键、唯一键的快速查找。

索引设计的评估指标

有序索引的组织方式

在讨论有序索引（Ordered Index）时，需首先明确索引项（Index Entry）的基本结构。每个索引项通常由“搜索键值”（Search Key Value）和指向对应物理记录的指针组成。该指针一般细化为磁盘块（Block/Page）的地址与块内偏移（Offset），以实现对于具体数据记录的精确定位。

以典型的“员工”表为例，假设表数据按员工ID（EmployeeID）递增顺序物理存储于磁盘。当在EmployeeID字段上建立索引，且表的物理记录顺序与索引序一致时，该索引被定义为聚集索引（Clustered Index，亦称主索引）。聚集索引的核心特性在于索引项排列顺序与底层数据存储顺序完全一致，因此支持高效的范围查询和顺序遍历。由于磁盘上相邻的索引项与数据记录空间局部性高度相关，能够最大化顺序I/O的利用。

反之，如在“部门”（Department）字段上创建索引，而表实际以EmployeeID排序存储，此时该索引即为非聚集索引（Non-Clustered Index，或称二级索引Secondary Index）。非聚集索引中的索引项顺序与底层数据存储顺序不一致，导致基于该索引的查询在数据检索过程中更频繁地触发随机磁盘读取（Random I/O）。

下述将用一个具体例子加以说明。考虑一张以学号（StudentID）递增排序的学生表：

若在学号（StudentID）字段上建立索引，由于数据文件本身已按学号有序存储，该索引为聚集索引（Clustered Index），其索引项顺序与底层数据物理排列完全一致，实现高效的顺序与范围检索。相反，若在“专业”字段（Major）上构建索引，由于同一专业的记录在物理存储上位置分散，二级索引项仅能通过包含指向数据记录的引用（如主键或物理地址）间接定位数据，此为典型的非聚集索引（Non-Clustered Index）。

密集索引与稀疏索引

有序索引根据索引覆盖数据记录的粒度，可分为密集索引（Dense Index）和稀疏索引（Sparse Index）。

密集索引（Dense Index）为数据表中的每一个搜索键值都维护一条索引项。对于聚集密集索引，每个索引项包含搜索键值以及指向该键值首条对应数据记录的指针，其余具有相同键值的记录在物理存储上紧邻分布。对于非聚集密集索引，由于底层数据按照不同属性排序，具有相同键值的记录位置可能随机分布，因此密集索引需要为表中每条物理记录维护一条索引项，实现逐条精确定位。密集索引能够支持高效的等值与范围检索，但索引规模通常与数据量线性相关，维护代价较高。

稀疏索引（Sparse Index）仅为数据文件中的部分搜索键值生成索引项，通常一个索引项对应一组物理上连续存储且键值有序的数据记录。稀疏索引本质要求底层数据按照搜索键全局有序排列（即只能应用于聚集索引场景），这样才能保证通过某个稀疏索引项定位后，顺序扫描能在较小代价下枚举所有目标记录。稀疏索引结构大幅减小了索引项数量与存储空间，在插入或删除大量记录场景下维护负担更轻，但单次检索可能需要额外的顺序扫描开销。

例如，考虑一张按订单日期升序存储、共含10000条记录的订单表：

使用密集索引查找2024-01-01的订单时，我们可以直接通过索引找到所有相关记录。而使用稀疏索引时，如果要查找2024-01-03的订单，我们需要先找到索引中小于等于这个日期的最大值（比如2024-01-01），然后从对应位置开始顺序扫描，直到找到目标记录。

密集索引的优势是查找速度快，但需要更多的存储空间和更高的维护成本。稀疏索引虽然查找时可能需要扫描一些额外的记录，但它占用空间小，插入删除操作的开销也更低。

一个常用的折中方案是为每个磁盘块建立一个索引项。由于从磁盘读取一个块的时间占据了大部分查询时间，读入块后在内存中扫描整个块的耗时几乎可以忽略不计。这种设计既保持了索引的精简，又能将磁盘访问次数降到最低。

多层索引结构

随着数据量的显著增加，索引结构本身的规模也会迅速膨胀，导致存储和访问效率问题。例如，若某用户表包含1,000万条记录，每条索引项占用100字节，则密集索引总体积将达到约1GB。在典型的内存配置下，整个索引文件难以完全驻留主存，每次访问索引可能涉及频繁的磁盘I/O操作，极大制约了查询性能。

举例而言，若索引文件被划分为10,000个磁盘块，且无法完整缓存在内存，则采用二分查找定位某一索引项时，理论上需访问log₂(10,000) ≈ 14个块。假设每次磁盘块读取耗时10毫秒，则单次索引查找的I/O延迟可高达140毫秒，这对于高吞吐需求的数据库系统是远不能接受的。

为应对此类性能瓶颈，数据库系统普遍采用分层索引（Multi-Level Index）机制，即在基础索引（一级索引）文件基础之上，额外构建更高层级的稀疏索引。底层索引可视作有序文件，上层索引则以稀疏采样的方式，为下层索引文件中一组有序项建立目录，其自身同样有序。该过程可以多级递归，每一级均可进一步构建索引，以对抗索引文件增长导致的随机I/O开销。

具体数值分析如下：假设一级索引覆盖10,000个块，实施二级稀疏索引，每个上层索引块可覆盖100个下层块，则二级索引规模仅需100个块。若二级索引可以完整载入内存，则任意一次数据查找只需在内存中定位对应的下层块索引，再执行一次磁盘读取即可，大幅降低I/O次数，相较于原先最多需读14个块的开销，实现数量级的查找性能提升。

即使是外层索引也可能太大而无法完全放入内存。比如对于一亿条记录的表，内层索引可能有100万个块，外层索引就需要1万个块，这仍然超出了典型的内存容量。此时我们可以继续添加第三层索引，如此反复，直到最顶层的索引足够小可以放入内存。

这种多层索引结构与树形结构密切相关，实际上就是树结构在磁盘存储中的应用。每向上一层，索引的大小就大约缩小到原来的1/N（N是每个块能容纳的指针数）。这使得即使是极大的数据集，索引的层数也能保持在很小的范围内。

索引的维护操作

索引作为数据库中提升查询效率的关键数据结构，其维护工作必须随着底层数据的增删而同步、准确。数据记录的搜索键值发生变更时，系统通常采用“先删后插”的方式更新索引——即先移除旧键值对应的索引项，再插入新键值对应的索引项。因此，索引维护的核心操作可归结为插入与删除。

插入操作的处理流程

插入新记录时，首先需基于搜索键定位其在索引中的目标区间，不同类型的索引具有各自的更新机制：

• 对于密集索引（Dense Index），若新搜索键值尚未出现在索引中，则应按序插入新的索引项。若该键值已存在，则依赖索引设计细节：如索引项维护的是同键值记录的指针集合，应向集合中补充指向新记录的指针；若仅存储首条记录指针，则只要新记录插入在相同键值区块之后，无需调整索引。
• 对于稀疏索引（Sparse Index），插入逻辑更为高效。常规做法是每个数据块仅对应一个索引项。仅当插入新记录引发新数据块的生成时，才需将该块首条记录的键值添加至索引。若新记录恰好成为某已存在块的第一条记录（即最小键值），则应更新该块在稀疏索引中的指示项，使其反映新的起始键值。

以下以按商品ID排序的数据表及其稀疏索引为例说明：

以稀疏索引为例，假设原有索引项为“1001 → 块A”、“2001 → 块B”、“3001 → 块C”。若插入ID为1500的数据记录，该记录属于块A，但由于其并非块A的首条记录，因此索引结构无需做任何变更。若插入ID为500的商品，其成为块A内新的首条记录，此时索引需将原“1001 → 块A”项更新为“500 → 块A”，以准确反映块的起始键值。

删除操作的处理

记录删除时，首先精确定位并移除目标记录，随后依据索引类型进行相应的维护和同步：

• 对于密集索引（Dense Index），若被删除的记录为其搜索键值对应的唯一记录，需要直接从索引中删除对应项；若存在多个同键值记录且索引维护的是指针集合，则仅移除相应指针；若索引项仅指向该键值的首条记录且该记录被删除，则需将指针更新至后继同键值记录。
• 对稀疏索引（Sparse Index），删除处理需分情形而定。若删除记录的键值未在索引项中出现，则无需任何操作。若索引项存在对应键值且该记录为该块的唯一入口，则应将索引项替换为下一个最小键值，或在下一个键值已有索引项时直接移除当前项。若被删除的记录正好为索引项指向的记录，则应将索引项更新为块中下一条记录的键值及指针。

多层（分级）索引的维护遵循递归策略。即，底层索引变动后，上层索引据同样维护规则递推更新，直至各层结构保持一致性与正确性, 以实现索引结构的动态自适应调整。

二级索引的特点

前面我们主要聚焦于聚集索引，现在我们来了解一下二级索引（Secondary Index）的技术特点。二级索引属于典型的密集索引（Dense Index），即每个搜索键值均需生成对应的索引项，并且索引需维护到文件中每条记录的指针（或位置引用）。

二级索引不能采用稀疏索引（Sparse Index）模式，原因在于数据在物理文件中的分布方式差异。聚集索引下，相同键值的数据记录在存储上是连续排列的，仅需索引指向每组的首条记录即可实现高效范围访问。 而在二级索引的场景，数据文件始终依据主键（聚集索引键）排序，导致相同的二级键值对应的记录在物理位置上呈现离散分布，因此必须为所有匹配的记录分别建立指针，否则无法保证检索的完整性和高效性。

举例来说，假设订单表按照“订单号”排序存储，如在“用户ID”字段上建立二级索引，则同一用户的订单记录可能分布于文件的不同位置。此时，二级索引需为每一条属于该用户的订单单独维护指针，而非仅指向第一条出现的位置。

为了提升大数量级重复值场景下的存储与访问效率，二级索引常采用“指针桶”（Pointer Bucket）设计。具体而言，索引项包含键值及对一个“桶”的指针，桶结构中集中保存该键值对应的全部实际记录指针列表。此策略兼顾了存储空间优化与检索性能，尤为适用于重复值较多的属性索引。

使用聚集索引顺序扫描数据非常高效，因为磁盘上的物理顺序与索引顺序一致，可以充分利用顺序读取的优势。但按二级索引顺序扫描就没那么高效了，因为每读取一条记录都可能需要访问不同的磁盘块，导致大量的随机I/O操作。这也是为什么在设计表结构时，需要仔细选择哪个字段作为聚集索引键的原因。

复合搜索键索引

在前述内容中，我们主要讨论了基于单一属性的索引设计。然而，在实际业务系统中，往往需要针对多个属性的组合建立索引结构，以支撑更复杂的复合条件查询。例如，电商平台通常需高效检索“特定分类下价格位于某一区间的商品”，此时应在（类别，价格）这一复合搜索键（Composite Search Key）上建立索引。

复合搜索键的索引项为属性元组。例如（"电子产品", 3000），所有索引项按照字典序（Lexicographical Order）排序，其排序规则为：先比较首属性，若相同则递进比较后续属性。因此，元组（"电子产品", 2000）排列在（"电子产品", 3000）之前，（"电子产品", 3000）排列在（"图书", 100）之前。

虚拟关键字排序带来的直接好处是，复合索引可以高效支撑多种查询模式：

• 对于全值精确匹配（如：WHERE 分类='电子产品' AND 价格=3000），可直接使用索引定位目标条目。
• 对于前缀范围查询（如：WHERE 分类='电子产品' AND 价格 < 5000），可先检索到（"电子产品", 0）的位置，再顺序遍历直至（"电子产品", 5000）。
• 即便仅依据索引的首属性（如：WHERE 分类='电子产品'），同样能够借助范围扫描实现高效检索。

需要注意的是，复合索引的适用范围也受到“最左前缀原则”限制：只有查询条件能够利用复合键的连续前缀属性时，索引优化效果才最佳。对于如“WHERE 分类 < '电子产品' AND 价格 < 5000”此类离散属性组合查询，虽然索引仍可被使用，但由于结果分布对应的物理位置分散，极易触发大量碎片化随机I/O，整体检索效率会明显下降。

哈希索引

有序索引在定位目标记录时尽管效率较高，但通常仍需通过多次键值比较完成定位。哈希索引则提供了一种截然不同的方案——利用哈希函数对搜索键进行计算，直接确定目标记录的存储位置，在理想情况下可实现 $O(1)$ 常数级的访问效率。

以专业数据库系统为例，哈希索引通过哈希函数 $h(K)$ 将搜索键 $K$ 映射到特定的存储桶（bucket）。这里，桶是逻辑概念，对应磁盘中的一个数据块，可容纳一条或多条记录。哈希索引的实现主要包括以下三种基本操作：

• 插入（Insert）：对待插入记录的键值 $K$ 计算 $h(K)$，将记录写入对应的桶；
• 查找（Search）：对目标键值 $K$ 计算 $h(K)$，直接定位到特定桶，在桶内查找所需记录；
• 删除（Delete）：通过哈希函数快速定位到目标桶，进而在桶内查找并删除目标记录。

以员工信息表为例，假设以员工ID为哈希索引键，并将所有记录分布到8个桶（编号0~7），可选择 $h(K) = K \bmod 8$ 作为哈希函数，则ID为12345的记录被映射到桶 $12345 \bmod 8 = 1$，ID为67890的记录被映射到桶 $67890<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi></mrow>$。查找和删除操作的基本流程同理，均依赖哈希映射直接定位数据。

需要注意的是，哈希方法可用于两种技术场景：一是哈希文件组织（Hash File Organization），直接通过哈希函数确定数据的物理存储块位置；二是哈希索引（Hash Index），即将原始文件的搜索键和指针项用哈希表结构组织，仅作为索引层辅助定位原始数据。 这两者在设计和实现上的侧重点不同，但核心思想均为：借助哈希函数，最大化简化和加速键值到存储位置的映射过程。

设计好的哈希函数

哈希函数的设计和选择在数据库哈希索引的性能中起到至关重要的作用。若哈希函数未能有效分布键值，极端情况下所有键被映射到同一桶内，则哈希索引整体退化为顺序扫描，其性能等同于线性查找。因此，理想的哈希函数需同时满足以下关键属性：

• 均匀性（Uniformity）：理想哈希函数应能够使所有输入键值在桶空间中“均匀”映射，避免数据倾斜。例如，设有 $B$ 个桶和 $N$ 个可能键值，理论上每个桶应平均分配 $\frac{N}{B}$ 个键。
• 不可预测性（Randomness）：实际应用场景下，键值分布往往具有一定规律。优质哈希函数应具有充分的分布“随机性”，使无论输入数据如何分布，各桶的负载均近似相等，从而防止特定桶产生异常高的碰撞概率。

例如，若以员工姓名首字母建立哈希索引，简单地将26个英文字母分别映射到26个桶，虽实现容易，但严重违反“均匀性”原则。原因在于姓氏分布极不均匀：如“王”“李”等姓在亚洲人口中极为集中，导致部分桶负载显著高于其他，否则如“欧阳”、“诸葛”等复姓则基本不会映射到大多数桶，这会导致哈希冲突频繁且命中不均。 再如按工资数值设桶，假定将￥3万~￥15万区间线性划分为10等分，不考虑实际工资分布，会因真实数据高度集中于某几个区段（如￥6万~￥8万）而产生负载失衡，桶间分布同样极为不均。

更优方案为采用“乘法累加”型哈希函数：

|
hash_value = 0
for each character c in string:
    hash_value = hash_value * 31 + ascii(c)
return hash_value mod bucket_count

这里选择31作为乘数不是随意的。31是一个质数，能够更好地分散哈希值；同时31 = 32 - 1，在二进制系统中可以通过位移和减法高效计算，性能更好。 对于数字类型的键值，除了简单的取模运算，还可以考虑更复杂的变换。例如，对于可能存在规律性的数字（如连续的ID），可以先进行一些位操作（如异或、位移）来打乱规律，再取模。

处理哈希冲突

即使哈希函数设计得很好，仍然不可避免地会出现不同键值映射到同一个桶的情况，这称为哈希冲突或桶溢出。 桶溢出的原因主要有两个：

1. 桶数量不足：如果总共有N条记录，每个桶能容纳F条记录，那么至少需要N/F个桶。如果桶数量少于这个值，必然会有桶溢出。
2. 数据倾斜：即使桶数量充足，由于哈希函数不够完美或数据分布不均，某些桶可能被分配了过多的记录。

为了降低溢出概率，实践中通常会分配比理论最小值多20%左右的桶。也就是说，如果理论上需要B个桶，实际分配1.2B个桶。这样虽然浪费了一些存储空间，但显著降低了溢出的可能性。 最常用的溢出处理方法是溢出链接。当一个桶满了但还有新记录需要插入时，系统会分配一个额外的溢出桶，通过指针将它链接到原始桶后面。如果溢出桶也满了，可以继续链接更多的溢出桶。

查找时，如果目标记录不在主桶中，系统需要沿着溢出链继续搜索，直到找到记录或到达链的末尾。这虽然增加了查找的时间复杂度，但在大多数桶没有溢出的情况下，性能仍然很好。 另一种处理冲突的方法是开放寻址，也称为开放哈希。在这种方法中，系统不使用溢出桶，而是在原有的桶集合中寻找空位。最简单的开放寻址策略是线性探测：如果h(K)对应的桶已满，就尝试h(K)+1、h(K)+2等位置，直到找到空桶。

不过，开放寻址在数据库系统中使用较少，主要原因是删除操作比较复杂。当删除一条记录后，不能简单地将其位置标记为空，因为这可能会中断其他记录的查找路径。

哈希索引的实现

哈希索引将搜索键值和相关指针组织成哈希结构。与文件哈希组织不同，哈希索引是一个独立的索引结构，指向存储在其他地方的数据记录。 还是用我们之前的员工数据库例子。假设我们在员工ID上建立哈希索引，使用h(ID) = ID mod 8的哈希函数。索引的结构可能是这样的：

每个索引项包含搜索键值和指向实际数据记录的指针。如果某个键值不是唯一的（比如按部门名称建立索引），一个索引项可能包含多个指针，指向所有具有相同键值的记录。

哈希索引特别适用于等值查询。要查找员工ID为12345的记录，我们计算12345 mod 8 = 1，直接访问桶1，在其中查找键值12345。如果没有冲突，这个过程只需要一次磁盘访问。

但哈希索引不适合范围查询。要查找ID在10000到20000之间的所有员工，我们无法通过哈希函数直接定位，因为这个范围内的ID可能散布在所有的桶中。此时只能扫描整个哈希表，效率反而比顺序扫描原文件还要低。

哈希结构的局限性

静态哈希（Static Hashing）方法存在本质性的局限性，即哈希函数及桶（bucket）的数量在初始化阶段即已确定，后续难以动态调整以适应数据库规模的变化。

当数据量快速增长时，预设的桶数量可能无法满足新增数据的需求，导致主桶后面挂接大量溢出桶（overflow bucket），加重了查找操作的I/O负担，严重影响系统性能。反之，若为了预防数据膨胀而过度分配桶，则在数据量未达到预期时造成资源浪费，空间利用率低下。

哈希函数的选取同样至关重要。系统上线后，如若发现哈希函数引发显著的数据倾斜问题（比如某些桶被大量数据占用，而其他桶利用率低），要修正哈希函数，必须对整个数据集重新计算哈希值并重排存储——这一重分布操作代价极高，且通常需要系统停机维护，业务影响较大。

基于上述问题，静态哈希仅适用于数据量相对稳定、增长可预测的应用场景。对于数据规模波动大、弹性要求高的数据库系统，则需采用能够动态扩展、自动调节结构的哈希机制，以保证性能和空间效率。

动态可扩展哈希

为克服静态哈希无法自适应数据量变化的结构性短板，数据库领域发展出了多种动态哈希方法，其中以可扩展哈希（Extendable Hashing）最具代表性。 该技术通过按需动态分配桶，并结合地址表重定向机制，能够实现哈希表容量的弹性扩展或缩减，有效提高空间利用率，并避免了全局重排带来的高昂开销，显著提升了系统适应大规模数据动态增长的能力。

可扩展哈希的基本机制

可扩展哈希的核心设计在于：并不为全部可能哈希值预配置存储桶，而是依据实际数据插入情况动态创建桶。同时，引入“桶地址表”（directory）作为中间层，实现哈希值与物理桶的灵活映射。这一级地址表支持实时扩容、缩容，并允许多个哈希前缀映射至同一个物理桶，实现存储结构的按需弹性调整。

系统通常选用位宽较大的哈希函数（如32位无符号整数），从而理论上产生2³²种可能哈希值。实际操作中，系统只取哈希值的前 i 位作为地址表索引（i为当前全局深度，动态可变），以此索引到桶地址表，进而访问对应桶。i的增长伴随数据量和分裂次数自动调节，而无需人为干预。 假定目前管理以下部门，各自已通过32位哈希算法获得哈希值（仅取高8位便于演示）：

刚开始时，我们可能只使用哈希值的前1位（i=1），这样只需要2个桶：以0开头的哈希值去桶0，以1开头的去桶1。

桶地址表的工作机制

可扩展哈希的关键组件是桶地址表。这个表的大小是2^i，其中i是当前使用的哈希位数。表中的每个条目都包含一个指向实际桶的指针。 重要的是，多个表条目可能指向同一个桶。每个桶都有一个本地深度值（通常记为ij），表示该桶实际需要多少位来区分其中的记录。而全局深度i表示当前桶地址表使用多少位进行索引。

举个例子，假设当前i=2（使用2位进行索引），桶地址表有4个条目：00、01、10、11。但实际上可能只有2个物理桶：

• 桶A的本地深度为1，对应哈希前缀00和01
• 桶B的本地深度为2，对应哈希前缀10和11

指向某个桶的地址表条目数量等于 $2^{i - i_j}$。在上面的例子中，桶A有 $2^{2-1}=2$ 个条目指向它，而桶B和桶C各有 $2^{2-2}=1$ 个条目指向它。

插入操作的处理

可扩展哈希的插入操作相比静态哈希更为复杂，其核心在于支持哈希表自适应动态扩展。插入时需综合判断桶的剩余空间、本地深度与全局深度关系，以保障结构的高效性和一致性。

情形一：目标桶未满（有空位）

此时直接执行插入操作。具体步骤为：根据待插入记录的哈希值，提取前i位作为桶地址表索引，定位对应桶，若桶空间充足即直接写入数据，无需进一步处理。

情形二：目标桶已满，且本地深度（ij）小于全局深度（i）

如目标桶已满但ij < i，表明该桶由多个地址表条目共同指向，可以局部分裂且无需扩展目录。分裂流程如下：

情形三：目标桶已满，且本地深度等于全局深度（ij = i）

当桶满且ij = i时，需先扩展地址表（即扩张目录），随后分裂桶。处理过程如下：

假设每个桶最大容纳2条记录，目录结构及数据分布如下所示：

假设我们需要插入“市场部”，其哈希值前2位为"01"，按目录映射应插入桶A。然而，当前桶A已达到容量上限，需执行桶分裂操作。由于桶A的本地深度$j=1$小于全局深度$i=2$，因此可以对该桶进行局部分裂：

查找和删除操作

查找操作在可扩展哈希中实现较为直接。针对给定的搜索键，系统首先对其计算哈希值，并提取前 $i$ 位作为目录（桶地址表）的索引，从而定位到目标桶。随后仅需在该桶内部进行线性或二分查找即可完成操作，整体查找路径高度可控，通常涉及一次目录访问和一次磁盘桶访问。

删除操作则相对复杂，涉及空间回收与结构收敛的判断。记录删除后，系统需检测是否存在满足合并条件的桶，以提升空间利用率并减少地址表冗余。桶合并的判定严格依赖于以下条件：

1. 两桶互为兄弟桶，即由同一次分裂事件产生。
2. 合并后的记录数量不超过单桶最大容量。
3. 两桶本地深度相同。

合并操作具体为：将两个兄弟桶的内容合并至单一桶，统一其本地深度（$j = j - 1$），并同步更新相应的目录指向。若合并后目录项存在冗余映射，理论上可进一步收缩全局深度及地址表容量，但在工业实现中，鉴于动态缩表成本较高且扩展需求常态存在，此步骤多采用延迟或惰性策略。

可扩展哈希的性能分析

可扩展哈希结构兼具理论与工程优势。查找操作的I/O复杂度常为常数级：一次地址表读取（通常驻留内存），加上一或两次桶访问即可，即始终处于$O(1)$阶。数据库规模的提升对查找性能影响极小，保证系统高吞吐。

插入操作在绝大多数情况下仅需一次新写。分裂事件仅局部触发，且只涉及相关目录条目和受影响的桶，与全表重构的静态哈希形成鲜明对比，从根本上提升了大规模动态环境下的写入表现。

空间利用率方面，可扩展哈希克服了静态哈希结构的空间浪费或溢出链冗余问题。目录空间开销一般远小于数据区，甚至在数十亿级记录规模下，地址表内存占用仍极为有限，对整体存储几乎无负担。

索引技术的选择与对比

在实际的数据库系统架构设计中，索引方式的选择（如有序索引B+树与哈希索引）对系统整体性能、扩展性和适应场景均有深远影响，所以我们需要从查询模式、性能表现、维护成本等多维度进行严谨权衡。

查询模式驱动的索引选择

精确匹配查询

针对以主键或唯一标识符为条件的等值查询（如 SELECT * FROM 用户表 WHERE 用户ID = 12345），哈希索引具备显著优势。理想情况下，哈希索引的查找复杂度为O(1)，几乎可以实现常数时间内完成定位。 而B+树等有序索引的查找复杂度为O(log N)。尽管对数时间复杂度增长缓慢，但在超大规模数据集（如10亿记录）下，前者仅需1-2次磁盘随机I/O，后者可能涉及4-5次树结构节点访问。此差异在IO密集型高并发应用中极具敏感性，直接影响数据库QPS（每秒查询数）上限。

范围与区间查询

涉及范围检索（如 SELECT * FROM 订单表 WHERE 下单日期 BETWEEN '2024-01-01' AND '2024-03-31'）时，有序索引如B+树结构显示出压倒性优势。B+树能够高效地找到区间起点，并通过叶子节点链表快速顺序扫描目标范围，且数据物理布局上的局部性有利于磁盘预读和高效缓存命中。 反观哈希索引，由于哈希函数将相邻键值均匀分布于不同桶，无法有效支持区间定位与顺序访问，只能退化为全表扫描，效率远逊于有序结构。

排序与分组

当查询包含ORDER BY或GROUP BY等操作时，有序索引可以利用其结构特性实现“流式有序读取”或高效聚合，无需额外排序或分组遍历。哈希索引则完全不具备天然有序性，往往需要配合外部排序或额外哈希结构，增加系统开销。

性能与工程维护角度

性能波动性与最优-最劣分析

有序索引（典型如B+树）的查找效率随树高对数增长，访问路径长度上界可提前分析并严格保证，即使极端情况下也具备良好的性能可控性。这对于高可靠性和延迟敏感型应用尤其重要。

哈希索引的“最优复杂度”理论上可达到O(1)查找，但其最坏情形下（大量哈希冲突导致溢出链或溢出桶）访问时间可退化为线性O(N)，远低于B+树性能下限。因此，哈希算法设计与负载因子的动态控制直接关系到系统最坏性能表现；在银行、金融等关键场景需格外谨慎。

维护与更新成本

结构维护同样有所差异。B+树的插入/删除操作需动态维护节点平衡和分裂/合并，复杂度受限于树高，最坏情形复杂度O(log N)且分布规律稳定。其系统长期运行下可保证性能不发生大幅波动。

哈希索引的插入与删除在负载适中时实现极简高效，适于高并发写场景。但一旦数据超出预设容量，特别对于静态哈希结构，扩容或重哈希会带来极高系统阻塞与I/O抖动，甚至需短暂锁表重构，不利于业务连续性。

因此，索引方案应根据数据特性和业务模式动态调整，实际工程中常需结合多种索引机制实现“精准查询高性能、范围检索有保障、维护代价可控”的系统最优解。

位图索引技术

位图索引（Bitmap Index）是一类针对低基数字段（取值范围有限、分布稠密字段）的高效索引机制。其在传统OLTP系统中应用有限，但在数据仓库、OLAP和高并发分析型场景中具有极高价值，尤其适用于大规模多维组合条件的高性能检索。

位图索引的基本概念

位图索引的核心思想是为每个可能的字段值创建一个位图（bit map），位图中的每一位对应数据表中的一条记录。如果某条记录在该字段上取这个值，对应的位就设为1，否则设为0。 让我们通过一个具体例子来理解。假设有一个客户表，包含以下记录：

在“性别”字段上建立位图索引：

在“城市”字段上建立位图索引：

位图索引的优势在于可以非常高效地处理多条件查询。要查找“北京的男性客户”，只需要将“城市=北京”的位图（10100）与“性别=男”的位图（10101）进行按位与操作：

|
北京: 10100
男性: 10101
结果: 10100

结果位图显示第0和第2条记录满足条件，对应张三和王五。

位图索引的高效执行机制

位图索引之所以具备卓越性能，本质依赖于位运算（Bitwise Operation）的并行处理能力。现代CPU通常支持32位、64位甚至更宽的数据宽度单元，能够在一条机器指令周期内对整个机器字进行并行位运算。例如，一次64位AND/OR/XOR操作可以瞬时处理64条记录对应的位。

以百万级数据规模举例，若有100万条记录，每个位图长度为100万位，约占用125KB内存。执行两个条件的位与（AND）操作，仅需进行约15625次（1000000÷64）的64位指令即可遍历全部记录。该过程在现代处理器上仅需几毫秒完成，相较于逐记录判定查找，效率提升数十甚至上百倍，对大规模多条件过滤尤为高效。

复杂多条件查询的优化

位图索引天然适配复杂布尔表达式的查询优化。对于任意组合的条件筛选，可通过多个位图间的位运算实现。例如，针对"（北京或上海）的（青年男性或中年女性）"等复合逻辑，仅需依次对相关位图执行OR、AND等运算，即可高效得出目标结果，无需逐条数据扫描。

|
北京: 10100
上海: 01001
OR:   11101  // 北京或上海
 
男性: 10101
青年: 10010
AND:  10000  // 青年男性
 
女性: 01010
中年: 01001
AND:  01000  // 中年女性
 
青年男性 OR 中年女性: 11000
 
最终结果: 11101 AND 11000 = 11000

位图索引的适用场景

与传统索引的结合

位图索引可以与传统B+树索引进行有机结合，以适配不同基数特性的查询需求。对于同时包含高基数字段与低基数字段的场景，通常采用混合索引策略：将高频或热点取值利用位图索引加速检索，低频或长尾取值则采用传统指针链或B+树索引管理。例如，在电商平台的商品价格索引设计中，针对“0-100元”“100-500元”等常见价格区间建立位图索引，而将特定价格值通过B+树索引维护，兼顾存储空间和查询效率。

位图压缩算法

在实际应用中，位图数据结构通常具有高度稀疏性（绝大多数位为0），因此广泛采用压缩算法以降低存储开销。最常见的做法是运行长度编码（Run-Length Encoding, RLE），即将连续的同值比特段表示为<值,长度>对。例如，对“0000011100000”进行RLE压缩后可表示为“0×5, 1×3, 0×5”。在高稀疏场景下，该方法可极大地压缩数据体积，节省90%以上的存储空间。 针对性能要求更高的场景，现代数据库还采用如字对齐混合（Word-Aligned Hybrid, WAH）等复杂压缩算法，在保障高压缩比的同时，支持对压缩数据直接进行高效的位运算操作。这些优化技术大大提升了位图索引在大数据分析与OLAP系统中的实用价值。

总体而言，位图索引虽存在适用范围限制，但在面向多维分析与大规模复杂查询场景时，具有不可替代的性能优势。伴随数据分析需求的持续增长，位图索引正在成为现代数据库系统中不可或缺的关键索引结构。

小结

索引和哈希技术是现代数据库系统的核心基础设施，它们让数据检索变得高效而灵活。从有序索引的密集与稀疏方案，到实现极速定位的哈希和可扩展哈希技术，以及在特定场景下效率极高的位图索引，各类索引机制各有优缺点，互为补充，构建起现代数据库系统完整而强大的索引生态。

在实际应用中，如何选择合适的索引策略，取决于对业务需求和数据特点的深入理解。随着数据规模的不断扩展和查询复杂度的提升，索引技术也在不断创新与优化。 在大数据和云计算时代，这些索引技术依然发挥着关键作用，为海量信息的快速管理和检索提供核心支撑。