个人技术分享

必须记住我们学习的时间是有限的。时间有限，不只由于人生短促，更由于人事纷繁。我们就应力求把我们所有的时间用去做最有益的事情。

备案号：鄂ICP备2023027962号-1

深入解析B树：数据结构、存储结构与算法优势

B树是一种自平衡的树数据结构，专门用于保持已排序的数据，并允许以对数时间复杂度进行搜索、顺序访问、插入和删除。每个节点最多有 M 个子节点。每个节点最少有 [M/2] 个子节点。根节点至少有两个子节点，除非树只有一个节点。所有叶子节点都在同一层次。一个节点的键值个数为 k，满足 [M/2] − 1 ≤ k ≤ M − 1。

【面试八股总结】MySQL索引（二）：B+树数据结构、索引使用场景、索引优化、索引失效

B 树是一个，每一个节点最多可以包括 M 个子节点，M 称为 B 树的阶，所以 B 树就是一个多叉树。叶子节点（最底部的节点）才会存放实际数据（索引+记录），非叶子节点只会存放索引；所有索引都会在叶子节点出现，叶子节点之间构成一个有序链表；非叶子节点的索引也会同时存在在子节点中，并且是在子节点中所有索引的最大（或最小）。非叶子节点中有多少个子节点，就有多少个索引；

[每周一更]-(第99期)：MySQL的索引为什么用B+树？

B+树通过将数据存储在叶子节点并使用链表连接叶子节点，实现了高效的范围查询和排序操作，同时减少了磁盘I/O操作的次数，提供了稳定的查询性能。理解为什么MySQL选择使用B+树而不是B树或其他树结构，首先需要深入了解B+树和B树的特性及其在数据库检索中的表现。B+树：在B树的基础上，将非叶节点改造为不存储数据的纯索引节点，进一步降低了树的高度；红黑树：通过舍弃严格的平衡和引入红黑节点，解决了AVL旋转效率过低的问题，但是在磁盘等场景下，树仍然太高，IO次数太多；各种树解决的问题以及面临的新问题。

B+树(Tree)

相对于B树，在内部节点中关键字的个数与其子树的个数相同，磁盘块上少了关键字代表的文件地址，所以在总数据量一定的情况下，单个磁盘块可以容纳更多的关键字，更多的节点指针，减少了数据从磁盘块读入到内存的次数(I/O读写次数降低)，提高了磁盘IO性能。表面上来看B+树会变胖，树的高度变低。更有利于对数据库的扫描 B树在提高了磁盘IO性能的同时并没有解决元素遍历效率低下的问题，而B+树只需要遍历叶子节点就可以解决对全部关键字信息的扫描，所以对于数据库中频繁使用的range query，B+树有着更高的性能。