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

缺乏、安全感 2023-05-31 15:25 19阅读 0赞

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

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

作者 | channingbreeze

来源公众号 | 互联网侦察

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

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

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2]

**【面试现场】**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 3]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 4]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 5]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 6]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 7]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 8]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 9]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 10]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 11]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 12]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 13]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 14]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 15]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 16]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 17]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 18]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 19]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 20]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 21]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 22]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 23]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 24]

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

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

**【前段时间的饭局】**

话说吕老师给小史讲完

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 25]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 26]

**【饭后】**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 27]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 28]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 29]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 30]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 31]

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

**【红黑树】**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 32]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 33]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 34]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 35]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 36]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 37]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 38]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 39]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 40]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 41]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 42]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 43]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 44]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 45]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 46]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 47]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 48]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 49]

**【B树】**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 50]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 51]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 52]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 53]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 54]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 55]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 56]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 57]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 58]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 59]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 60]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 61]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 62]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 63]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 64]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 65]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 66]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 67]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 68]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 69]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 70]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 71]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 72]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 73]

**【B+树】**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 74]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 75]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 76]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 77]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 78]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 79]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 80]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 81]

小史：我明白了，如果是多条的话，B树需要做局部的中序遍历，可能要跨层访问。而B+树由于所有数据都在叶子结点，不用跨层，同时由于有链表结构，只需要找到首尾，通过链表就能把所有数据取出来了。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 82]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 83]

**【回到现场】**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 84]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 85]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 86]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 87]

HR和小史简单地聊了聊基本情况，这次面试就结束了。

小史走后，面试官在系统中写下了面试评语：

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 88]

几天后，小史收到了A厂的offer。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 89]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 90]

\---

以上，便是今日分享，觉得不错，还请点个在看，谢谢～

推荐阅读：

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 91]

