BTree 索引原理及其应用

虽然写 BTree，但其实本章主要讨论其中一个优化的子集，即广泛使用的 B+Tree。

1. BTree

1.1. BTree 结构

1.2. BTree 索引特性

例如存在如下的表

ID | first_name | last_name    | Class      | Position |  ssn | 
---------------------------------------------------------------
| Teemo      | Shroomer     | Specialist | Top      | 2345 |
| Cecil      | Heimerdinger | Specialist | Mid      | 5461 |
| Annie      | Hastur       | Mage       | Mid      | 8784 |
| Fiora      | Laurent      | Slayer     | Top      | 7867 |
| Garen      | Crownguard   | Fighter    | Top      | 4579 |
| Malcolm    | Graves       | Specialist | ADC      | 4578 |
| Irelia     | Lito         | Figher     | Top      | 5689 |
| Janna      | Windforce    | Controller | Support  | 4580 |
| Jarvan     | Lightshield  | Figher     | Top      | 4579 |
| Katarina   | DuCouteau    | Assassin   | Mid      | 5608 |
| Kayle      | Hex          | Specialist | Top      | 4794 |
| Emilia     | LeBlanc      | Mage       | Mid      | 3468 |
| Lee        | Sin          | Fighter    | Jungle   | 8085 |
| Lux        | Crownguard   | Mage       | Mid      | 4567 |
| Sarah      | Fortune      | Marksman   | ADC      | 6560 |
| Morgana    | Hex          | Controller | Support  | 3457 |
| Orianna    | Reveck       | Mage       | Mid      | 9282 |
| Sona       | Buvelle      | Controller | Support  | 4722 |
| Jericho    | Swain        | Mage       | Mid      | 5489 |
| Shauna     | Vayne        | Marksman   | ADC      | 2352 |
| Xin        | Zhao         | Fighter    | Jungle   | 6902 |
| Yorick     | Mori         | Tank       | Top      | 4840 |
| Wu         | Kong         | Fighter    | Jungle   | 4933 |

创建 users.first_name 的索引，B+Tree 叶子节点组织如下：

first_name  Primary Key
-----------------------
Annie    -> 3
Cecil    -> 2
Emilia   -> 12
Fiora    -> 4
Garen    -> 5
Irelia   -> 7
Janna    -> 8
Jarvan   -> 9
Jericho  -> 19
Katarina -> 10
Kayle    -> 11
Lee      -> 13
Lux      -> 14
Malcolm  -> 6
Morgana  -> 16
Orianna  -> 17
Sarah    -> 15
Shauna   -> 20
Sona     -> 18
Teemo    -> 1
Wu       -> 23
Xin      -> 21
Yorick   -> 22

那么复合索引呢？

创建 (class, position) 的复合索引，B+Tree 叶子节点组织如下：

class-position       Primary Key
--------------------------------
AssassinMid       -> 10
ControllerSupport -> 16
ControllerSupport -> 18
ControllerSupport -> 8
FigherTop         -> 7
FigherTop         -> 9
FighterJungle     -> 13
FighterJungle     -> 21
FighterJungle     -> 23
FighterTop        -> 5
MageMid           -> 12
MageMid           -> 14
MageMid           -> 17
MageMid           -> 19
MageMid           -> 3
MarksmanADC       -> 15
MarksmanADC       -> 20
SlayerTop         -> 4
SpecialistADC     -> 6
SpecialistMid     -> 2
SpecialistTop     -> 1
SpecialistTop     -> 11
TankTop           -> 22

可以看到，叶子节点会首先根据 class 的字典序、其次根据 position 的字典序组织。

最左前缀：(a, b, c) => (a), (a, b), (a, b, c), (a, b, c[:k]), (a, b[:k]), (a[:k])
第一原则是，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。

1.3. 与 BTree 的区别

B + 树查询时间复杂度固定是 logn，B 树查询复杂度最好是 O (1)。
B 树每个节点即保存数据又保存索引，因此每个节点的字节点指针数量更少，即扇出更少，高度通常比 B+ 树高
B + 树相邻接点的指针可以大大增加区间访问性，范围查询效率更高

2. BTree In Storage Engine

存储引擎要做的事情无外乎是将磁盘上的数据读到内存并返回给应用，或者将应用修改的数据由内存写到磁盘上。如何设计一种高效的数据结构和算法是所有存储引擎要考虑的根本问题，目前大多数流行的存储引擎是基于 BTree 或 LSM Tree 这两种数据结构来设计的。

2.1. InnoDB

每一个索引在 InnoDB 里面对应一棵 B+ 树。

2.1.1. 数据结构

聚簇索引

InnoDB 要求表必须有主键

InnoDB 的数据文件本身就是索引文件。

表数据文件本身就是按 B+Tree 组织的一个索引结构，这棵树的叶节点 data 域保存了完整的数据记录。这个索引的 key 是数据表的主键，因此 InnoDB 表数据文件本身就是主索引。

