【面试现场】为什么 MySQL 数据库要用B+树存储索引？

点击蓝色“ 五分钟学算法 ”关注我哟

加个“ 星标 ”，天天中午 12:15，一起学算法

作者 | channingbreeze

来源公众号 | 互联网侦察

小史是一个应届生，虽然学的是电子专业，但是自己业余时间看了很多互联网与编程方面的书，一心想进 BAT 互联网公司。

话说两个多月前，小史通过了 A 厂的一面，两个多月后的今天，小史终于等到了 A 厂的二面。

简单的自我介绍后，面试官看了看小史的简历，开始发问了。

【面试现场】

小史：没问题，这个项目前端用的 react+webpack ，后端用的 nginx+SpringBoot+Redis+MySql ，前后端分离的，最后用 docker 进行容器化部署。主要模块有师生系统、课程系统、成绩系统、选课系统等。

这个项目的架构和说辞，小史早已背得溜溜的。

小史：底层 mysql 是存储， redis 是缓存， dao 层操作 mysql ， cache 层操作 redis ， service 层处理业务逻辑， rest api 层为前端提供 rest 接口。前端这边用 react 进行模块化， webpack 打包部署。网关 nginx 进行负载均衡。 mysql 、 redis 、 nginx 和 springboot 应用都放在 docker 里部署。

题目： 为什么MySQL数据库要用B+树存储索引？

小史听到这个题目，陷入了回忆。

【前段时间的饭局】

话说吕老师给小史讲完 人工智能的一些知识 后，他们一起回家吃小史姐姐做的饭去了。

【饭后】

吕老师：面试的时候一定是往深了问，不精通的话容易吃亏。不过面试时一般都是根据项目来问，项目中用到的技术，一定要多看看原理，特别是能和数据结构和算法挂钩的那部分。

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

【红黑树】

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

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

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

【B树】

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

两个月前，小史面试没考虑内存情况差点挂了， 传送门

【B+树】