写点什么

为什么 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:282116

评论

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

智慧警务,大数据分析决策平台建设方案

t13823115967

大数据

移动开发属于哪个领域!2021年Android春招面试经历,详细的Android学习指南

欢喜学安卓

android 程序员 面试 移动开发

学习安卓开发!View的这些基础知识你必须要知道,Android岗

欢喜学安卓

android 程序员 面试 移动开发

面向垂直领域的OpenIE图谱构建技术

DataFunTalk

爱奇艺SOAR探索与实践

爱奇艺技术产品团队

安全

消失的同事

石君

时代发展 28天写作

多熟悉一门编程语言看法

superman

架构师第 6 课作业及学习总结

小诗

「架构师训练营第 1 期」

独角兽余额宝(Java现场面试48题):性能调优+索引+Mysql+缓存+HashMap+GC

Java架构之路

Java 程序员 架构 面试 编程语言

Activemq Jms 简单示例

Java 消息队列 JMS Activemq

Prometheus学习笔记之查询【基础篇】

卓丁

Prometheus Monitor 监控告警 普罗米修斯 PromQL

Spring Cloud Gateway (七)处理流程解析

Java 网关 SpringGateway

「学习笔记」深入理解ThreadLocal

Java架构师迁哥

2021 十大技术趋势扑面而来,你准备好了吗?

李忠良

区块链 人工智能 云计算 大数据 架构

面试大揭秘!从技术面被“虐”到征服CTO,全凭这份强到离谱的pdf

Java架构之路

Java 程序员 架构 面试 编程语言

MySQL慢查询(中):正确的处理姿势,你get到了吗?

架构精进之路

MySQL MySQL优化 MySQL架构 28天写作

架构师训练营 第十二周作业

文江

Go的声明语法为什么是这样

Rayjun

Go 语言

OOP: DIP与LSP

Iris

面向对象 架构训练营

链上数据存储,区块链底层技术落地

t13823115967

区块链落地

推荐系统解构

DataFunTalk

大数据

芯片破壁者(二十五):从全球贸易网络看芯片博弈

脑极体

架构师训练营第十二周作业

丁乐洪

网卡分身技术,你 Get 了吗

Linux云计算网络

网络

案例研究之聊聊 QLExpress 源码 (一)

小诚信驿站

聊聊架构 规则引擎 28天写作 QLExpress源码 聊聊源码

大作业 1

郎哲

追寻人生的意义

三只猫

28天写作

精选算法面试-链表(判断环)

李孟聊AI

算法 链表 28天写作

面向对象设计总结

Iris

面向对象

用 flomo 管理自己的奇思妙想瀑布流

Guanngxu

洞察

JiangX

创业 投资 认知 28天写作 洞察

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