MySQL面试题

B+树与B树差异

所有的数据都会出现在叶子节点。

叶子节点形成一个单向链表。

非叶子节点仅仅起到索引数据作用，具体的数据都是在叶子节点存放的。

B+树缺陷：

B+树最大的性能问题是会产生大量的随机IO，随着新数据的插入，叶子节点会慢慢分裂，逻辑上连续的叶子节点在物理上往往不连续，甚至分离的很远，但做范围查询时，会产生大量读随机IO。

对于大量的随机写也一样，举一个插入key跨度很大的例子，如7->1000->3->2000 ... 新插入的数据存储在磁盘上相隔很远，会产生大量的随机写IO。

MySQL对B+树进行改进

MySQL数据库在进行数据操作时常会使用范围的查找，例如使用select*from*where x(字段)<y，原生B+树的叶子节点只有向右的指针，同时B+树底层排序默认为从小到大，这时候在进行x<y的操作时,唯有从Root节点逐个搜索比较满足小于y这个数值的数据才能遍历到所有数据，这非常浪费计算机的时间和性能。

而改进后的B+树，在进行范围搜索时双向指针可以完美地解决逆向搜索带来的时间和性能浪费的问题，当我们需要搜索一个满足x(字段)<y条件时，只需要找到小于y的最大值然后通过双向循环链表向前搜索便可以得到所有数据。同时在对z<x(字段)<y时，只需要定向到一个满足该条件的任何一个值，然后通过链表双向循环搜索便可以极快地搜索出需要的值。

[1]林荣杭,刘小英.MySQL索引改进的B+树的研究[J].电脑知识与技术,2022,18(16):12-13+18.DOI:10.14004/j.cnki.ckt.2022.1080

[2]黑马程序员