# Tree Indexes

上节提到，DBMS 使用一些特定的数据结构来存储信息：

* Internal Meta-data
* Core Data Storage
* Temporary Data Structures
* Table Indexes

本节将介绍存储 table index 最常用的树形数据结构：B+ Tree，Skip Lists，Radix Tree

## Table Index

table index 为提供 DBMS 数据查询的快速索引，它本身存储着某表某列排序后的数据，并包含指向相应 tuple 的指针。DBMS 需要保证表信息与索引信息在逻辑上保持同步。用户可以在 DBMS 中为任意表建立多个索引，DBMS 负责选择最优的索引提升查询效率。但索引自身需要占用存储空间，因此在索引数量与索引存储、维护成本之间存在权衡。

## B+ Tree

### B-Tree Family

B-Tree 中的 B 指的是 Balanced，实际上 B-Tree Family 中的 Tree 都是 Balanced Tree。B-Tree 就是其中之一，以之为基础又衍生出了 $$B^+ \ Tree$$ 、 $$B^{link} \ Tree$$ 、 $$B^\* \ Tree$$ 等一系列数据结构。B-Tree 与 B+ Tree 最主要的区别就是 B+ Tree 的所有 key 都存储在 leaf nodes，而 B-Tree 的 key 会存在所有节点中。

### B+ Tree

B+ Tree 是一种自平衡树，它将数据有序地存储，且在 search、sequential access、insertions 以及 deletions 操作的复杂度上都满足 $$O(logn)$$ ，其中 sequential access 的最终复杂度还与所需数据总量有关。

B+ Tree 可以看作是 BST (Binary Search Tree) 的衍生结构，它的每个节点可以有多个 children，这特别契合 disk-oriented database 的数据存储方式，每个 page 存储一个节点，使得树的结构扁平化，减少获取索引给查询带来的 I/O 成本。其基本结构如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZz8wddPpPJxP1xxb5Y%2F-LZykS00HETGUoHxtn62%2FScreen%20Shot%202019-03-02%20at%2010.14.35%20PM.jpg?alt=media\&token=71549c13-7809-4929-bb1d-66f6c2fcba63)

以 M-way B+tree 为例，它的特点总结如下：

* 每个节点最多存储 M 个 key，有 M+1 个 children
* B+ Tree 是 perfectly balanced，即每个 leaf node 的深度都一样
* 除了 root 节点，所有其它节点中至少处于半满状态，即 $$M/2-1  \leq #keys \leq M-1$$ 
* 假设每个 inner node 中包含 k 个 keys，那么它必然有 k+1 个 children
* B+ Tree 的 leaf nodes 通过双向链表串联，从而为 sequential access 提供更搞笑的支持

#### B+ Tree Nodes

B+ Tree 中的每个 node 都包含一列按 key 排好序的 key/value pairs，key 就是 table index 对应的 column，value 的取值与 node 类型相关，在 inner nodes 和 leaf nodes 中存的内容不同。

leaf node 的 values 取值在不同数据库中、不同索引优先级中也不同，但总而言之，通常有两种做法：

* Record/Tuple Ids：存储指向最终 tuple 的指针
* Tuple Data：直接将 tuple data 存在 leaf node 中，但这种方式对于 [Secondary Indexes](https://docs.oracle.com/cd/E17275_01/html/programmer_reference/am_second.html) 不适用，因为 DBMS 只能将 tuple 数据存储到一个 index 中，否则数据的存储就会出现冗余，同时带来额外的维护成本。

此外，leaf node 还需要存储相邻 siblings 的地址以及其它一下元信息，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZz8wddPpPJxP1xxb5Y%2F-LZyqI1gxZLbynuj3rFr%2FScreen%20Shot%202019-03-02%20at%2010.40.07%20PM.jpg?alt=media\&token=04c53f49-4a52-4ea6-befa-1675e781fc31)

#### B+ Tree Operations

*Insert*

