type
Post
status
Published
date
Oct 11, 2026
slug
sql
summary
tags
技术探索
category
icon
password
以常用的 InnoDB 为例，主键索引和普通二级索引使用 B+ 树：非叶节点负责导航，叶子节点保存索引记录，叶子页按顺序连接。
选择它的核心原因是：树矮、磁盘 I/O 少，范围查询方便。
对比结构 | 为什么 B+ 树更适合 |
二叉搜索树、AVL、红黑树 | 每个节点最多两个分支，数据多时树较高；B+ 树一个节点有很多分支，树更矮，通常需要访问的页更少。普通二叉搜索树还可能退化成链表。 |
B 树 | 内部节点也存数据记录；B+ 树非叶节点只存键和子页指针，能容纳更多分支，叶子页链表也让范围扫描更方便。 |
哈希索引 | 等值查询快，但不支持有序的范围扫描和排序；B+ 树能兼顾这些需求。 |
什么是B+树？
B+ 树是一种平衡的多叉搜索树：上层节点负责导航，叶子节点保存索引记录，叶子页按顺序连接。
- 非叶节点： 只存键和子节点指针，能容纳很多分支，让树更矮、减少磁盘读页。
- 叶子节点： 保存索引记录。例如 InnoDB 主键索引的叶子节点保存整行数据。
- 叶子页链表： 定位到范围起点后，就能沿链表扫描，方便范围查询。blog.jcole.us
什么是B树？
相比B+树，非叶子节点会存具体数据，叶子节点没有用有序链表相连
什么是二叉搜索树
二叉搜索树（BST）每个节点存一个键，最多两个子节点，左子树更小、右子树更大。
本身不保证平衡，可能退化成链表。
什么是红黑树？
红黑树是一种自平衡的二叉搜索树，通过给节点标记红、黑两种颜色，并进行变色和旋转，防止树退化成链表。
- 怎么查： 左子树的值更小，右子树的值更大，每次比较后选择一边继续找。
- 怎么保持平衡： 插入、删除后，如果违反颜色规则，就通过变色和旋转调整结构，限制树的高度。
- 优点： 查找、插入、删除的时间复杂度都能保持 O(log n)，适合内存中频繁增删的有序数据。
- 为什么 MySQL 不选它： 每个节点最多两个分支，数据多时树较高；B+ 树分支更多、树更矮，更适合减少磁盘读页次数。
MySQL底层怎么查一条数据？
例如查：
根页和中间页像两级目录，告诉你“该去哪个下一层页”；叶子页才保存实际订单数据。
① 先看根页的目录：
ID 范围 | 去哪个中间页 |
4900001～5000000 | 中间页 A |
5000001～5100000 | 中间页 B |
5100001～5200000 | 中间页 C |
要找的
5000001 属于第二个范围，所以直接进入 中间页 B。② 再看中间页 B 的目录：
ID 范围 | 去哪个叶子页 |
5000001～5000100 | 叶子页 1 |
5000101～5000200 | 叶子页 2 |
5000201～5000300 | 叶子页 3 |
5000001 属于第一个范围，所以进入 叶子页 1。③ 到达叶子页 1：
这里真正存着
5000001、5000002……5000100 对应的订单记录，找到起点后，就开始顺序读取。目录中的范围是由索引键划分出来的，跳转靠的是子页指针。
分享