[[TOC]]
1. Table Indexes#
table index 是一份表属性的副本，主要用来加速。
table index 主要权衡两个方面的因素
- 维护的代价
- 加速的效果
2. B+ Tree#
B+ 树是一个自平衡的数据结构，查找插入等操作的事件复杂度通常在 $O (\log {n})$ ，并且这种数据结构针对比较大的数据块做了优化。
B+ 树是一个 M- 叉搜索树有以下的特征：
- 完美平衡（所有的叶子节点的层数都相同）
- 除了根节点外，左右节点的有
M/2-1 <= #keys <= M-1 - 所有有
k个 key 的节点都有k+1个非空子节点。
在 B+ 树中，叶子节点是存储最后我们需要的 key 的地方。因此我们如果要依据叶子节点去寻找最终的 val 的话，有以下两种方法。
- 将 val 存在的地方用一个指针记录下地址
- 直接存储在叶子节点中。
B-Tree VS. B+Tree#
B - 树和 B + 树最主要区别是，B - 树的 key 也存在于非叶子节点。因此 B - 树在利用存储空间上无疑相较于 B + 树更为优秀。
因此可能存在以下的一些问题。
- B - 树在遍历的时候不得不在各个节点中来回跳跃。而 B + 树则可以直接扫描。
- B - 树，在使用将 val 存储在节点中的方法可能会导致查询过慢。
可视化#
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
INSERT#
找到一个叶子节点进行插入。按照大小插入。
如果该节点有足够的空间容纳，那么则插入停止。如果没有足够的空间那么有以下两步操作。
- 将该节点以中间值对半分为两个节点。
- 将该中间值向上推给父节点。若没有父节点，则创造父节点。然后对父节点执行同样的操作。
DELETE#
找到叶子节点进行删除。
如果该叶子节点删除了该 key 之后至少有一半的容量，那么删除停止。
如果该叶子节点只有 M/2-1 个 key 了，那么有以下两种策略
- 尝试将隔壁节点的值拿过来。
- 如果尝试失败那么则尝试将两个节点合并。
Selection Conditions#
具有与树结构查询的优缺点。
Duplicate Keys#
有两种方式来解决重复的 keys
- 在所有的 key 后面加入 recorid ID 来确保每个 key 都是独一无二的。
- 使用一个可以溢出的节点来保存这些重复的信息。
Clustered Indexes#
表通常依照 primary key 进行索引。
不过有一些数据库采用聚集索引，会为表加上一个隐藏的 primary key。别的数据库通常无法使用这个索引
3. B+ Tree Design Choices#
Node Size#
通常是存储设备越慢，采用的 node size 越大。
- HDD: ~1MB
- SSD: ~10KB
- In-Memory: ~512B
Merge Threshold#
一些 DBMS 不会总是合并那些 half full 状态的节点。
因为，如果延迟合并操作的话，那么可能会减少重新平衡的开销。
维持一些比较小的节点并且周期性的重构树可能会更好。
Variable length Keys#
- 采用指针的方法，即在 B + 树中仅仅存储指向值的指针。
- 采用可变长的节点。
- 将所有的值强制以一个固定大小存储在 B+ 树中。
- 采用 map 的形式来进行存储
Intra-Node Search#
- Linear
- 线性的扫描节点
- 可以采用 SIMD 的技术增加扫描的数据量。
- Binary
采用二分法进行查找 - Interpolation
通过值，从而知道位置在哪。
4. Optimizations#
Prefix Compression#
通过提取出相同前缀的方式来进行压缩。
Deduplication#
在 index 不一定都是独一无二的所有的值中，可以通过将这些值合并为一个 key 。
Suffix Truncation#
这种方式是通过在节点中选出可以进行区分比较的小的前缀长度，从而达到查找的目的。
Pointer Swizzling#
将 B+ 树中的 page id 固定在 buffer pool 中，可以避免重复的读 disk 进而加快速度。然后将 page id 的指针替换为在 memory 中的真实的值，这样就可以绕过 buffer pool 的转换，进行直接访问。
Bulk Insert#
重建一个 b+ 树的方法最快的方法是从底层向上建树