1. 找到对应的 leaf node，L
2. 将 key/value pair 按顺序插入到 L 中
3. 如果 L 还有足够的空间，操作结束；如果空间不足，则需要将 L 分裂成两个节点，同时在 parent node 上新增 entry，若 parent node 也空间不足，则递归地分裂，直到 root node 为止。

*Delete*

1. 从 root 开始，找到目标 entry 所处的 leaf node, L
2. 删除该 entry
3. 如果 L 仍然至少处于半满状态，则操作结束；否则先尝试从 siblings 那里拆借 entries，如果失败，则将 L 与相应的 sibling 合并
4. 如果合并发生了，则可能需要递归地删除 parent node 中的 entry

B+Tree 的 Insert、Delete 过程，可参考[这里](https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html)。

#### In Practice

* Typical Fill-Factor: 67%
  * Average Fanout = 2\*100\*0.67 = 234
* Typical Capacities:
  * Height 4: 312,900,721 entries
  * Height 3:     2,406,104 entries
* Pages per level:
  * Level 1 =           1 page  =    8KB
  * Level 2 =      134 pages =  1MB
  * Level 3 = 17956 pages = 140 MB

#### Clustered Indexes

Clustered Indexes 规定了 table 本身的物理存储方式，通常即按 primary key 排序存储，因此一个 table 只能建立一个 cluster index。有些 DBMSs 对每个 table 都添加聚簇索引，如果该 table 没有 primary key，则 DBMS 会为其自动生成一个；而有些 DBMSs 则不支持 clustered indexes。

#### Compound Index

DBMS 支持同时对多个字段建立 table index（B+ Tree），即 compound index，如

```sql
CREATE INDEX compound_idx ON table (a, b, c);
```

它可以被用在包含 a 的 condition 的查询中，如：

```sql
SELECT c
  FROM table
 WHERE a = 5 AND b >= 42 AND c < 77;
 
SELECT c
  FROM table
 WHERE a = 5 AND b >= 42;

SELECT c
  FROM table
 WHERE a = 5;
```

尽管它可以被用在不包含 a 相关 condition 的查询中，但这约等于全表扫描，因此 DBMS 通常会使用全表扫描。如果使用 hash index 作为 table index，则必须对 (a, b, c) 完全匹配才可以使用。

### B+ Tree Design Choices

#### Node Size

通常来说，disk 的数据读取速度越慢，node size 就越大：

| Disk Type | Node Size |
| --------- | --------- |
| HDD       | \~1MB     |
| SSD       | \~10KB    |
| In-Memory | \~512B    |

具体情境下的最优大小由 workload 决定。

#### Merge Threshold

由于 merge 操作引起的修改较大，有些 DBMS 选择延迟 merge 操作的发生时间，甚至可以利用其它进程来负责周期性地重建 table index。

#### Variable Length Keys

B+ Tree 中存储的 key 经常是变长的，通常有三种手段来应对：

1. Pointers：存储指向 key 的指针
2. Variable Length Nodes：需要精细的内存管理操作
3. Key Map：内嵌一个指针数组，指向 node 中的 key/val list&#x20;

#### Non-unique Indexes

索引针对的 key 可能是非唯一的，通常有两种手段来应对：

1. Duplicate Keys：存储多次相同的 key
2. Value Lists：每个 key 只出现一次，但同时维护另一个链表，存储 key 对应的多个 values，类似 chained hashing

分别如下面两张图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_0J7tK9NuY_hCjQq7k%2F-L_0LltxgsSJAcnO5TnR%2FScreen%20Shot%202019-03-03%20at%2010.21.08%20AM.jpg?alt=media\&token=0c2c4c22-8570-4d5b-bbef-0b8c2aa80351)

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_0J7tK9NuY_hCjQq7k%2F-L_0LoG2q-PazVQ2OD-5%2FScreen%20Shot%202019-03-03%20at%2010.21.16%20AM.jpg?alt=media\&token=541fa6b1-24c7-40eb-806f-c4d64a89d981)

#### Intra-node Search

在节点内部搜索，就是在排好序的序列中检索元素，手段通常有：

