MongoDB的索引策略分析 /1

近期换了工作，新公司在数据持久化的方面的技术栈用到了MongoDB，遂有了这篇内容，旨在学习Mongo的同时，对Mongo的一些设计进行刨析分解。本篇主要侧重于MongoDB的索引存储策略与传统关系型数据库Mysql的对比与差异原因。

索引存储结构

谈及索引，对于目标检索的过程次数以及I/O次数是存储结构权衡优劣的关键。在Mysql(Innodb)中，我们的聚簇索引、二级索引默认都是由B+树进行索引的存储管理。而在MongoDB中，则采用了B树进行索引的构建。对于二者的孰优孰劣暂不论定，我们先得弄明白这两种数据结构的优势和劣势分别在哪。接下来内容可能会比较偏基础，关于Mysql的部分我会配合着一些基础结构进行分析（因为目前更熟悉一点的还是Mysql）。

B-Tree、B+tree可以说是为磁盘或其它存储工具而生，不同于基础的二叉搜索树，B-树，B+树都有着矮胖的特征，而我们都知道磁盘在读取数据时是以块为基础单位，矮胖的特征意味着一个盘块内可以存放更多的内容，在查找数据的过程中得以减少盘块的读取次数。

B+树

B+树是Mysql(InnoDB)的默认索引结构，包括聚簇索引和二级索引。而其存储的方式也很简单明了，Mysql定义了很多种类型的页面以存放各种数据譬如说Undo日志页（FIL_PAGE_UNDO_LOG）、系统页（FIL_PAGE_TYPE_SYS）、段信息页（FIL_PAGE_INODE），还有我们最基本的存放数据的页叫索引页或者数据页（FIL_PAGE_INDEX），而索引页中的数据，在数据头的数据结构有一个字段叫record_type用于标注数据类型，0代表非叶子节点记录，1代表普通记录。听到这里是不是比较熟悉，让我们来看看一个Mysql存放一张表的数据结构是怎样的。

基本的东西我已经在图上标出来了，虽然已经略去了很多信息，但是大体结构大家可以意会一下。可以从图上看到数据之间通过指针关联，在叶子节点页面间也通过指针关联，主键有序排列，这就是我们Mysql数据存储数据所构建的一个聚簇索引，二级索引把主键替换为索引列，数据替换为数据主键就好了。从大体结构上看就是一个标准的B+树，即非叶子节点只存放主键范围，而叶子节点存放主键和数据，叶子节点间通过指针相互连接。通过以上结构我们也可以看出一些问题。

非叶子节点由于不存储具体数据，所以可以存放更多的主键范围指向，即我们每次IO可以搜索更多数据。
所有的数据全部存放在叶子节点，非叶子节点只负责索引的工作，所以每次查询的时间复杂度都固定在了O(logn)
在叶子节点部分还通过指针将叶子节点串联起来，而叶子节点间的数据也是有序的，所以提高了区间范围的搜索访问性、

B树

B+树其实是基于B树的矮胖基础形态下，添加了【非叶子节点不存储具体数据内容，只存放索引】、【叶子节点存放全部数据并使用指针连接】两种特性。换句话说，B树的所有节点都存放数据，节点的左子树小于当前节点值，右子树大于当前节点值。

MongoDB是一种面向文档的数据库管理系统，与传统关系型数据库譬如Mysql不同的是Mysql的数据是扁平化的，构建结构化的数据往往需要通过连表查询在业务中进行组合。而MongoDB是面向文档的数据库，数据在存储阶段就是结构化的，聚合的。

我们可以看一下Mongo的数据存储结构是怎样的（按照理解画的）。

Mongo在索引上也区分为主键索引和非主键索引，这方面与Mysql的聚簇索引和二级索引类似，主键索引储存主键以及数据内容，非主键索引储存索引列数据以及主键。从数据存储结构图来进行分析，我们大致能得出以下几个结论：

搜索从根节点开始，由于B树所有节点都会负责数据存储的工作。所以搜索的时间复杂度和数据在结构中的位置强相关，最好的状态是数据在根节点中就搜索到了，可以直接返回，时间复杂度是O(1)。即从平均搜索速度来看MongoDB查询速度会比Mysql更快
单纯从存储结构上看，数据的存储分布在各个节点，因此如果需要对数据进行遍历，则需要对整个树进行数据的读取。但是从整体的角度层面来看，MongoDB的数据是结构化存储，所有的数据都可以以聚合的方式进行存储，对于数据的遍历需求并没有关系型数据库那么高。在数据的存储底层，Mongo使用的也是BSON(Binary Json)进行存储，在类型支持和网络传输效率上相较于Json也有了很大的提升。

小结

本篇我们从传统的关系型数据库和非关系型数据库的视角做了对比，了解了Mongo在数据存储方面使用的结构，以及与关系型数据库在存储方面的差异。数据结构同技术一样没有优劣之分，适合的才是最好的。Mongo作为非关系型数据库，在效率的综合考量上采用了b-tree和bson进行搭配使用，也在搜索速度上达到了一个不差的水平。

以上就是我的一个对于Mongo的初步概览，后续对于Mongo的具体索引模式，以及一个索引优化的思路也会有些总结，对内容中有疑问、错误的部分也欢迎大家指正，交流。

尾巴

最近换了工作，新公司从各方面来看都很好，我也需要花上一些时间精力去融入公司，融入项目。可能与年终总结中定下定期更新博客内容有些冲突，时间没有那么确定。但是至少一月两篇的原创内容还是会尽量去保证的。2020年对于我来说也是个新开始，总之，加油。