X. Indexing

Introduction

Primary Index v.s. Secondary Index

• 主索引(primary index)，聚簇索引(clustering index)：数据已排序的列的索引．

• 辅助索引(secondary index)，非聚簇索引(non-clustering index)：数据未排序的列的索引．

Dense Index v.s. Sparse Index

• 稠密索引(dense index)：索引了数据的所有搜索键．

  • 如果同一索引项有多个，只索引第一个，其余的通过 PageTable 逐个遍历可以得到．

• 稀疏索引(sparse index)：仅索引了数据的少量搜索键．

  • 稀疏索引必须建立在按搜索键排序的数据上即主索引的情况，或者说顺序文件中．

Multilevel Index

• 一种多级索引方法：将 主索引(primary index) 放在磁盘上，然后在它上面构建一个稀疏索引．

B+ Tree Index Files

TBD:?

• B+ 树(B+ tree)

  • 所有叶子结点的深度均相同．

  • 叶子结点的容量在 $\left\lceil {(n - 1)/2} \right\rceil$ 到 $n - 1$ 之间．

  • 根节点的容量在 $2$ 到 $n$ 之间（注意这里说的是指针的个数而不是存的键值的个数）．

  • 其余节点容量在 $\left\lceil {n/2} \right\rceil$ 到 $n$ 之间（注意这里说的是指针的个数而不是存的键值的个数）．

Insertion on B+ Tree

Algorithm: B+ 树插入

• 通过搜索操作进行定位，插入到对应位置．

• 如果此时叶节点满了，则将现在 $n$ 个中的前 $\left\lceil {n\text{ / }2} \right\rceil$ 个节点放在原位置，将剩下的 $n - \left\lceil {n\text{ / }2} \right\rceil$ 个节点放在新节点中，将新节点的键插入到原节点的父节点中．

• 如果此时非叶节点满了，则将第 $\left\lceil {(n + 1)\text{ / }2} \right\rceil$ 个键节点 push 给父节点，前 $\left\lceil {(n + 1)\text{ / }2} \right\rceil - 1$ 个键节点留在原节点，剩余节点放到新节点中，并递归处理满了的情况．

Problem: 历年卷 20-21 P5.2

Insert entry 14.

Answer

注意 15 这个键值会被丢上去．在非叶节点上每个键值最多出现一次，注意．

Deletion on B+ Tree

Algorithm: B+ 树删除

• 通过搜索定位到对应指针，将其删除．

• 如果存在节点容量小于要求（注意叶节点和非叶节点的要求略有不同的），则需要进行合并或迁移．

  • 如果能和兄弟节点合并，就直接合并放到左侧节点，将右侧节点在上方的键值删除．接下来如果不满足容量要求需要递归处理．

  • 如果不能的话，从左侧匀一个给右侧，然后将上方右侧节点原先的键值更新（精简版本：父节点 key 下移，兄弟节点 key 上移）．这时，可以退出递归．

注意：通过 B+ 树的删除操作后，索引节点中存在的 key，不一定在叶子结点中存在对应的记录．因为你更新的时候有可能在中途就退出了，没有一路更新上去，但是至少能保证搜索算法仍然是 work 的．

Log Structured Merge (LSM) Tree

• 核心思想：查询操作多一个小 $\log$（可能需要对每一层 B+ 树搜索），但是写入操作大大加快．

Buffer Tree

• 核心思想：B+ 树的每个节点都维护一个缓冲区，缓冲区慢时才将数据插入到下一等级．