* Linear Scan
* Binary Search
* Interpolation：通过 keys 的分布统计信息来估计大概位置进行检索

### Optimizations

#### Prefix Compression

同一个 leaf node 中的 keys 通常有相同的 prefix，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_1_UDdC7q8aUpWoZFP%2F-L_1_xqPyDnHWGa_t-bM%2FScreen%20Shot%202019-03-03%20at%204.07.14%20PM.jpg?alt=media\&token=e4a05c0b-aaae-4d68-b7aa-b26af773bf84)

为了节省空间，可以只存所有 keys 的不同的 suffix。

#### Suffix Truncation

由于 inner nodes 只用于引导搜索，因此没有必要在 inner nodes 中储存完整的 key，我们可以只存储足够的 prefix 即可，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_1_UDdC7q8aUpWoZFP%2F-L_1bJBUJ9Jc373f5emC%2FScreen%20Shot%202019-03-03%20at%204.13.09%20PM.jpg?alt=media\&token=f4ddc5b1-16a2-4471-8e4b-e0d6ca328ce0)

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_1_UDdC7q8aUpWoZFP%2F-L_1bOmad1u6PBka5lAw%2FScreen%20Shot%202019-03-03%20at%204.13.31%20PM.jpg?alt=media\&token=7d200429-7aa0-41bd-a563-dcd5b6cdf944)

#### Bulk Insert

建 B+ Tree 的最快方式是先将 keys 排好序后，再从下往上建树，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_1_UDdC7q8aUpWoZFP%2F-L_1cIAI_Y6fIIaj2u05%2FScreen%20Shot%202019-03-03%20at%204.17.26%20PM.jpg?alt=media\&token=9062db09-0be9-4e85-82be-c5ac48489541)

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_1_UDdC7q8aUpWoZFP%2F-L_1cK6-vXCwjezwdcKS%2FScreen%20Shot%202019-03-03%20at%204.17.20%20PM.jpg?alt=media\&token=ed9eff87-09fa-4e63-9631-e25f5b7df06a)

因此如果有大量插入操作，可以利用这种方式提高效率

#### Pointer Swizzling

Nodes 使用 page id 来存储其它 nodes 的引用，DBMS 每次需要首先从 page table 中获取对应的内存地址，然后才能获取相应的 nodes 本身，如果 page 已经在 buffer pool 中，我们可以直接存储其它 page 在 buffer pool 中的内存地址作为引用，从而提高访问效率。

## Additional Index Usage

### Implicit Indexes

许多 DBMSs 会自动创建 index，来帮助施行 integrity constraints，情形包括：

* Primary Keys
* Unique Constraints
* Foreign Keys

如当我们创建下面的 foo table 时：

```sql
CREATE TABLE foo (
  id SERIAL PRIMARY KEY,
  val1 INT NOT NULL,
  val2 VARCHAR(32) UNIQUE
);

CREATE TABLE bar (
  id INT REFERENCES foo (val1),
  val VARCHAR(32)
);
```

DBMS 可能会自动建立以下索引：

```sql
CREATE UNIQUE INDEX foo_pkey ON foo (id);        /* primary keys */
CREATE INDEX foo_val1_key ON foo (val1);         /* foreign keys */
CREATE UNIQUE INDEX foo_val2_key ON foo (val2);  /* Unique Constraints */
```

### Partial Indexes

只针对 table 的子集建立 index，这可以大大减少 index 本身的大小，如下所示：

```sql
CREATE INDEX idx_foo
          ON foo (a, b)
       WHERE c = 'WuTang';
```

一种常见的使用场景就是通过事件来为 indexes 分区，即为不同的年、月、日分别建立索引。

### Covering Indexes

如果 query 所需的所有 column 都存在于 index 中，则 DBMS 甚至不用去获取 tuple 本身即可得到查询结果，如下所示：

```sql
CREATE INDEX idx_foo ON foo (a, b);

SELECT b FROM foo
 WHERE a = 123;
```

甚至可以在 index 中有意加入别的 column （INDEX INCLUDE COLUMNS）：

