一、B+树和B树

b+树是一个自平衡树，当我们插入数据时，其会保证数据的有效性；b+树插入、删除和查询的算法复杂度为O(log n)。

介绍B+树和B树的概念以及查询、插入、删除操作：https://segmentfault.com/a/1190000020416577
为什么数据库中，B+树更加受欢迎：
1. https://zhuanlan.zhihu.com/p/422639017
2. https://www.zhihu.com/question/57466414

二、数据库索引

table indexes用于快速找到数据，每次insert或者select操作会自动更新索引。数据库索引技术中大量使用到b+树和b树。

聚簇索引（clustered indexes）

聚簇索引会对page中tuple的物理布局进行匹配排序（对磁盘上实际数据重新组织以按指定的一个或多个列的值排序，这里的值是主键的值）。

查询的情况

B+树可以进行复合查询，比如查询两个属性的值，一个值为A，一个值为B；而hash table不行。

对于查找key=（A，*）的情况，除了根据原有的查找方式查找外，还需要沿着叶子结点的链表做顺序遍历，直到找到不匹配的值才结束。

对于查找key=（*，B）的情况，先找到大致的范围（找到可能相符合的叶子结点），之后对每一个叶子结点中的key进行匹配。

B+树在数据库中的设计

1. Node Size

存储设备的速度越慢，节点尺寸越大。

HDD：～1MB
SSD：～10KB
In-Memory：~512B

最优的节点尺寸大小还依赖于具体的workload，对于叶子节点的扫描， DBMS使用的是耗时长的顺序扫描，通常情况下这更适合大小更大的节点，因为我们可以进行更多的顺序扫描；如果DBMS所进行的查找、遍历需要进行大量的随机I/O，我想要的是体积更小的节点。

2. Merge Threshold

因为B+树的插入和删除操作极有可能导致B+树越来越趋向于不平衡，在实战中我们不会立即合并半满的叶子节点（当然拆分是立即执行的），而是会在之后统一重新平衡整一棵树。

3. Variable Length Keys（如何处理可变长度的key）

方式一（pointers）：不将key本身存放在节点中，我们所保存的指向其的指针，当查找时访问指针所指向的地址进行匹配。
方式二（variable length nodes）：可变空间大小的节点，但这需要很小心的内存管理。
方式三（padding）：填充key使该key的长度等于该key类型的最大可能长度。
方式四（Key Map / Indirection）：微优化，避免不必要的磁盘访问。其将key的指针存放在key数组中，我们这里的指针实际上是两个在该叶子节点中对应的offset值（类似于之前学的slotted page），而不是指向其它任何page。在叶子节点的存储结构上来看，key的指针从节点的头开始排列，而key+values从节点的尾部开始排列。

Non-Unique indexes

Approach #1: Duplicate keys

在Key Map / Indirection的设计下，有多个相同的key对应各自的value。（有两种处理方式，一种是在key后面加上key所在的这个tuple的record id；一种是在原有的叶子节点下面添加一个新的节点，存储重复的key以及其对应的值，有点像hash table中的bucket链表）

Approach #2: Value Lists

在Key Map / Indirection的设计下，一个key对应一个value list。

Intra-Node search（节点内搜索）

Approach #1: Linear

线性查找

Approach #2: Binary

二分查找

Approach #3: Interpolation

根据已知key的分布做插值查找

Optimizations

Prefix Compression

前缀压缩，因为近似的key总会被放在一个叶子节点中，因此可以查提取相同的前缀进行压缩。

Suffix Truncation

后缀压缩，压缩原理与前缀压缩类似，做这种压缩在做搜索的时候可以避免一些不必要的比较。

Bulk Insert

首先拿到所有的key并进行排序，之后我们将其排列在叶子节点上，将它们正确填入到叶子节点中。之后我们只需要使用中间的key来填充中间节点并生成指针。

Pointer Swizzling

用page指针代替page id来做索引，这适用于被固定于内存中的page，这样的好处就是不需要再使用page id来访问buffer pool了，而可以直接使用指针访问该page对应的内存。

Partial Indexes（部分索引）

只关联部分字段的索引，使用这种索引进行查询时无法读取到没有被关联的字段（因为其相当于只读取buffer pool中的索引而不读取持久化的page）。

Covering Indexes（覆盖索引）

覆盖索引指的是响应查询需求结果所需的所有字段都能在索引本身找到。可以使用index include columns技术在索引中嵌入额外的列来支持索引查询，这个额外的列只存储在叶子节点中但是不是key的一部分。

Functional/Expression Indexes

使用这种索引可以不通过key的自身值进行查找，而是通过该key所衍生出的某些值来进行查找。

Trie Index

使用digit（数字，字符）来表示keys来一个个地检查前缀而不是比较整个key。它也被称为prefix tree或者digital search tree。它的所有操作的算法复杂度为O(k)，其中k是key的长度。

Radix Index

如果一个path上只有一个子节点，可以将该path上的不用于区分路径的节点进行合并。

more tree details in CMU 15-826：R-tree，Quad-Tree，KD-tree

Inverted Index（倒排索引）

more details in CMU 11-442

该索引存储词语和包含这些词语的属性之间的映射，其也被称为full-text search index或concordance。

该索引可以做一些在b+树无法进行的搜索：

phrase searches：包含某个词组
proximity searches：近似
wildcard searches：通配符搜索

Decision #1: what to save

这个索引至少要保存记录包含的词语
同时也可以保存词频，词语位置和其它元数据

Decision #2: when to update

使用辅助数据去更新，考虑使用定期更新、分批更新