为什么MySQL数据库要用B+树存储索引?

时间:2021-07-20 15:42:20
为什么MySQL数据库要用B+树存储索引?

小史:树的话,无非就是前中后序遍历、二叉树、二叉搜索树、平衡二叉树,更高级一点的有红黑树、B 树、B+ 树,还有之前你教我的字典树。

红黑树

为什么MySQL数据库要用B+树存储索引?

一听到红黑树,小史头都大了,开始抱怨了起来。

为什么MySQL数据库要用B+树存储索引?

小史:红黑树看过很多遍了,但是每次都记不住,它的规则实在是太多了,光定义就有四五条规则,还有插入删除的时候,需要调整树,复杂得很。

为什么MySQL数据库要用B+树存储索引?

吕老师:小史,问你红黑树,并不是让你背诵它的定义,或者让你手写一个红黑树,而是想问问你它为什么这样设计,它的使用场景有哪些。

为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?

B 树

为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?

吕老师:小史,你要知道,文件系统和数据库的索引都是存在硬盘上的,并且如果数据量大的话,不一定能一次性加载到内存中。

为什么MySQL数据库要用B+树存储索引?

两个月前,小史面试没考虑内存情况差点挂了。

为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?

B+ 树

为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?

吕老师:这也是和业务场景相关的,你想想,数据库中 Select 数据,不一定只选一条,很多时候会选多条,比如按照 ID 排序后选 10 条。

为什么MySQL数据库要用B+树存储索引?

小史:我明白了,如果是多条的话,B 树需要做局部的中序遍历,可能要跨层访问。

而 B+ 树由于所有数据都在叶子结点,不用跨层,同时由于有链表结构,只需要找到首尾,通过链表就能把所有数据取出来了。

为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?

回到现场

为什么MySQL数据库要用B+树存储索引?
为什么MySQL数据库要用B+树存储索引?

小史:这和业务场景有关。如果只选一个数据,那确实是 Hash 更快。但是数据库中经常会选择多条,这时候由于 B+ 树索引有序,并且又有链表相连,它的查询效率比 Hash 就快很多了。

为什么MySQL数据库要用B+树存储索引?

小史:而且数据库中的索引一般是在磁盘上,数据量大的情况可能无法一次装入内存,B+ 树的设计可以允许数据分批加载,同时树的高度较低,提高查找效率。

为什么MySQL数据库要用B+树存储索引?