HarmonyOS开发者限时福利来啦!最高10w+现金激励等你拿~ 了解详情
写点什么

为什么 MongoDB 使用 B 树(二)

  • 2019-12-26
  • 本文字数:1632 字

    阅读完需:约 5 分钟

为什么 MongoDB 使用 B 树(二)

非关系型

我们在上面其实已经多次提到了 MongoDB 是非关系型的文档数据库,它完全抛弃了关系型数据库那一套体系之后,在设计和实现上就非常自由,它不再需要遵循 SQL 和关系型数据库的体系,可以更自由对特定场景进行优化,而在 MongoDB 假设的场景中遍历数据并不是常见的需求。



MySQL 中使用 B+ 树是因为 B+ 树只有叶节点会存储数据,将树中的每一个叶节点通过指针连接起来就能实现顺序遍历,而遍历数据在关系型数据库中非常常见,所以这么选择是完全没有问题的7


MongoDB 和 MySQL 在多个不同数据结构之间选择的最终目的就是减少查询需要的随机 IO 次数,MySQL 认为遍历数据的查询是常见的,所以它选择 B+ 树作为底层数据结构,而舍弃了通过非叶节点存储数据这一特性,但是 MongoDB 面对的问题就不太一样了:



虽然遍历数据的查询是相对常见的,但是 MongoDB 认为查询单个数据记录远比遍历数据更加常见,由于 B 树的非叶结点也可以存储数据,所以查询一条数据所需要的平均随机 IO 次数会比 B+ 树少,使用 B 树的 MongoDB 在类似场景中的查询速度就会比 MySQL 快。这里并不是说 MongoDB 并不能对数据进行遍历,我们在 MongoDB 中也可以使用范围来查询一批满足对应条件的记录,只是需要的时间会比 MySQL 长一些。


SQL


SELECT * FROM comments WHERE created_at > '2019-01-01'
复制代码


很多人看到遍历数据的查询想到的可能都是如上所示的范围查询,然而在关系型数据库中更常见的其实是如下所示的 SQL —— 查询外键或者某字段等于某一个值的全部记录:


SQL


SELECT * FROM comments WHERE post_id = 1
复制代码


上述查询其实并不是范围查询,它没有使用 >< 等表达式,但是它却会在 comments 表中查询一系列的记录,如果 comments 表上有索引 post_id,那么这个查询可能就会在索引中遍历相应索引,找到满足条件的 comment,这种查询也会受益于 MySQL B+ 树相互连接的叶节点,因为它能减少磁盘的随机 IO 次数。


MongoDB 作为非关系型的数据库,它从集合的设计上就使用了完全不同的方法,如果我们仍然使用传统的关系型数据库的表设计思路来思考 MongoDB 中集合的设计,写出类似如上所示的查询会带来相对比较差的性能:


JavaScript


db.comments.find( { post_id: 1 } )
复制代码


因为 B 树的所有节点都能存储数据,各个连续的节点之间没有很好的办法通过指针相连,所以上述查询在 B 树中性能会比 B+ 树差很多,但是这并不是一个 MongoDB 中推荐的设计方法,更合适的做法其实是使用嵌入文档,将 post 和属于它的所有 comments 都存储到一起:


JSON


{    "_id": "...",    "title": "为什么 MongoDB 使用 B 树",    "author": "draven",    "comments": [        {            "_id": "...",            "content": "你这写的不行"        },        {            "_id": "...",            "content": "一楼说的对"        }    ]}
复制代码


使用上述方式对数据进行存储时就不会遇到 db.comments.find( { post_id: 1 } ) 这样的查询了,我们只需要将 post 取出来就会获得相关的全部评论,这种区别于传统关系型数据库的设计方式是需要所有使用 MongoDB 的开发者重新思考的,这也是很多人使用 MongoDB 后却发现性能不如 MySQL 的最大原因 —— 使用的姿势不对。


有些读者到这里可能会有疑问了,既然 MongoDB 认为查询单个数据记录远比遍历数据的查询更加常见,那为什么不使用哈希作为底层的数据结构呢?



如果我们使用哈希,那么对于所有单条记录查询的复杂度都会是 O(1),但是遍历数据的复杂度就是 O(n);如果使用 B+ 树,那么单条记录查询的复杂度是 O(log n),遍历数据的复杂度就是 O(log n) + X,这两种不同的数据结构一种提供了最好的单记录查询性能,一种提供了最好的遍历数据的性能,但是这都不能满足 MongoDB 面对的场景 —— 单记录查询非常常见,但是对于遍历数据也需要有相对较好的性能支持,哈希这种性能表现较为极端的数据结构往往只能在简单、极端的场景下使用。


本文转载自 Draveness 技术博客。


原文链接:https://draveness.me/whys-the-design-mongodb-b-tree


2019-12-26 17:282011

评论

发布
暂无评论
发现更多内容

分布式架构10-CAP理论

亮哥的成长三板斧

架构 分布式架构

轻量应用服务器到底有多好?华为云云耀云服务器L实例来告诉你

轶天下事

分布式架构03-副本协议

亮哥的成长三板斧

架构 分布式架构

分布式架构07-两阶段提交协议

亮哥的成长三板斧

架构 分布式架构

分布式架构08- MVCC

亮哥的成长三板斧

架构 分布式架构

分布式架构完结篇

亮哥的成长三板斧

架构 分布式架构

ARTS 打卡第 29 天

自由

ARTS 打卡计划

轻量级云服务器推荐,华为云云耀L实例助你一臂之力

平平无奇爱好科技

华为云云耀云服务器L实例:中小企业和开发者的云端伙伴

平平无奇爱好科技

分布式架构02-数据分布

亮哥的成长三板斧

架构 分布式架构

分布式架构04-lease机制

亮哥的成长三板斧

架构 分布式架构

分布式架构05-quorum机制

亮哥的成长三板斧

架构 分布式架构

轻量应用服务器怎么样?云耀云服务器L实例值得入手吗?

轶天下事

分布式架构06-日志技术

亮哥的成长三板斧

架构 分布式架构

微服务架构简要剖析

亮哥的成长三板斧

架构 分布式 微服务

数据通信网络之使用 eNSP 组网

timerring

数据通信网络

快速试错01-重新理解低成本创业

亮哥的成长三板斧

精益创业

为什么选择华为云云耀云服务器L实例作为轻量应用服务器?

轶天下事

华为云云耀云服务器实例L:为企业提供安全可靠的轻量应用服务器架构

平平无奇爱好科技

蓝易云:RabbitMQ安装、端口修改、基本操作详解!

百度搜索:蓝易云

云计算 Linux 运维 RabbitMQ 云服务器

分布式架构-提问环节

亮哥的成长三板斧

架构 分布式架构

分布式架构-阶段总结

亮哥的成长三板斧

架构 分布式架构

分布式架构09-Paxos协议

亮哥的成长三板斧

架构 分布式架构

为什么 MongoDB 使用 B 树(二)_语言 & 开发_Draveness_InfoQ精选文章