面试题学习笔记 | MySQL B+ 树索引
为什么 MySQL 使用 B+ 树作为索引结构？
性能：
B+ 树是一种多叉平衡搜索树结构，每个叶子节点到根节点的路径长度相同，因此查找效率稳定。在插入和删除时，B+ 树会通过分裂和合并操作来保持树的平衡。其设计特点使得删除操作能够减少结构调整，从而提高效率。B+ 树的增、删、改、查等操作的时间复杂度为 O(log n)
树的高度增长较慢，磁盘 I/O 次数较少：
与红黑树等二叉搜索树不同，B+ 树是多叉树，每层可以容纳更多的节点。此外，B+ 树的非叶子节点仅存储索引键和指向下一个节点的指针，而叶子节点才存储完整的数据。这样一来，B+ 树可以在内存中存放更多的索引页，从而减少了搜索过程中的磁盘 I/O 次数
天然支持范围查询和区间查找：
B+ 树的叶子节点按照索引顺序排列，并通过双向链表连接。因此，一旦定位到目标范围的叶子节点，就可以快速遍历其余节点，极大地提高了范围查询的效率
三层 B+ 树能存多少数据？
在 InnoDB 中，默认的数据页大小为 16 KB，叶子节点存储数据行，非叶子节点则存储索引和指向下一节点的指针
具体能存储多少数据取决于数据的实际大小，以下是一个假设的计算：
假设每个叶子节点存储的数据行大小为 1 KB
假设每个中间非叶子节点的索引占用 8 字节（bigint 类型），每个指针占用 6 字节
根据这些假设，我们可以做如下计算：
每个中间层（第 1 和第 2 层）可以指向 1170 个叶子节点：
(16 KB × 1024) / (6 字节 + 8 字节) = 1170 个叶子节点每个叶子节点（第 3 层）可以存储 16 条数据：
16 KB / 1 KB = 16 条数据
最终，三层 B+ 树可以存储的数据量为：
1170 × 1170 × 16 = 21,902,400 条数据，约为 200 万条
B+ 树查询数据的全过程
B+ 树的数据存储在数据页中，InnoDB 中每个数据页的默认大小为 16 KB。在非叶子节点中存储索引键值和指向下一层节点的指针，而叶子节点存储实际的数据，并且可以存储多行数据，通过页目录实现快速检索
B+ 树作为多叉平衡搜索树，会通过索引键值进行二分查找，逐层向下定位到对应的叶子节点
找到叶子节点后，叶子节点中存储了多行数据，这些数据按组排列，并通过单向链表连接。每个叶子节点内的页目录结构分成多个槽，每个槽指向该组中最大的记录，因此可以通过二分查找进一步定位到具体的数据行
总结来说，查询过程通过两次二分查找实现：
第一次通过二分法查找到对应的叶子节点
第二次通过二分法在叶子节点内查找到实际的数据行