```sql
CREATE INDEX idx_foo
          ON foo (a, b)
     INCLUDE (c);
```

### Functional/Expression Indexes

index 中的 key 不一定是 column 中的原始值，也可以是通过计算得到的值，如针对以下查询：

```sql
SELECT * FROM users
 WHERE EXTRACT(dow FROM login) = 2;
```

直接针对 login 建立索引是没用的，这时候可以针对计算后的值建立索引：

```sql
CREATE INDEX idx_user_login 
          ON users (EXTRACT(dow FROM login));
```

## Skip Lists

从上文的介绍中，可以发现 table index 实际上就是一个 dynamic order-preserving 的数据结构，同时对增删改查的操作应提供较高的性能（B+ Tree， $$O(logn)$$ ）。

dynamic order-preserving 的数据结构中，最简单的就是 sorted linked list，所有操作的复杂度均在 $$O(n)$$ ，性能较 B+ Tree 相比逊色许多，但如果将多个 sorted linked list 垒起来，就可能提供与 B+ Tree 相媲美的性能：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_1_UDdC7q8aUpWoZFP%2F-L_1pWlPslNDhgbSfMTF%2FScreen%20Shot%202019-03-03%20at%205.15.09%20PM.jpg?alt=media\&token=de50bfb2-2cc1-4a7c-b228-90fe2766a428)

这就是 Skip Lists。在 MIT 6.046 课程中有专门的一节课介绍 Skip Lists，可以[点击](https://zhenghe.gitbook.io/open-courses/mit-6.046/skip-lists)查看。Skip Lists 是一种基于概率的数据结构，它提供的复杂度都是期望的结果。它的 Pros & Cons 总结如下：

* Pros
  * 比 B+ Tree 的一般实现使用更少的内存
  * 插入和删除操作不需要重新平衡树结构
* Cons
  * 并不像 B+ Tree 一样对 disk/cache 的结构友好
  * 反向搜索实现复杂

## Radix Tree

### Radix Tree vs. Trie

radix tree 实际上就是压缩后的 trie

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_1_UDdC7q8aUpWoZFP%2F-L_1xs0YmeoxMZ1Dl51N%2FScreen%20Shot%202019-03-03%20at%205.51.43%20PM.jpg?alt=media\&token=cfb7bba1-76d6-4235-b61a-3c90886b4e76)

### 简介

radix tree 将每个 key 拆成一个序列：

* 树的高度取决于 keys 的长度
* 不需要重新平衡树（rebalancing）
* 从 root 到 leaf 的路径代表相应的 leaf

### Binary Comparable Keys

为了让 keys 能够合理地拆解成序列，许多类型的 key 都需要特殊处理：

* Unsigned Integers：对小端存储的机器要把 bits 翻转一遍
* Signed Integers：需要翻转 2's-complement 从而使得负数小于正数
* Floats：需要分成多个组，然后存储成 unsigned integer
* Compound：分别转化各个 attributes 然后组合起来

举例如下：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_1_UDdC7q8aUpWoZFP%2F-L_1zGqAEB-KtBOE937J%2FScreen%20Shot%202019-03-03%20at%205.57.50%20PM.jpg?alt=media\&token=e8c637b5-0fda-49ae-8db5-e8d03cc68196)

## Inverted Indexes

尽管 tree index 非常有利于 point 和 range 查询，如：

* Find all customers in the 15217 zip code
* Find all orders between June 2018 and September 2018

但对于 keyword search，tree index 就显得无能为力，如：

* Find all Wikipedia articles that contain the word "Pavlo"

尽管 DBMSs 在一定程度上支持这种搜索，但更复杂、灵活的查询就不是它们的专长。有一部分 DBMSs 专门提供复杂、灵活的 keyword search 功能，如 ElasticSearch、Solr、Sphinx 等。

## 参考

[slides1](https://15445.courses.cs.cmu.edu/fall2018/slides/07-trees1.pdf), [slides2](https://15445.courses.cs.cmu.edu/fall2018/slides/08-trees2.pdf)