为什么要有聚簇索引？磁盘上的组织是如何的？

索引维护

B+ 树为了维护索引有序性，在插入新值的时候需要做必要的维护。以上面这个图为例，如果插入新的行 ID 值为 700，则只需要在 R5 的记录后面插入一个新记录。如果新插入的 ID 值为 400，就相对麻烦了，需要逻辑上挪动后面的数据，空出位置。页分裂、合并则需要更耗时的操作。

自增主键的插入数据模式，正符合了我们前面提到的递增插入的场景。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。

索引列的选择

基于上面的索引维护过程说明，我们来讨论一个案例：

你可能在一些建表规范里面见到过类似的描述，要求建表语句里一定要有自增主键。当然事无绝对，我们来分析一下哪些场景下应该使用自增主键，而哪些场景下不应该。

时间：自增主键的插入数据模式，正符合了我们前面提到的递增插入的场景。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。
空间：由于每个非主键索引的叶子节点上都是主键的值，因此主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。

所以，从性能和存储空间方面考量，自增主键往往是更合理的选择。

比如，有些业务的场景需求是这样的（典型的 KV 场景）：

只有一个索引；
该索引必须是唯一索引。

这时候，尽量使用主键查询，可以避免每次查询需要搜索两棵树（回表）。

2.1.2. 覆盖索引

select * from T where k between 3 and 5，需要执行几次树的搜索操作，会扫描多少行？

在 k 索引树上找到 k=3 的记录，取得 ID = 300；
再到 ID 索引树查到 ID=300 对应的 R3；
在 k 索引树取下一个值 k=5，取得 ID=500；
再回到 ID 索引树查到 ID=500 对应的 R4；
在 k 索引树取下一个值 k=6，不满足条件，循环结束。

select ID from T where k between 3 and 5 呢？

这时只需要查 ID 的值，而 ID 的值已经在 k 索引树上了，因此可以直接提供查询结果，不需要回表。也就是说，在这个查询里面，索引 k 已经 “覆盖了” 我们的查询需求，我们称为覆盖索引。

字段顺序

这个最左前缀可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。

因为可以支持最左前缀，所以当已经有了 (a,b) 这个联合索引后，一般就不需要单独在 a 上建立索引了。因此，第一原则是，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。

索引越多，“维护成本” 越大

2.1.3. 索引下推

对于联合索引（name, age）为例。如果现在有一个需求：检索出表中 “名字第一个字是张，而且年龄是 10 岁的所有男孩”。那么，SQL 语句是这么写的：

select * from tuser where name like ‘ 张 %’ and age=10 and ismale=1;

索引只能用 “张”

然后？

判断其他条件是否满足。

在 MySQL 5.6 之前，只能从 ID3 开始一个个回表。到主键索引上找出数据行，再对比字段值。

而 MySQL 5.6 引入的索引下推优化（index condition pushdown)，可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

2.2. WiredTiger

其实 mongo 除了 wiredtiger 之外，还支持 mongrocks，不过 mongorocks 底层是使用基于 LSM-Tree 的 RocksDB。本文只讨论 BTree，所以 mongorocks 抛到一边。

2.2.1. 数据结构

wiredtiger 维护索引文件跟数据文件。

key 其实是一个 RecordID，每插入一个文档都会插入新的 key/value（RecordID => RecordPosition）

mongo 中并不会将 id 索引与行内容存放在一起（即没有聚簇索引的概念）。取而代之的，mongodb 将索引与数据分开存放，通过 RecordId 进行间接引用。

举例一张包含两个索引（id 和 name）的表，在 wt 层将有三张表与其对应。

如上图所示，集合包含 {_id: 1}, {name: 1} 2 个索引

用户插入文档时，底层引擎将文档内容存储，返回对应的位置信息，即 RecordId1
集合包含 2 个索引

插入 {_id: ObjectId1} ⇒ RecordId1 的索引
插入 {name: “rose”} ⇒ RecordId1 的索引

有了上述的数据，在根据_id 访问时文档时（根据其他索引字段类似）

根据文档的 _id 字段从底层 KV 引擎读取 RecordId
根据 RecordId 从底层 KV 引擎读取文档内容

WechatIMG761

2.2.2. 索引实现

其实所有 BTree 索引的实现都是大同小异

在 MongoDB 中，没有 clustered index，因此，Collection 初始的物理存储跟 doc 插入的顺序有关，MongoDB 按照 doc 插入的顺序，依次将 doc 存储在 disk 上，插入顺序上相邻的 doc 在 disk 的物理位置上也是相邻的；对 doc 的修改可能对 collection 的物理存储发生变化，如果 doc 的修改不会导致 doc 的 size 增加，那么 doc 会继续存储在原来的存储空间中，而不会对 collection 的物理存储有影响，一旦修改操作导致 doc 的 size 增加，导致 doc 发生移动，那么 collection 的物理存储就会发生变化。

