B+树（死去的八股记忆开始胡乱攻击）。
- 索引（index）：由表中属性的子集组成的数据结构，其中排列可以是有序的，用于搜索定位到特定的元组。
- 过滤器（filer）：用于判断一个key是否存在于集合中，但无法具体指引其位置。例如布隆过滤器。
Overview
- 双向链表是B树和B+树较大的区别，对于范围查询，B+树到达叶子节点后顺序扫描即可取得结果，无需返回root；而B树必须从root多次查询。
- 对于点查，B树的扫描次数不稳定；B+树稳定在logn。
叶子节点
叶子节点内部结构示例：
叶子节点：Value
- 记录Record ID：记录对应Record的页号的偏移量，跳转到指向位置读取元组；（所谓二级索引）
- 记录原始元组：无需跳转，value即可以返回的原始值。
插入
- 找到对应的叶子节点；
- 按序插入数据条目；
- 如果叶子节点有足够的剩余空间，插入操作结束；
- 如果叶子节点没有足够的剩余空间，则将当前叶子节点中的所有key分散到当前节点和新节点中：
- 尽量保持平均分散，并保留排序后处于中间位置的key；
- 在上层节点中插入索引条目。
删除
- 找到对应的叶子节点；
- 移除给定数据条目；
- 如果删除后叶子节点的条目数量依然有half-full，删除操作结束；
- 如果删除后叶子节点的条目数量少于半数：
- 尝试向左右的邻居节点借一些条目数量，借完之后注意上层索引的更新；
- 如果失败，则将叶子节点和其中之一邻居节点进行merge
例如我们删除节点6，导致叶子节点仅包含5一个元素：
因此向邻居节点借来一个9作为填充，由于9是原所在叶子节点的前导位，和上层节点的索引有关，因此需要同步更新上层节点：
- 如果merge发生，那么必须删除叶子节点上层节点相应的索引条目。
（proj2实现的时候可以进一步详细讨论）
Composite Index
联合索引：key包含了两个及以上的属性，例如index on (a, b, c)
当建立联合索引后，支持按部分属性的查找（但必须按照索引联合的顺序，例如a、ab、abc，不支持bc），这点和哈希表构建的索引不同，哈希表必须获取全量key的哈希值，从而映射到相应的位置。
Duplicate Keys
当key可能出现重复值：
- 在key之后追加record id，确保唯一性；
- 允许叶节点，将重复key的record都写入溢出节点：本方法除了增加了管理复杂度，还扰乱了叶子节点和溢出节点之间的有序性。
Design Choices
Node Size
node size取决于设备硬件，当硬件读取速度越慢时，我们希望节点的大小越大，这样可以尽可能最大化顺序访问。
Merge Threshold
适当放宽merge的阈值（前述讲述中，要求节点保持half-full状态），允许系统某一时间段存在一些较小的节点可能会更好，当新的插入进入则对其进行填充，删除至空时直接丢弃，可能会降低一些merge的成本，稍微在平衡性上做出让步。
Variable-length Keys
变长字段处理：
- 指针：存储指向元组属性的指针（加剧随机访问？）
- 变长节点：每个节点大小可变，但对内存管理的要求更高；
- padding：总是将每个key的大小padding到预规定的最大值；
- key map / indirection：在节点内部嵌入一个指针的数组，其中存储指向key-value对的指针（类似之前讲过的槽位数组）。
Intra-Node Search
- 线性搜索：利用SIMD优化；
- 二分查找：因为叶子节点内部数据有序；
- 插值搜索：基于key的分布情况估计期望key的位置。（少用）
Prefix Compression
分布在同一个节点中的有序序列趋向于具备相同的前缀，因此可以将前缀单独提取，存储有区分的部分。
Deduplication
Suffix Truncation
后缀阶段：对于独一无二的字符串，若字符串前几位足以进行区分，则可以对后缀进行截断，无序完整存储。
Pointer Swizzling
指针交换。
B+树中，节点以页为单位存储在磁盘上，每个页具备独立id。当一个节点引用另一个节点时，通常不会存内存地址，而是存节点对应页的id，因为页面ID是唯一且不变的，但其载入的内存地址可能会发生变化。
那么，处于非叶子节点上，向下查找的实际流程：找到下层节点页ID、查page table、找到对应的frame、得到内存地址、访问内存地址上的子节点实际内容。过程中存在页表查询的开销。
而优化思路就是：假如一个页面在buffer pool中被pin住了，即不会被驱逐，那么将具备稳定的内存地址，此时可以直接存储内存指针而非页号。
性能收益：
- 减少一次页表查询；
- 避免了查询page_table可能导致的latch争用；
- 在高频查询可能受益。
需要注意的是，页面刷盘时需要及时更新节点存储状态。
Bulk Insert
批量插入：对于一个已知、存在许多key的table，构建索引最快的方式是先排序，自底向上构建。
Optimizations
Write-Optimization B+Tree
前述介绍插入、删除操作时，已经指出可能引发B+树的合并和拆分操作，这将带来较大的维护和管理上的困难。
类似log-structured tree，可以优化的地方在于：
- 将更新操作存储；
- 必要的时刻批量应用这些更新；
- 写日志从根节点开始，log写满之后将部分日志下推；
- 日志下推到叶子节点后触发真正的插入/删除。
