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+ 树的方法最快的方法是从底层向上建树