写点什么

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

评论

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

不止缓存!Redis这16种妙用你可能没见识过……

Java你猿哥

redis 缓存 分布式 消息队列 全局唯一ID

mac端摄影师青睐软件:ON1 Photo RAW 2023.5 中文激活版

真大的脸盆

Mac Mac 软件 图像编辑 编辑图像 照片编辑

PoseiSwap  参赛,参与斯坦福、Nautilus Chain等联合主办的 Hackathon 活动

股市老人

极光笔记 | EngageLab Push的多时区解决方案

极光GPTBots-极光推送

运营 消息推送 笔记分享 海外

C语言编程—作用域规则

芯动大师

PoseiSwap 参赛,参与斯坦福、Nautilus等联合主办的 Hackathon 活动

BlockChain先知

设计模式之订阅发布模式

越长大越悲伤

设计模式 发布订阅模式 spring boot3 订阅发布

神册!出自阿里P8的深入理解Java虚拟机最新版,让我涨薪60%

Java你猿哥

Java JVM 虚拟机 并发 代码优化

京东首席系统架构师教你如何搭建高可用高并发系统架构

Java 高可用 系统架构 高并发

Go 语言 map 如何顺序读取?

AlwaysBeta

Go 面试 map

PoseiSwap  参赛,参与斯坦福、Nautilus等联合主办的 Hackathon 活动

鳄鱼视界

Auto-GPT 迈向智能体的第一步——从信息增强和上下文理解开始

Zilliz

Milvus 向量数据库 autogpt gptcache zillizcloud

Vue3 修改项目名称及相关信息

Andy

SpringBoot 整合 MyBatis 组合 Redis 作为数据源缓存

Java你猿哥

Java redis Spring Boot mybatis ssm

世界顶级级架构师编写2580页DDD领域驱动设计笔记,属实有牌面

Java你猿哥

Java 领域驱动设计 DDD crud 领域驱动

Go 语言 map 是并发安全的吗?

AlwaysBeta

Go 面试 map

CMake vs Makefile: 如何选择适合你的项目构建工具

小万哥

Linux 程序员 C/C++ 后端开发 cmake

关于斐波那契数列的笔记

贝湖光

AIGC背后的技术分析 | 机器学习背后的微分入门

TiAmo

机器学习 AIGC

PoseiSwap 参赛,参与斯坦福、Nautilus等联合主办的 Hackathon 活动

西柚子

线程是如何通讯的?

Java你猿哥

Java 线程 多线程 ssm 通讯

公司来了一个腾讯做优化的大佬,三下五除二让我程序快了200%

Java 性能优化 JVM 性能调优

聊聊技术变现这件事

老张

斜杠青年 技术变现 技术咨询

改变开发的未来 | 探索无服务器与人工智能的协同效应

亚马逊云科技 (Amazon Web Services)

Serverless

数字化转型应该如何去做?(敏捷思维篇)

数字随行

数字化转型

MySQL 正确使用带有横线“-”SQL语句

Andy

Zebec生态进展迅速,频被BitFlow、Matryx DAO等蹭热度碰瓷

鳄鱼视界

2023-05-26:golang关于垃圾回收和析构函数的选择题,多数人会选错。

福大大架构师每日一题

golang 福大大

Django笔记三十七之多数据库操作(补充版)

Hunter熊

Python django 多数据库

Github星标88.8k,阿里新产的Spring Cloud进阶小册!面面俱到

Java你猿哥

Java 架构 微服务 微服务架构 Spring Cloud

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