【CMU 15-445】07 树索引-I

Slides
Notes

1. 索引 Indexes

我们将重点介绍数据库中的数据结构——表索引。

表索引是表中列的子集的副本，其组织方式使DBMS能够比执行顺序扫描更快地找到元组。DBMS确保表和索引的内容始终同步。

DBMS的工作是找出用于执行查询的最佳索引。在每个数据库要创建的索引数量上存在权衡(索引使用存储并且需要维护)。

2. B+树

（计算机基础的经典数据结构，多路查找树）

B+树是一种自平衡的树数据结构，它保持数据的排序，并允许在O(log(N))中进行查找、顺序访问、插入和删除。它针对读/写大数据块的面向磁盘的DBMS进行了优化。

几乎每个支持顺序保持索引的现代DBMS都使用B+树。有一种特定的数据结构称为B-Tree，但人们也使用这个术语来泛指一类数据结构。现代B+树实现结合了其他B-Tree变体的功能，例如B^link-Tree中使用的同级指针。

形式上，B+树是具有以下属性的 M-Way 查找树：

• 它是完全平衡的(即，每个叶节点都在相同的深度)；
• 除根节点外的每个内部节点至少半满( M/2−1<= key 的个数 <= M−1)；
• 每个有 k 个 key 的内部节点都有 k+1 个非空子节点。

B+树中的每个节点都包含一个 key/value 对的数组：

• 每个节点的数组(几乎)都是按 key 排序的。
• 内部节点的 value 数组将包含指向其他节点的指针。
• 叶子节点 value 的两种方法：1）record IDs：指向 tuple 位置的指针；2）tuple 数据：存储在叶节点中的元组的实际内容。

2.1. 插入 Insertion

找到正确的叶子节点 L
按排序将新条目添加到 L 中：如果 L 有足够的空间，则操作完成；否则，将 L 分成两个节点 L 和 L2。重新均匀分配条目并复制 中间 keys。将指向 L2 的索引项插入 L 的父节点。
要拆分内部节点，请均匀重新分配条目，但 push up 中间 keys。

2.2. 删除 Deletion

找到正确的叶L
移除条目：如果 L 至少已半满，则操作完成。否则，你可以尝试重新分配，从兄弟姐妹那里借。如果重新分配失败，则合并同级。
如果发生合并，则必须删除父项中指向 L 的条目。

3. B+树设计策略

节点大小：

• B+树的最佳节点大小取决于磁盘速度。其想法是通过尽可能多的键/值对来分摊将节点从磁盘读入内存的成本。
• 磁盘越慢，理想的节点应越大（目的是减少磁盘I/O）。
• 与拥有更多单 key 查找相比，某些工作负载的扫描负担可能更重。

合并阈值：

• 某些DBMS在半满时并不总是合并。
• 延迟合并操作可能会减少重组的数量。
• 对于DBMS来说，让 underflows 发生，然后定期重建整个树以重新平衡它可能会更好。

可变长度键：

• 指针 Pointers：将键存储为指向元组属性的指针(很少使用)。
• 可变长度节点：B+树中每个节点的大小可能不同，但需要仔细的内存管理。这种做法也很少见。
• 键映射 Key Map：在节点中嵌入映射到key+value 列表的指针数组。这类似于前面讨论的slotted 页面。这是最常见的方法。

非唯一索引：

• 重复键：使用相同的叶子节点布局，但多次存储重复键。

• 值列表：每个键只存储一次，并维护唯一值的链接列表。
  节点内查找：

• 线性：从头到尾扫描节点中的 键/值 条目。当你找到你要找的 key 时，停下来。这不需要对键/值条目进行预排序。

• 二分：跳到中间 key，然后根据中间关键字小于还是大于搜索关键字向左/向右旋转。这需要对键/值条目进行预排序。

• 插值 Interpolation：根据节点中已知的 低/高 关键字值，近似计算搜索关键字的起始位置。然后从该位置执行线性扫描。这需要对键/值条目进行预排序。

4. B+树优化

前缀压缩 Prefix Compression:

• 同一叶节点中的排序关键字可能具有相同的前缀。
• 不是每次都存储整个key，而是提取公共前缀，只存储每个key的唯一后缀。

后缀截断 Suffix Truncation：

• 内部节点的 Key 只用于流量导向( direct traffic )，我们并不需要整个Key。
• 存储将探测正确路由到索引所需的最小前缀。

批量插入 Bulk Inserts:
提前拥有这批数据的所有 keys。

• 从头开始构建B+树的最快方法是首先对 key 进行排序，然后自下而上构建索引。
• 这比逐个插入要快，因为没有拆分或合并。

pointer swizzling：

• 遍历时需要去buffer pool管理器，让其将page id转换为指针，这样的开销太大
• 保存page id时⽤page指针来替换，写出到磁盘时再将page指针换成page id
• 指针重排是将基于名称或位置的引用转换为直接指针引用（内存地址）