3.3 更多的索引结构（阅读内容）
散列表
散列表的两个要素是散列函数和桶数组，相关知识在先修课程《数据结构》中做过讲解，这里不再赘述。散列表索引的桶数组存储在页式文件中。
静态散列表
桶的总数不变。i 号桶对应 i 号页，桶满后以链表的形式添加新页。
动态散列表
动态散列表可以根据记录总数调整桶的总数。其做出的改进如下：
-
增加了一个间接层，用一个指向页面的指针数组（桶地址表）而非页面数组来表示桶数组。
-
指针数组能动态增长，且数组长度总是2的幂，因此数组每增长一次，桶的数量就翻倍。
-
并非每个桶都单独拥有一个页面。如果多个桶的记录只需一个页面就能放下，那么这些桶可能共享一个页面，即多个桶指针指向同一个页面。
-
散列函数 h 为每个键计算出一个长度为N的二进制序列，但是在某一时刻，这个序列中只有前 i 位 (i≤N) 被使用，此时桶的数量为 2^i 个。
插入关键字为 K 的记录时，根据散列函数计算 h(K)，取出该二进制序列的前 i 位，并根据桶地址表找到桶数组中相对应的页面 j。如果页面已满，可能出现两种情况：
-
桶地址表中有多个表项指向该页面，此时不需要扩大桶地址表就能分裂页面。分配一个新的页面 n，调整桶地址表中原来指向页面 j 的表项，其中一半指向新创建的页面 n；重新散列页面j中的各条记录，将其分配到页面 j 或页面 n 中，并再次尝试插入新记录。如果插入失败，则需要继续进行页面分裂。
-
如果桶地址表中只有一个表项指向页面 j，此时分裂该页，需要使桶地址表的大小翻倍，以容纳由于分裂而产生的两个桶指针。桶地址表扩展后，原表中的每个表项都被两个表项替代，且这两个表项都包含和原始表项一样的指针，所以也应该有两个表项指向页面 j。此时，分配一个新的页面 n，并让第二个表项指向页面 n。将原页面j中的各条记录重新散列，根据前 i+1 位来确定该记录是放在页面 j 中还是页面 n 中，然后再次尝试插入新记录。如果插入失败，则需要继续进行页面分裂。
其它索引结构
数据库也会用到跳转表 (Skiplist)、布隆过滤 (Bloom filter) 等数据结构。最新的学习型索引的研究方向使用AI技术优化索引的设计。不过这些内容已经超出本课程范围。