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

朱雀 2023-05-31 15:26 134阅读 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]: /images/20230531/514a7dfd348146748d57248489beb59b.png
[640_wx_fmt_jpeg 4]: /images/20230531/c06ff5b07c5b4b3389ecebbf8c2abfc4.png
[640_wx_fmt_jpeg 5]: /images/20230531/abb245fdb60b44ba8f5b51bc178c00fd.png
[640_wx_fmt_jpeg 6]: /images/20230531/e8c9e04c85204c2b8bd41f0b81c1367f.png
[640_wx_fmt_jpeg 7]: /images/20230531/5f3789c91dea45da80ea8cbc3e6943c5.png
[640_wx_fmt_jpeg 8]: /images/20230531/a47a6ac951be44a6863d6322c6c03272.png
[640_wx_fmt_jpeg 9]: /images/20230531/4f1ad84daf824af6807519985def612f.png
[640_wx_fmt_jpeg 10]: /images/20230531/a73d5898c024417cb2ddba9a4c1ad38a.png
[640_wx_fmt_jpeg 11]: /images/20230531/1b42d061ce4347c988b468bb4967ea22.png
[640_wx_fmt_jpeg 12]: /images/20230531/203df3403cee4d219946ed9dc374d144.png
[640_wx_fmt_jpeg 13]: /images/20230531/7952236dd8b34594971e9abf013c4e5d.png
[640_wx_fmt_jpeg 14]: /images/20230531/58d23e831a1b49f692e2e4f897d1b641.png
[640_wx_fmt_jpeg 15]: /images/20230531/37c156f0276842a1910fe859ba1d9aac.png
[640_wx_fmt_jpeg 16]: /images/20230531/e4fc920971764d5caef724de5ca61dec.png
[640_wx_fmt_jpeg 17]: /images/20230531/cad2906ef589436cbdff6e0c59e32520.png
[640_wx_fmt_jpeg 18]: /images/20230531/232a70786ced479f9306838af513e3e3.png
[640_wx_fmt_jpeg 19]: /images/20230531/4e27185cb32148fbb973cebe06b4f700.png
[640_wx_fmt_jpeg 20]: /images/20230531/e3f6684e5b9a4f4a9c915bae0da4cbf5.png
[640_wx_fmt_jpeg 21]: /images/20230531/a02f1180a26841a9baebd585159ab4ab.png
[640_wx_fmt_jpeg 22]: /images/20230531/c58d10dadca24afb96b6544e2087a2bd.png
[640_wx_fmt_jpeg 23]: /images/20230531/80c709b11ef54cf88dc5b07931b6f5d2.png
[640_wx_fmt_jpeg 24]: /images/20230531/ea3cfaefcbdc4a67b3337a92fb23cb05.png
[640_wx_fmt_jpeg 25]: /images/20230531/e1739fe34bec4cb4babcba01043a5854.png
[640_wx_fmt_jpeg 26]: /images/20230531/e0b82f2b5b284d6eae8054216ab14e28.png
[640_wx_fmt_jpeg 27]: /images/20230531/6210d780cd84452b88109afa54b961a2.png
[640_wx_fmt_jpeg 28]: /images/20230531/6963cb6e21a84b9eb2a6e262ee9e996c.png
[640_wx_fmt_jpeg 29]: /images/20230531/10fe4ceab4ed4835816dcc80fe13b5ca.png
[640_wx_fmt_jpeg 30]: /images/20230531/310acae220e54304b4a5135cc7c62471.png
[640_wx_fmt_jpeg 31]: /images/20230531/ca89f49f66e84a898a83b9afa9e9b1a7.png
[640_wx_fmt_jpeg 32]: /images/20230531/881379e7565244deb56b4b66e6064eb3.png
[640_wx_fmt_jpeg 33]: /images/20230531/c15ba8d3c39e416ab8a5e6d4b9ae5895.png
[640_wx_fmt_jpeg 34]: /images/20230531/56379116529a439fa75aaf481d7b322c.png
[640_wx_fmt_jpeg 35]: /images/20230531/2e991e89692f404c979de35d5382c327.png
[640_wx_fmt_jpeg 36]: /images/20230531/9da39b19c38c469f89e0af3744bdb77f.png
[640_wx_fmt_jpeg 37]: /images/20230531/bee9213667ec45c39fc6ffe4978b548c.png
[640_wx_fmt_jpeg 38]: /images/20230531/de5e754d3c904a6ba0ec1876c2b3e429.png
[640_wx_fmt_jpeg 39]: /images/20230531/63fe1b9f68654722b366df40f195cbe4.png
[640_wx_fmt_jpeg 40]: /images/20230531/b4d68c8452ed41829e949611ed9d6726.png
[640_wx_fmt_jpeg 41]: /images/20230531/f1cdd22a24814f9c81ea1a00adb42174.png
[640_wx_fmt_jpeg 42]: /images/20230531/02d4d3d9bd854d17a52da1dbdde79977.png
[640_wx_fmt_jpeg 43]: /images/20230531/52088e19b2b1487981ee190560641844.png
[640_wx_fmt_jpeg 44]: /images/20230531/34e8b2c8b1c34666b2a4981088a44457.png
[640_wx_fmt_jpeg 45]: /images/20230531/b743e5c0b9714b83b9ed086577729dff.png
[640_wx_fmt_jpeg 46]: /images/20230531/f91842a195754fdfbaead6c86e1b8c15.png
[640_wx_fmt_jpeg 47]: /images/20230531/4fc29cae870f4e368e321f4b036f4f34.png
[640_wx_fmt_jpeg 48]: /images/20230531/fed52394e9844f9888437864cb7d5564.png
[640_wx_fmt_jpeg 49]: /images/20230531/4de7f35d0bbf4251931d42304d132bc5.png
[640_wx_fmt_jpeg 50]: /images/20230531/90a9bc3e5fa34ebd846c9adb56fd9d1e.png
[640_wx_fmt_jpeg 51]: /images/20230531/ceb31dced2cc4432b6c1328d7011f63e.png
[640_wx_fmt_jpeg 52]: /images/20230531/c0f0149880df45a798b0b5c5083d4ac0.png
[640_wx_fmt_jpeg 53]: /images/20230531/4871a8913b744259b2d7abcf67f42db3.png
[640_wx_fmt_jpeg 54]: /images/20230531/c77266f1d767448eb6789055c0c948ea.png
[640_wx_fmt_jpeg 55]: /images/20230531/e54b2ad4be8446d18f141ba22776390f.png
[640_wx_fmt_jpeg 56]: /images/20230531/f44d2540acdb4031b7e6a2208f8dc431.png
[640_wx_fmt_jpeg 57]: /images/20230531/849ba7b9133341a4bf4e4732afc9195c.png
[640_wx_fmt_jpeg 58]: /images/20230531/c248c730864240ca990c7c238c672fea.png
[640_wx_fmt_jpeg 59]: /images/20230531/964436d300974d33959cd584cfc689f5.png
[640_wx_fmt_jpeg 60]: /images/20230531/4af670bb7d33455d8d52aed50b83bc72.png
[640_wx_fmt_jpeg 61]: /images/20230531/140e6d8d5ff5477cb91b4ecbc5afbc59.png
[640_wx_fmt_jpeg 62]: /images/20230531/bbf2ce9d739d45e39987e4c4374ef658.png
[640_wx_fmt_jpeg 63]: /images/20230531/0576dcb993264c128e4c98597eabf56c.png
[640_wx_fmt_jpeg 64]: /images/20230531/55996fecf4af48adaabaceb4256f2623.png
[640_wx_fmt_jpeg 65]: /images/20230531/2f513421c26b495db49ef571b3fc8f9d.png
[640_wx_fmt_jpeg 66]: /images/20230531/f1e844d506dd475686ab9241c3ace887.png
[640_wx_fmt_jpeg 67]: /images/20230531/ed7d80c4caf74951810c839f1889d1e3.png
[640_wx_fmt_jpeg 68]: /images/20230531/fa34b69add8d4b59a46b3de517add897.png
[640_wx_fmt_jpeg 69]: /images/20230531/cdc3aba909694482b495ae1a16716781.png
[640_wx_fmt_jpeg 70]: /images/20230531/79795472c8bd4355bf9132d803a71afc.png
[640_wx_fmt_jpeg 71]: /images/20230531/b3df1c909d8042fca7acddf0f3d8955a.png
[640_wx_fmt_jpeg 72]: /images/20230531/5392356f1c5a4fa69122184f775565f0.png
[640_wx_fmt_jpeg 73]: /images/20230531/0a1f6065f1dc4eff89d9da7489875602.png
[640_wx_fmt_jpeg 74]: /images/20230531/2b512d92f9e24206978077d12fa5288a.png
[640_wx_fmt_jpeg 75]: /images/20230531/54ad6b2f66c54f16aed8d5c7f7fbcbf4.png
[640_wx_fmt_jpeg 76]: /images/20230531/599a2fcbc56b48119ab9ea2b1db44b28.png
[640_wx_fmt_jpeg 77]: /images/20230531/a47bf160ee1f49c3a26aaf7bb7a52091.png
[640_wx_fmt_jpeg 78]: /images/20230531/f9de5402933741dfa54f5114c5351f34.png
[640_wx_fmt_jpeg 79]: /images/20230531/429d2f29718549a8a601aac718621e61.png
[640_wx_fmt_jpeg 80]: /images/20230531/270e08c66c11471594ce857af4089cfe.png
[640_wx_fmt_jpeg 81]: /images/20230531/4c2ef97ce69844fc96ed0347ac5925f8.png
[640_wx_fmt_jpeg 82]: /images/20230531/1de1e354e1204e8894d0f26e9ddb6f74.png
[640_wx_fmt_jpeg 83]: /images/20230531/e43d76e2624846dcba6d94efdbe54215.png
[640_wx_fmt_jpeg 84]: /images/20230531/47470bad750c4322af6e861891c1b1b9.png
[640_wx_fmt_jpeg 85]: /images/20230531/bb24114c08ab4d6eabea3a26c52dbb2f.png
[640_wx_fmt_jpeg 86]: /images/20230531/fb1e344c8b5346be904ead82ac8cfe09.png
[640_wx_fmt_jpeg 87]: /images/20230531/8637109b5e1146de9b396b90b8948832.png
[640_wx_fmt_jpeg 88]: /images/20230531/475b9961862342feb8ca913dcb0ef645.png
[640_wx_fmt_jpeg 89]: /images/20230531/fd72607482d44487b1cdebaf7458f054.png
[640_wx_fmt_jpeg 90]: /images/20230531/033661ed94514ba8ac0b17b6d403349a.png
[640_wx_fmt_jpeg 91]: /images/20230531/b4f144b6392e4562b15df944b2cedb9b.png