[640_wx_fmt_jpeg]: /images/20230531/1878065dc7a24abe969bed044b278318.png
[640_wx_fmt_jpeg 1]: /images/20230531/5df76518570743508798035758948ee9.png
[640_wx_fmt_jpeg 2]: /images/20230531/40f9c1d1c80d4fce9ba1c529679392c8.png
[640_wx_fmt_jpeg 3]: https://img-blog.csdnimg.cn/img_convert/1616b37d7823632c0f0d3f723f5a47c6.png
[640_wx_fmt_jpeg 4]: https://img-blog.csdnimg.cn/img_convert/02bbdbc493113b5650ff61d92f92b86c.png
[640_wx_fmt_jpeg 5]: https://img-blog.csdnimg.cn/img_convert/c52497f820d1fb885d9d0d141cb3605c.png
[640_wx_fmt_jpeg 6]: https://img-blog.csdnimg.cn/img_convert/4cb5f5376e01a9b425cd7b9d986379c5.png
[640_wx_fmt_jpeg 7]: https://img-blog.csdnimg.cn/img_convert/3f47f826b3025952b3fd3dc538433531.png
[640_wx_fmt_jpeg 8]: https://img-blog.csdnimg.cn/img_convert/2c2fa30123287ad82d540bc6e0cefbb7.png
[640_wx_fmt_jpeg 9]: https://img-blog.csdnimg.cn/img_convert/0885f9311f806e25c1d84e3cd19d0f20.png
[640_wx_fmt_jpeg 10]: https://img-blog.csdnimg.cn/img_convert/d1b48e3244d2b38c92dedc72fe1257cb.png
[640_wx_fmt_jpeg 11]: https://img-blog.csdnimg.cn/img_convert/5292fecf377d4660c43771b250eed2e8.png
[640_wx_fmt_jpeg 12]: https://img-blog.csdnimg.cn/img_convert/9b8d6a84892a344875153c42334bd5cf.png
[640_wx_fmt_jpeg 13]: https://img-blog.csdnimg.cn/img_convert/38578070b52bfd81f7626b3656c9e0ae.png
[640_wx_fmt_jpeg 14]: https://img-blog.csdnimg.cn/img_convert/1d1bf8655c20126560c0a49ebcfdf02b.png
[640_wx_fmt_jpeg 15]: https://img-blog.csdnimg.cn/img_convert/8c9bd7a409bd9094bc0e398a66afc1ad.png
[640_wx_fmt_jpeg 16]: https://img-blog.csdnimg.cn/img_convert/892dd8bfc5cd9549a47717c9f31ec320.png
[640_wx_fmt_jpeg 17]: https://img-blog.csdnimg.cn/img_convert/796fcb5035e7cd645022063025eb8912.png
[640_wx_fmt_jpeg 18]: https://img-blog.csdnimg.cn/img_convert/738157f0a15d3e6f63d4d03531e92f2e.png
[640_wx_fmt_jpeg 19]: https://img-blog.csdnimg.cn/img_convert/612040e21b5b5ac0e91394ca4ab90b34.png
[640_wx_fmt_jpeg 20]: https://img-blog.csdnimg.cn/img_convert/e3747f7e277fbffd373b081e63871096.png
[640_wx_fmt_jpeg 21]: https://img-blog.csdnimg.cn/img_convert/abdcf9949892b5a20f2fd866a269cd72.png
[640_wx_fmt_jpeg 22]: https://img-blog.csdnimg.cn/img_convert/c1092c8bf69e8713414b5ec97de44cb4.png
[640_wx_fmt_jpeg 23]: https://img-blog.csdnimg.cn/img_convert/baba6d22ba339b1611cff23ccaa9d500.png
[640_wx_fmt_jpeg 24]: https://img-blog.csdnimg.cn/img_convert/80983d326db1bfa0a0e3f1951360629a.png
[640_wx_fmt_jpeg 25]: https://img-blog.csdnimg.cn/img_convert/87cf54d4f1060557636daea026b3ffa5.png
[640_wx_fmt_jpeg 26]: https://img-blog.csdnimg.cn/img_convert/536e5e101b5521e8db447912427ec444.png
[640_wx_fmt_jpeg 27]: https://img-blog.csdnimg.cn/img_convert/2ca865c47cc82d6bc9f01c64150ede88.png
[640_wx_fmt_jpeg 28]: https://img-blog.csdnimg.cn/img_convert/ed294a2c0b6d84c217e1ef7f3552baff.png
[640_wx_fmt_jpeg 29]: https://img-blog.csdnimg.cn/img_convert/8ea854b4cadabc18c4a7e798c40f6ed5.png
[640_wx_fmt_jpeg 30]: https://img-blog.csdnimg.cn/img_convert/f70221f2ce531e3c39cfd90988a34ae7.png
[640_wx_fmt_jpeg 31]: https://img-blog.csdnimg.cn/img_convert/6c422052d0038d758888523b057bab37.png
[640_wx_fmt_jpeg 32]: https://img-blog.csdnimg.cn/img_convert/ed9944afe820d72095c2be9f2377dc91.png
[640_wx_fmt_jpeg 33]: https://img-blog.csdnimg.cn/img_convert/6e47a2591016d544a814a2df5c0de353.png
[640_wx_fmt_jpeg 34]: https://img-blog.csdnimg.cn/img_convert/b1a0b6dbb11fa55c3d37f849bf55fdc8.png
[640_wx_fmt_jpeg 35]: https://img-blog.csdnimg.cn/img_convert/4882226584459afc17a9db795b34a2d0.png
[640_wx_fmt_jpeg 36]: https://img-blog.csdnimg.cn/img_convert/b11b8efc1cdec6179a81ca6a054b5593.png
[640_wx_fmt_jpeg 37]: https://img-blog.csdnimg.cn/img_convert/5286ff47e189ccae0bab2acece1c279f.png
[640_wx_fmt_jpeg 38]: https://img-blog.csdnimg.cn/img_convert/3493a40a7af5051d2a703a87330a6690.png
[640_wx_fmt_jpeg 39]: https://img-blog.csdnimg.cn/img_convert/cd583d4013ad6111b1a0912faf155513.png
[640_wx_fmt_jpeg 40]: https://img-blog.csdnimg.cn/img_convert/0e513d3ed73bf3f46e742bd304a4a583.png
[640_wx_fmt_jpeg 41]: https://img-blog.csdnimg.cn/img_convert/600fc0588e4b2335c3aeed558bd11926.png
[640_wx_fmt_jpeg 42]: https://img-blog.csdnimg.cn/img_convert/ef862a44bcd10eaf5dfdd415b26a1d0f.png
[640_wx_fmt_jpeg 43]: https://img-blog.csdnimg.cn/img_convert/f09998b401ab02c66433f515d17a7b3b.png
[640_wx_fmt_jpeg 44]: https://img-blog.csdnimg.cn/img_convert/6db9ab418d3cb62e086a799e4d0a69a1.png
[640_wx_fmt_jpeg 45]: https://img-blog.csdnimg.cn/img_convert/aece74145329ce87f3af57ec8f72c5e7.png
[640_wx_fmt_jpeg 46]: https://img-blog.csdnimg.cn/img_convert/9fb2f928e0f8b0d952af29c716e76c25.png
[640_wx_fmt_jpeg 47]: https://img-blog.csdnimg.cn/img_convert/1d0085bae5fa630ecc73217d5bff7793.png
[640_wx_fmt_jpeg 48]: https://img-blog.csdnimg.cn/img_convert/2a88b8f99b297942fe7f76909145a562.png
[640_wx_fmt_jpeg 49]: https://img-blog.csdnimg.cn/img_convert/a9c28fe5a54522900f9037ace984d59b.png
[640_wx_fmt_jpeg 50]: https://img-blog.csdnimg.cn/img_convert/8abff6c54d3154f0a050439937757d1f.png
[640_wx_fmt_jpeg 51]: https://img-blog.csdnimg.cn/img_convert/7196dba98dd94f43031c2b0d9f4ac6d9.png
[640_wx_fmt_jpeg 52]: https://img-blog.csdnimg.cn/img_convert/6dbe891fd206ce444508cde5d5a1d4c2.png
[640_wx_fmt_jpeg 53]: https://img-blog.csdnimg.cn/img_convert/1668afe20498d82e1e70e096517da3f1.png
[640_wx_fmt_jpeg 54]: https://img-blog.csdnimg.cn/img_convert/4a8c5162a20bf28c7003f381b03a9e2f.png
[640_wx_fmt_jpeg 55]: https://img-blog.csdnimg.cn/img_convert/73961bbabe5a6117ecb8ff2a3f746308.png
[640_wx_fmt_jpeg 56]: https://img-blog.csdnimg.cn/img_convert/a8b413fd8b6ea4c5c4e6b10d825030b3.png
[640_wx_fmt_jpeg 57]: https://img-blog.csdnimg.cn/img_convert/4b33444052b8897a8ae98e98b2ee39b8.png
[640_wx_fmt_jpeg 58]: https://img-blog.csdnimg.cn/img_convert/09ec5fb554712f07790ac779708782b2.png
[640_wx_fmt_jpeg 59]: https://img-blog.csdnimg.cn/img_convert/1c99bb46ccee18df1d6600a4d68548b3.png
[640_wx_fmt_jpeg 60]: https://img-blog.csdnimg.cn/img_convert/5fce98fcf8de7482308ceeaaf5b09331.png
[640_wx_fmt_jpeg 61]: https://img-blog.csdnimg.cn/img_convert/38b1edd0082c84a1c627a89f50448656.png
[640_wx_fmt_jpeg 62]: https://img-blog.csdnimg.cn/img_convert/cdf8464206d51a3f5f363ca703020efa.png
[640_wx_fmt_jpeg 63]: https://img-blog.csdnimg.cn/img_convert/4ce44b8d6351ddd09b15787b0b8052e2.png
[640_wx_fmt_jpeg 64]: https://img-blog.csdnimg.cn/img_convert/95b6f07e2d5ff4c658951ea49d7501c2.png
[640_wx_fmt_jpeg 65]: https://img-blog.csdnimg.cn/img_convert/d7182d4b63a206b96da15cef61122b8e.png
[640_wx_fmt_jpeg 66]: https://img-blog.csdnimg.cn/img_convert/b65994fc5cad4220c3e4b21eac454af3.png
[640_wx_fmt_jpeg 67]: https://img-blog.csdnimg.cn/img_convert/d9d093840a9dd6b5c1514dd0a340bfad.png
[640_wx_fmt_jpeg 68]: https://img-blog.csdnimg.cn/img_convert/e7dd2686afe18fc85ef8c3996bf78beb.png
[640_wx_fmt_jpeg 69]: https://img-blog.csdnimg.cn/img_convert/339f9f4d3fe52370725a2717d5a75db8.png
[640_wx_fmt_jpeg 70]: https://img-blog.csdnimg.cn/img_convert/e101124c6e0b149e0ce27b870ea06e4e.png
[640_wx_fmt_jpeg 71]: https://img-blog.csdnimg.cn/img_convert/cc1340bf2efa9f0cec79ff722e611b29.png
[640_wx_fmt_jpeg 72]: https://img-blog.csdnimg.cn/img_convert/58572cc72b591556090d2dd31c055736.png
[640_wx_fmt_jpeg 73]: https://img-blog.csdnimg.cn/img_convert/04b9f6046232101fb3f581e5292f1e5a.png
[640_wx_fmt_jpeg 74]: https://img-blog.csdnimg.cn/img_convert/1c2ba3739673e82dd680ecd956b138c3.png
[640_wx_fmt_jpeg 75]: https://img-blog.csdnimg.cn/img_convert/6ff521a64c74425827d3703fc6362287.png
[640_wx_fmt_jpeg 76]: https://img-blog.csdnimg.cn/img_convert/987db4f7471950daae2ad615daba9253.png
[640_wx_fmt_jpeg 77]: https://img-blog.csdnimg.cn/img_convert/d61a3834c01f50c19be3f537582d5430.png
[640_wx_fmt_jpeg 78]: https://img-blog.csdnimg.cn/img_convert/f101e503d80902d49633de5d79779653.png
[640_wx_fmt_jpeg 79]: https://img-blog.csdnimg.cn/img_convert/00d1a86c5a17200b76a6414cbdee6263.png
[640_wx_fmt_jpeg 80]: https://img-blog.csdnimg.cn/img_convert/4df518f13645cd02fb801deb48169350.png
[640_wx_fmt_jpeg 81]: https://img-blog.csdnimg.cn/img_convert/d12f51c953c7e02f18d36602f9f794e6.png
[640_wx_fmt_jpeg 82]: https://img-blog.csdnimg.cn/img_convert/578d781f565a0241bec1cfae704b0532.png
[640_wx_fmt_jpeg 83]: https://img-blog.csdnimg.cn/img_convert/60178fead6c0bfe23723e676032ecc4e.png
[640_wx_fmt_jpeg 84]: https://img-blog.csdnimg.cn/img_convert/5174e572c54d841933de519e7d19bf64.png
[640_wx_fmt_jpeg 85]: https://img-blog.csdnimg.cn/img_convert/583bbcee5a922b088603c89436428a3b.png
[640_wx_fmt_jpeg 86]: https://img-blog.csdnimg.cn/img_convert/fdbeca90b355f8e9cff8ed781409bc9a.png
[640_wx_fmt_jpeg 87]: https://img-blog.csdnimg.cn/img_convert/eb91d680ec7937cd41087133b537b531.png
[640_wx_fmt_jpeg 88]: https://img-blog.csdnimg.cn/img_convert/3218ae59875c25b550590e3c89ef9121.png
[640_wx_fmt_jpeg 89]: https://img-blog.csdnimg.cn/img_convert/ea6b25aef62974f297a4d18a4ef79751.png
[640_wx_fmt_jpeg 90]: https://img-blog.csdnimg.cn/img_convert/4a7d06bce177873c575dca306ebe6a4d.png
[640_wx_fmt_jpeg 91]: https://img-blog.csdnimg.cn/img_convert/3d9f7b6f9be3e1f90573cc28ee77cf24.png