MongoDB索引原理

索引的本质

索引（Index）是帮助数据库高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是数据结构。现在的数据库（ mongo，mysql 等）索引多采用 B－Tree 数据结构。

为什么使用B-Tree

红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用 B-/+Tree 作为索引结构。

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储在磁盘上。这样的话，索引查找过程中就要产生磁盘 I/O 消耗，相对于内存存取，I/O 存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘 I/O 操作次数的渐进复杂度。

换句话说，索引的结构组织要尽量减少查找过程中磁盘 I/O 的存取次数。下面先介绍内存和磁盘存取原理，然后再结合这些原理分析 B-/+Tree 作为索引的效率。

主存存取原理

原理

目前计算机使用的主存基本都是随机读写存储器（RAM），现代 RAM 的结构和存取原理比较复杂，这里本文抛却具体差别，抽象出一个十分简单的存取模型来说明 RAM 的工作原理。

01_MongoDB索引原理.png

从抽象角度看，主存是一系列的存储单元组成的矩阵，每个存储单元存储固定大小的数据。每个存储单元有唯一的地址，现代主存的编址规则比较复杂，这里将其简化成一个二维地址：通过一个行地址和一个列地址可以唯一定位到一个存储单元。图5展示了一个4 x 4的主存模型。

主存的存取过程

主存的存取过程如下：

当系统需要读取主存时，则将地址信号放到地址总线上传给主存，主存读到地址信号后，解析信号并定位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取。

写主存的过程类似，系统将要写入单元地址和数据分别放在地址总线和数据总线上，主存读取两个总线的内容，做相应的写操作。

这里可以看出，主存存取的时间仅与存取次数呈线性关系，因为不存在机械操作，两次存取的数据的 “距离” 不会对时间有任何影响，例如，先取 A0 再取 A1 和先取 A0 再取 D3 的时间消耗是一样的。

磁盘存取原理

上文说过，索引一般以文件形式存储在磁盘上，索引检索需要磁盘 I/O 操作。与主存不同，磁盘 I/O 存在机械运动耗费，因此磁盘 I/O 的时间消耗是巨大的。

下图是磁盘的整体结构示意图：

02_MongoDB索引原理.png

一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）。

03_MongoDB索引原理.png

盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。

当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。

局部性原理与磁盘预读

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘 I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：

当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高 I/O 效率。

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

B-/+Tree索引的性能分析

到这里终于可以分析 B-/+Tree 索引的性能了。

上文说过一般使用磁盘 I/O 次数评价索引结构的优劣。先从 B-Tree 分析，根据 B-Tree 的定义，可知检索一次最多需要访问 h（h为数高）个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次 I/O 就可以完全载入。为了达到这个目的，在实际实现 B-Tree 还需要使用如下技巧：

每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个 node 只需一次 I/O。

B-Tree 中一次检索最多需要 h-1 次 I/O（根节点常驻内存），渐进复杂度为 O(h)=O(logdN)。一般实际应用中，出度 d 是非常大的数字，通常超过 100，因此 h 非常小（通常不超过 3）。

综上所述，用 B-Tree 作为索引结构效率是非常高的。

而红黑树这种结构，h 明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的 I/O 渐进复杂度也为 O(h)，效率明显比 B-Tree 差很多。

B+Tree 更适合外存索引，原因和内节点出度 d 有关。从上面分析可以看到，d 越大索引的性能越好，而出度的上限取决于节点内 key 和 data 的大小：

dmax = floor(pagesize / (keysize + datasize + pointsize))   (pagesize – dmax >= pointsize)

或

dmax = floor(pagesize / (keysize + datasize + pointsize)) – 1   (pagesize – dmax < pointsize)

floor 表示向下取整。由于 B+Tree 内节点去掉了 data 域，因此可以拥有更大的出度，拥有更好的性能。

mongo中的索引

当你抱怨 MongoDB 集合查询效率低的时候，可能你就需要考虑使用索引了，为了方便后续介绍，先科普下 MongoDB 里的索引机制（同样适用于其他的数据库比如 mysql）。

