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年对于我来说也是个新开始,总之,加油。

https://juejin.im/post/5ea45a4451882573883be438

「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论