如果插入的集合包含索引（MongoDB 的集合默认会有_id 索引），针对每项索引，还会往 WiredTiger 插入一个新的 key-value，key 是索引的字段内容，value 为插入文档时生成的 RecordId，这样就能快速根据索引找到文档的位置信息。

ObjectID

为什么 ObjectID 是递增的？

上文说到插入顺序上相邻的 doc 在 disk 的物理位置上也是相邻的。因此默认的 ObjectID 上的索引中，叶子结点的数据也是相邻的（highly clustered）。

单字段索引

下述索引会对 age 进行升序排序

db.person.createIndex( {age: 1} )

复合索引

这个索引要先按 age 字段升序、age 相同的按 name 字段降序

db.person.createIndex( {age: 1, name: 1} )

那么下面语句呢？

db.person.createIndex( {age: 1, name: -1} )

MongoDB 针对每个索引，会有一个位图来描述索引各个字段的排序方向，如果方向是逆序（如 b: -1），会把 key 的内容里将 b 字段对应的 bit 全部取反。

InnoDB 的回表查询也适用于此，如果复合索引能够覆盖查询，则不用回表。

多 key 索引

当索引的字段为数组时，创建出的索引称为多 key 索引，多 key 索引会为数组的每个元素建立一条索引

{"name" : "jack", "age" : 19, habbit: ["football, runnning"]}
db.person.createIndex( {habbit: 1} )  // 创建多key索引
db.person.find( {habbit: "football"} )

底层会创建类似 person.habbit_football => RecordID1 的索引 key/value

全文索引

待补充

3. Application

3.1. order by / sort

MySQL 跟 MongoDB 的实现类似，这里用 MySQL 来举例。

CREATE TABLE `t` (
  `id` int(11) NOT NULL,
  `city` varchar(16) NOT NULL,
  `name` varchar(16) NOT NULL,
  `age` int(11) NOT NULL,
  `addr` varchar(128) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `city` (`city`)
) ENGINE=InnoDB;

查询城市是 “杭州” 的所有人名字，并且按照姓名排序返回前 1000 个人的姓名、年龄。我们执行

select city,name,age from t where city='杭州' order by name limit 1000  ;

通常情况下，这个语句执行流程如下所示：

初始化 sort_buffer，确定放入 name、city、age 这三个字段；
从索引 city 找到第一个满足 city=’ 杭州’条件的主键 id，也就是图中的 ID_X；
到主键 id 索引取出整行，取 name、city、age 三个字段的值，存入 sort_buffer 中；
从索引 city 取下一个记录的主键 id；
重复步骤 3、4 直到 city 的值不满足查询条件为止，对应的主键 id 也就是图中的 ID_Y；
对 sort_buffer 中的数据按照字段 name 做快速排序；
按照排序结果取前 1000 行返回给客户端。

如果需要取的字段过多，超多 sort_buffer 的话，则会走到 rowid 排序（多回表一次）

需要排序的原因是，原来的数据就是无序的。要解决这个问题，则要利用好索引结构。

例如，对上述需求，我们新建索引：

alter table t add index city_user(city, name);

则对于每个 city，name 都是有序的：

当然，这个索引对于上述需求还需要回表去取 age，因此建立 (city, name, age) 的覆盖索引可以避免回表。

如果要取多个城市的呢？

select * from t where city in (“杭州”,"苏州") order by name limit 100;

如果这个需求需要分页呢？

select city,name,age from t where city='杭州' order by name limit 10000,100;

3.2. fuzzy search

待补充

4. Reference

https://mp.weixin.qq.com/s/Wuzh47jsBh5QonBrZxUnjg
https://mongoing.com/archives/5367
https://dzone.com/articles/learn-mongodb-with-me-part-3?utm_source=dzone&utm_medium=article&utm_campaign=mongodb-cluster
https://time.geekbang.org/column/article/73479
MySQL 索引实现 http://blog.codinglabs.org/articles/theory-of-mysql-index.html
innodb 索引：https://tech.bytedance.net/articles/12571#
MongoDB 索引原理 https://yq.aliyun.com/articles/386769
MongoDB 索引选择策略 https://dzone.com/articles/effective-mongodb-indexing-part-2
复合索引的形象描述 https://medium.com/@User3141592/single-vs-composite-indexes-in-relational-databases-58d0eb045cbe

BTree 索引原理及其应用

BTree in Storage Engine

BTree 索引原理及其应用

1. BTree

1.1. BTree 结构

1.2. BTree 索引特性

1.3. 与 BTree 的区别

2. BTree In Storage Engine

2.1. InnoDB

2.1.1. 数据结构

聚簇索引

索引维护

索引列的选择

2.1.2. 覆盖索引

2.1.3. 索引下推

2.2. WiredTiger

2.2.1. 数据结构

2.2.2. 索引实现

ObjectID

单字段索引

复合索引

多 key 索引

全文索引

3. Application

3.1. order by / sort

3.2. fuzzy search

4. Reference

CATALOG

FEATURED TAGS

FRIENDS