写点什么

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

评论

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

Function Mesh:Serverless 在消息与流数据场景下的火花

Apache Pulsar

大数据 架构 云原生 Apache Pulsar pulsar社区

数据倾斜的产生和解决办法?

编程江湖

顺丰科技 x StarRocks :双十一实时运单分析实践

StarRocks

数据库 大数据 数据分析 StarRocks

Tapdata 在线研讨会:DaaS vs 大数据平台,是竞争还是共处?

MongoDB中文社区

mongodb

为什么要学习linux内核源码以及如何学习Linux内核源码

赖猫

c++ Linux 运维 嵌入式 Linux内核

秋招拿到offer之后,分享面试阿里、头条、腾讯的经过以及一些总结

Geek_1df311

Java 编程 程序员 架构 面试

DPDK 网络协议栈-vpp-OvS-DDos-虚拟化专家之路

赖猫

Linux 网络协议栈 DPDK

关于JAVA中顺序IO的基本操作

编程江湖

Python Qt GUI设计:QSpinBox计数器类(基础篇—15)

不脱发的程序猿

Python PyQt GUI设计 QSpinBox计数器类

【死磕Java并发】-----J.U.C之AQS:阻塞和唤醒线程

chenssy

11月日更 死磕 Java 死磕 Java 并发

如何修复org/jacoco/agent/rt/internal_773e439/Offline异常?

Changing Lin

11月日更

学习Java需要掌握哪些技能?

程序员万金游

Java

活动预告|AICon全球人工智能与机器学习技术大会

第四范式开发者社区

机器学习 开源 OpenMLDB

Java Collectors API实践

FunTester

Java API 测试开发 FunTester Collectors

在 JavaScript 中如何检查对象为空

编程江湖

2021年底Java最新学习路线图

程序员万金游

Java

封神总结!蚂蚁金服+滴滴+美团+拼多多+腾讯15万字Java面试题

热爱java的分享家

Java 面试 程序人生 编程语言 经验分享

豪华阵容!13位专家力荐Spring5为企业级开发提供一站式方案

热爱java的分享家

Java 面试 程序人生 编程语言 经验分享

博文推荐|深度解析如何在 Pulsar 中实现隔离

Apache Pulsar

Java 架构 分布式 云原生 Apache Pulsar

直播预告|11.27(周六)观测云&思否联合举办的开发者线上沙龙巡演第3站来啦

观测云

直播 沙龙

一物一码可追溯!看区块链如何帮助消费者

CECBC

天翼账号网关系统架构演进历程

架构 网关 亿级流量 双十一

(文末福利)如果代码莫名其妙跑起来了,就不要去动它了……吗?

Zilliz

数据库

激荡十年,从未来窗口 re:Invent 看云计算发展变迁 | Q推荐

亚马逊云科技 (Amazon Web Services)

数据库 云计算 云原生 re:Invent

在牛客逮到一个阿里10年老Java开发,聊过之后收益良多...

Geek_1df311

Java 编程 架构 面试 计算机

Java线程的生命周期包括哪几种状态?

程序员万金游

java线程

公司刚来的阿里p8,看完我构建的springboot框架,甩给我一份文档

热爱java的分享家

Java 面试 程序人生 经验分享 P8

博文推荐|腾讯专家深度解析 Apache Pulsar 五大应用场景

Apache Pulsar

架构 分布式 云原生 Apache Pulsar 消息中间件

我滴个乖乖!首次公布Java10W字面经,Github访问量破百万

热爱java的分享家

Java 面试 程序人生 编程语言 经验分享

博文推荐 | Apache Pulsar 三大跨地域复制解决方案

Apache Pulsar

Java 架构 分布式 云原生 Apache Pulsar

TypeScript 之 Typeof Type Operator

冴羽

JavaScript typescript html5 翻译 大前端

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