面试题学习笔记 | 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+ 树作为多叉平衡搜索树,会通过索引键值进行二分查找,逐层向下定位到对应的叶子节点
找到叶子节点后,叶子节点中存储了多行数据,这些数据按组排列,并通过单向链表连接。每个叶子节点内的页目录结构分成多个槽,每个槽指向该组中最大的记录,因此可以通过二分查找进一步定位到具体的数据行
总结来说,查询过程通过两次二分查找实现:
第一次通过二分法查找到对应的叶子节点
第二次通过二分法在叶子节点内查找到实际的数据行