db.person.find()
{ "_id" : ObjectId("571b5da31b0d530a03b3ce82"), "name" : "jack", "age" : 19 }
{ "_id" : ObjectId("571b5dae1b0d530a03b3ce83"), "name" : "rose", "age" : 20 }
{ "_id" : ObjectId("571b5db81b0d530a03b3ce84"), "name" : "jack", "age" : 18 }
{ "_id" : ObjectId("571b5dc21b0d530a03b3ce85"), "name" : "tony", "age" : 21 }
{ "_id" : ObjectId("571b5dc21b0d530a03b3ce86"), "name" : "adam", "age" : 18 }

当你往某各个集合插入多个文档后，每个文档在经过底层的存储引擎持久化后，会有一个位置信息，通过这个位置信息，就能从存储引擎里读出该文档。比如 mmapv1 引擎里，位置信息是 [文件 id + 文件内 offset]，

在 wiredtiger 存储引擎（一个 KV 存储引擎）里，位置信息是 wiredtiger 在存储文档时生成的一个 key，通过这个 key 能访问到对应的文档；为方便介绍，统一用 pos(position 的缩写)来代表位置信息。

比如上面的例子里，person 集合里包含插入了 4 个文档，假设其存储后位置信息如下(为方便描述，文档省去 _id 字段)

位置信息	文档
pos1	{“name” : “jack”, “age” : 19 }
pos2	{“name” : “rose”, “age” : 20 }
pos3	{“name” : “jack”, “age” : 18 }
pos4	{“name” : “tony”, “age” : 21}
pos5	{“name” : “adam”, “age” : 18}

假设现在有个查询 db.person.find( {age: 18} ), 查询所有年龄为18岁的人，这时需要遍历所有的文档（全表扫描），根据位置信息读出文档，对比 age 字段是否为 18。当然如果只有 4 个文档，全表扫描的开销并不大，但如果集合文档数量到百万、甚至千万上亿的时候，对集合进行全表扫描开销是非常大的，一个查询耗费数十秒甚至几分钟都有可能。

如果想加速 db.person.find( {age: 18} ），就可以考虑对 person 表的 age 字段建立索引。

db.person.createIndex( {age: 1} )  // 按age字段创建升序索引

建立索引后，MongoDB 会额外存储一份按 age 字段升序排序的索引数据，索引结构类似如下，索引通常采用类似 btree 的结构持久化存储，以保证从索引里快速（O(logN)的时间复杂度）找出某个 age 值对应的位置信息，然后根据位置信息就能读取出对应的文档。

AGE	位置信息
18	pos3
18	pos5
19	pos1
20	pos2
21	pos4

简单的说，索引就是将文档按照某个（或某些）字段顺序组织起来，以便能根据该字段高效的查询。有了索引，至少能优化如下场景的效率：

查询，比如查询年龄为 18 的所有人。
更新/删除，将年龄为 18 的所有人的信息更新或删除，因为更新或删除时，需要根据条件先查询出所有符合条件的文档，所以本质上还是在优化查询。
排序，将所有人的信息按年龄排序，如果没有索引，需要全表扫描文档，然后再对扫描的结果进行排序。

众所周知，MongoDB 默认会为插入的文档生成 _id 字段（如果应用本身没有指定该字段），_id 是文档唯一的标识，为了保证能根据文档id快递查询文档，MongoDB 默认会为集合创建 _id 字段的索引。

db.person.getIndexes() // 查询集合的索引信息
[
    {
        "ns" : "test.person",  // 集合名
        "v" : 1,               // 索引版本
        "key" : {              // 索引的字段及排序方向
            "_id" : 1           // 根据_id字段升序索引
        },
        "name" : "_id_"        // 索引的名称
    }
]

索引原理总结

索引（Index）是帮助数据库高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是数据结构。现在的数据库（ mongo，mysql 等）索引多采用 B－Tree 数据结构。