要说数据库面试里出现频率最高的数据结构B树和B树敢说第二没人敢说第一。不管是聊InnoDB索引、聊磁盘IO还是聊千万级数据量的SQL优化最后都绕不开这个多路平衡树家族。但说句实话我见过太多人能把“B树叶子节点用链表串起来”这种结论背得滚瓜烂熟真让他从头写一遍插入、分裂、删除当场就露馅了。这篇文章把B树和B树从“为什么要设计成这样”一路讲到“代码到底怎么写”不绕弯子、不堆概念。适合准备面试的工程师、正在啃数据库原理的学生以及所有想彻底搞懂索引底层逻辑的开发者。理解这套东西之后再看EXPLAIN、再看存储引擎源码你会觉得整个世界都清晰了很多。1. 从需求出发数据库为什么非它不可1.1 一次磁盘IO到底有多贵先不谈树聊聊一个最容易被忽略的事实内存和磁盘的速度差。现在的CPU L1缓存延迟大约是1纳秒内存访问大约是100纳秒而一块普通机械硬盘的随机IO大概是10毫秒就算是NVMe SSD一次随机读也要几十微秒到一百微秒。10毫秒和100纳秒之间差了整整十万倍。这意味着数据库每次索引查找只要隔三差五跑去磁盘碰运气哪怕多一次IO整个查询的耗时就会肉眼可见地恶化。我这里特别喜欢拿图书馆打比方CPU缓存是你手边的那一格书架内存是你脑子里的记忆磁盘则是另一个城市里的书库。你查一本书内存里没有就得坐高铁去隔壁城市取。设计索引数据结构本质上就是在设计“怎样用最少次数的高铁往返”拿到目标数据。数据库管理数据的基本单位是页不是单条记录。InnoDB默认的页大小是16KB你想读一行数据也得把整页数据从磁盘捞进来。所以数据结构设计有两条铁律一是节点尺寸尽量和磁盘页对齐一次IO读满一整页二是树的高度必须压到极致让查找路径上的节点访问次数越少越好。B树家族就是沿着这个思路演化出来的。1.2 二叉搜索树为什么撑不住既然目标是降低树高天然的想法是让一个节点多装几个key。先看看传统的平衡二叉树红黑树、AVL树每个节点只存一个key最多两个孩子。拿100万条数据来说最理想情况下AVL树高约log2(1000000)≈20层。听起来不多是吧可如果每访问一层都意味着一次磁盘IO20次IO是什么概念普通的SSD一次随机读约50微秒20次就是1毫秒换成机械硬盘20次乘以10毫秒直接就是200毫秒级别。这还只是理想情况红黑树工程实现的高度往往能达到2log2(N)100万数据能蹿到40层附近灾难。更麻烦的是平衡二叉树为了维持平衡插入删除要频繁旋转。旋转在内存里是几个指针的调整但数据落到磁盘上就意味着索引节点对应的页被反复重写缓存命中率很不好看。反过来如果做一棵又大又扁的树每个节点能装几百上千个key树高瞬间降到个位数。这就是多路搜索树的思想把二叉变成m叉用“单节点容量”换“树高”。B树就是这个思想的经典落地m阶B树的m决定了每个节点能放几个key和孩子指针。需要补充的是红黑树本身在纯内存里非常优秀C的std::map、Java的TreeMap都靠它。它的劣势只在磁盘场景下被放大。所以面试里开口就说“红黑树不如B树”其实不严谨后面我在第五部分会讲清楚两种结构的主场各自在哪。1.3 B树家族的整体设计哲学B树家族的核心设计哲学我用四个词概括多路、平衡、有序、页对齐。多路是指一个节点能存多个key。假设一棵100阶B树节点可以放99个key和100个孩子指针100万条数据最坏只需要几层就能完成查找。平衡指的是所有叶子节点必须落在同一层保证任意一条查找路径长度一致不会出现某些数据快、某些数据慢的“深井”。有序指的是每个节点内部的key按升序排列子树区间和key严格对应精确查找和范围查找都能用二分思路加速。页对齐是工程层面的关键节点大小刻意设计成磁盘页的整数倍一次IO刚好读一整页。这里有个关键点B树和B树都是“所有叶子在同一层”的平衡多路查找树所以面试里经常被混着聊。但真正让数据库选择B树而不是B树的是在B树基础上做了几个非常精妙的结构改动。我们先把B树本身讲透再往B树走。2. B树原理拆解定义、插入、删除与树高账本2.1 一棵m阶B树的定义一棵m阶B树满足下面五个性质每个节点最多有m棵子树。根节点至少有两棵子树除非它本身就是叶子。除根节点外每个非叶子节点至少有ceil(m/2)棵子树。有k棵子树的非叶子节点恰好有k-1个key所有key升序排列。所有叶子节点都在同一层。为什么要强制“至少ceil(m/2)棵子树”这是为了防止树退化成链表。如果没有这个下限理论上你可以写一棵“每个节点只有1个key”的B树那它跟二叉搜索树没有任何区别树高优势全没了。下限保证了即使节点稀疏树高最多也不过是log_{m/2}(N)级别依然够矮。举个例子3阶B树也叫2-3树每个节点最多2个key非根节点至少1个key。6阶B树每个节点最多5个key3个子树指针非根节点至少3个子树。这个“一半下限”是B树所有旋转、借位、合并操作的总根源后面删除算法你会在每个分支里看到它的影子。2.2 查找、插入、删除三板斧查找的逻辑最直观。从根开始在节点内部用顺序或二分找到目标key所在的区间沿着对应的孩子指针往下走直到叶子。如果叶子层有目标key就返回没有就说明不存在。插入逻辑的核心是“先插后裂”。先在叶子节点插入新key保持节点内key有序。插入后如果key个数不超过m-1万事大吉。一旦超过m-1节点就超载了必须做分裂取中间位置的key上提到父节点原节点一分为二。如果父节点因为这个新上提的key也超载了就继续向上分裂最坏情况一路裂到根。根裂开后树的高度才增加一层。我拿3阶B树插入1到6演示一遍你立刻能感受到分裂的节奏。插入1、2时根就是叶子节点key是[1,2]插入3时节点超载[1,2,3]取中间key2上提成根左右孩子分别[1]和[3]插入4时走到右叶[3,4]不超载根key变为[2]右叶为[3,4]插入5时右叶[3,4,5]超载中间key4上提到根根变成[2,4]此时两个叶子[3]和[5]再插入6继续往右叶[5,6]走。每一步都保证叶子在同一层树高始终保持矮胖。删除是B树里最折腾的操作核心策略是“能借就借借不到就合并”。删除叶子key后如果节点key数低于下限ceil(m/2)-1先看兄弟节点是否富余。富余的话从父节点借一个key下来兄弟的key上提补位这叫旋转。如果兄弟也不富余就把当前节点、兄弟节点和父节点中分在他们中间的那个key合并成一个节点父节点因此少了一个key可能又要递归往上触发新的借位或合并。最极端情况合并到根根空了树高减1。2.3 树高与磁盘IO的账本前面说的都是理论现在算一笔实账。假设磁盘页是16KBkey是8字节孩子指针是6字节那么每个节点大约能存16000/(86)≈1142个key。换句话说这是一个1000多阶的B树树高只有三四层。100万条数据根节点就能覆盖全部区间二层足够了。10亿条数据三层也顶天了。InnoDB里经常说“三层B树支撑十亿级别索引”说的就是这个账。查询一条记录理想情况下只需要2到3次磁盘IO一次读根页一次读中间页一次读叶子页剩下的都是内存里的二分查找。相比之下二叉树同样数据量要20多次IO高下立判。这账算完你也就明白了为什么所有数据库存储引擎都信仰“矮胖树”。矮是IO次数少胖是单节点信息量大。B树家族的每一步设计都是冲着这两个字去的。3. B树凭什么成为数据库事实标准3.1 相比B树它改了什么内节点不存数据B树和B树的根本差别一句话就能讲完B树的非叶子节点只存key和子树指针不存数据所有数据都沉到叶子节点上叶子之间用指针串成链表。就这么一个改动带来的连锁反应非常大。因为内节点不再背负value或行数据同样的16KB页能装的key数量大幅上升。还是刚才的账本如果内节点只存key和指针一组仍按14字节算能存1142个key如果还要存一个8字节的value一组就是22字节只能存700多个key差距接近一倍。树高又矮了一层IO又省了一次。还有一个容易被忽略的细节B树的叶子节点才是“数据层”所有查询都必须走到叶子层。B树呢运气好在内节点就命中数据路径短运气不好就得一路走到底。B树的做法是用“每次查询都走同样的路径长度”换“最坏情况也可预期”这对数据库来说极其宝贵。数据库要处理海量并发请求时延稳定比偶尔更快更重要。3.2 范围查询、页缓存和预读优势B树最让数据库欲罢不能的地方是它的范围查询能力。因为叶子节点之间有一根链表查“where age between 18 and 25”这种SQL只要先定位到起始叶子然后顺着链表一路扫过去就行几乎不需要回跳。B树就没有这个条件每个节点的数据分布在各层范围扫描要不断在树里上下折腾IO次数完全不可控。页缓存层面B树的内节点因为不存数据同等缓存容量下能缓存更多索引层热点索引页驻留内存的概率更高。预读机制也跟着受益存储引擎发现你在顺序扫描叶子链表会把相邻叶子页提前读入缓冲池你还没访问到数据已经在内存里等着了。MySQL InnoDB、PostgreSQL、MongoDB的默认索引实现全是B树不是偶然。范围查询、排序、分页这些高频SQL场景B树就是为它们量身定做的。3.3 和红黑树、LSM树的定位差异这里回应一下搜得特别多的一个问题“B树是红黑树吗”答案很简单不是。红黑树是二叉树属于内存数据结构服务的是std::map、TreeMap、Linux内核调度器这种纯内存场景B树是多路搜索树属于磁盘数据结构服务的是数据库索引这种以IO为主导的场景。两者的关键差异就是树高和节点容量。红黑树处理100万数据要20多层B树只要3层。但如果所有数据都在内存里层次差异没那么致命反而红黑树的指针跳转相对局部插入删除的旋转调整比B树的分裂合并简单得多。所以说在内存里做有序结构优先考虑红黑树或跳表在磁盘上做有序索引B树才是正经答案。至于LSM树那是RocksDB、LevelDB这类写多读少场景的选择——顺序写合并代替原地更新跟B树是另一套取舍。它们不是替代关系是不同负载下的不同解。面试被问到时能说出“B树适合读多写少、LSM适合写多读少”这一层就比背概念强很多。4. 手写一个简化版B树核心代码逐行拆解4.1 节点结构设计讲解原理用图最直观但只有自己动手写过一次很多细节才会真正刻进脑子里。我在这里用Python写一个教学版B树过滤并发、磁盘序列化这些工程噪音聚焦数据结构本身。每个节点叫BPlusNode内部有这几个字段keys存关键字列表如果是叶子节点values存对应的value如果是内部节点children存孩子指针叶子节点还有一个next指针用于范围扫描时的链表遍历。class BPlusNode: B树节点叶子节点用values存数据内部节点用children存子树指针 def __init__(self, order, is_leafTrue): self.order order # 阶数节点最多order棵子树 self.is_leaf is_leaf self.keys [] # key列表始终有序 self.children [] # 内部节点使用 self.values [] # 叶子节点使用 self.next None # 叶子链表指针节点维护一个max_keys变量等于order-1。在插入逻辑里一旦keys的长度超过max_keys就要触发分裂。4.2 查找和范围查询实现查找从根出发在内部节点依次比较key找出应该走的孩子。叶子层则遍历keys判断目标是否存在。class BPlusTree: def __init__(self, order4): self.order order self.max_keys order - 1 self.root BPlusNode(order, is_leafTrue) def find(self, key): node self.root while not node.is_leaf: i 0 while i len(node.keys) and key node.keys[i]: i 1 node node.children[i] for i, k in enumerate(node.keys): if k key: return node.values[i] return None这里内部节点的孩子选择逻辑要仔细讲一下。对每个内部节点的key它把区间切成len(keys)1段。查找时用key node.keys[i]做判断意思是只要目标key不小于当前keys[i]就往右子树继续找。走到叶子后keys列表中存储的是和值一一对应的key所以直接线性扫一下即可。范围查询在此基础上加一个链表遍历就行。先定位到不小于lo的那个叶子然后通过next指针向后扫直到超过hi或者链表结束。def range(self, lo, hi): node self.root while not node.is_leaf: i 0 while i len(node.keys) and lo node.keys[i]: i 1 node node.children[i] result [] while node: for k, v in zip(node.keys, node.values): if k hi: return result if k lo: result.append((k, v)) node node.next return result因为叶子keys是有序的所以一旦发现当前key已经大于hi直接返回结果即可不需要再看后面的节点。4.3 插入与分裂的完整流程插入是B树最核心的机制。整体策略是递归找到应该插入的叶子插入后检查是否超载超载就分裂分裂产生的中间key上抛给父节点父节点可能因此超载继续分裂上抛。def insert(self, key, value): split_result self._insert(self.root, key, value) if split_result is not None: mid_key, new_node split_result new_root BPlusNode(self.order, is_leafFalse) new_root.keys [mid_key] new_root.children [self.root, new_node] self.root new_root def _insert(self, node, key, value): if node.is_leaf: # 先在叶子层插入 i 0 while i len(node.keys) and key node.keys[i]: i 1 node.keys.insert(i, key) node.values.insert(i, value) if len(node.keys) self.max_keys: return node.split() return None i 0 while i len(node.keys) and key node.keys[i]: i 1 split_result self._insert(node.children[i], key, value) if split_result is None: return None mid_key, new_node split_result node.keys.insert(i, mid_key) node.children.insert(i 1, new_node) if len(node.keys) self.max_keys: return node.split() return Nonesplit函数负责把节点一分为二并返回上抛给父节点的中间key。这里要特别注意叶子节点和内部节点的差异叶子分裂时中间key的“副本”要留在右叶子内部节点分裂时中间key是要拿走供父节点使用的不能保留在两个孩子里。def split(self): mid len(self.keys) // 2 mid_key self.keys[mid] new_node BPlusNode(self.order, is_leafself.is_leaf) if self.is_leaf: new_node.keys self.keys[mid:] new_node.values self.values[mid:] self.keys self.keys[:mid] self.values self.values[:mid] new_node.next self.next self.next new_node return mid_key, new_node else: new_node.keys self.keys[mid 1:] new_node.children self.children[mid 1:] self.keys self.keys[:mid] self.children self.children[:mid 1] return mid_key, new_node为什么叶子分裂的mid_key要保留在右叶子而内部节点不保留因为B树的性质是内部节点的key只承担路由职责真正查找key时必须落到叶子层才算数。如果右叶子丢了mid_key那查询时就找不到这个值了反之保留一个副本并不违反有序性。主insert里的根分裂处理也很关键。当递归返回非空split结果说明根也超载了。这时创建一个新的根节点把中间key放进新根旧根和新分裂出的节点成为它的左右孩子树高增加一层。4.4 删除与合并的边界处理删除操作比插入麻烦我写一个教学级版本重点展示“借位合并”的骨架。整体策略是递归找到目标叶子删除key如果删除后节点key数量不足阈值就尝试向兄弟借key或者在父节点层面合并。def delete(self, key): self._delete(self.root, key) if not self.root.is_leaf and len(self.root.keys) 0: self.root self.root.children[0] def _delete(self, node, key): if node.is_leaf: if key not in node.keys: return False i node.keys.index(key) node.keys.pop(i) node.values.pop(i) return len(node.keys) self.min_keys() i 0 while i len(node.keys) and key node.keys[i]: i 1 if self._delete(node.children[i], key): # 孩子节点key数不够需要借位或合并 return self._borrow_or_merge(node, i) return False_borrow_or_merge是我特意留出来的一层封装完整实现要考虑先检查左兄弟、再检查右兄弟、都不够才合并。我建议你把它当作一个练习自己补全补完之后你对“节点占用率”“分裂合并抖动”这些概念会有特别深的体会。def min_keys(self): # 非根节点至少 ceil(order/2)-1 个key return (self.order 1) // 2 - 1 def _borrow_or_merge(self, parent, child_index): # TODO: 1. 尝试从左兄弟借key # TODO: 2. 尝试从右兄弟借key # TODO: 3. 都不够则与兄弟合并父节点删除一个key并递归调整 pass教学版可以直接把合并逻辑写死在本地但在工程级B树里借位和合并会牵扯到父节点key的下降、兄弟节点指针的更新、链表next的修正每一步都要谨慎。遇到删除操作导致根节点key清零时树高减一的逻辑也在这里处理。5. 工程落地内存与磁盘场景下的关键优化5.1 内存B树的缓存友好与并发设计前面聊的是磁盘场景现在切到纯内存场景。如果用B树做内存索引注意一个细节keys应该用连续数组存储比如C里的vector而不是链表式节点。原因很简单连续数组的相邻key在内存地址上也是相邻的CPU在加载第一个key时会把后面一连串key一起塞进缓存行。线性扫描几十个key其实比跳来跳去的链表节点快得多。但纯内存的有序K/V场景很多项目最终选了跳表比如Redis。为什么因为B树的插入和分裂会改变父子指针在并发写场景下要锁多个节点锁粒度不好控制跳表虽然平均高度略高但无锁实现相对成熟写入性能更好。也就是说B树在内存里最大的对手不是红黑树而是跳表。选择哪个取决于你对写并发和范围扫描哪个更看重。如果有人问我推荐哪种内存有序结构我的经验是读多写少、范围查询多优先B树写并发很高、实现简单优先优先跳表。清晰定义场景比一味追逐某个数据结构“高级”要重要得多。5.2 磁盘场景页大小、扇出与预读磁盘B树的核心设计几乎都围绕页大小展开。InnoDB默认16KB页用户也能配置成8KB或4KB。页大小变大单页能装的key变多扇出变大树高变小但代价是单次读取的内容变多点查询时浪费的带宽也变大。对HDD这种顺序读写性能远高于随机读写的介质来说大页更合适SSD对随机读没那么敏感小页也能接受。前面算过16KB页、8字节key加6字节指针扇出超过1100。这带来一个工程事实十亿条记录的普通表二级索引往往也是3层。这3层意味着一次B树查找只需要2到3次真正意义的磁盘IO加上缓冲池命中实际响应常控制在毫秒级。很多慢查询问题根本不是索引层数太多而是SQL写法让索引失效或者索引本身设计得不合理。预读是B树的隐性红利。你连续扫描叶子链表时存储引擎会按顺序把相邻页提前读入缓冲池比如InnoDB的线性预读检测到当前正在顺序读取时会自动把之后64个页甚至更多页一次性拉进内存。这种机制能把范围查询的速度提升一个数量级代价只是提前占用一部分缓冲池空间。5.3 填充因子、合并阈值和双向链表工程级B树还有三个参数值得你留意填充因子、合并阈值、双向链表。填充因子是指节点初始化时预留的空闲比例典型值是70%到80%。如果创建索引时指定了较低的填充因子批量导入数据时就不会立刻触发频繁分裂。数据库里做数据归档、夜间大批量写索引提前设置fillfactor70能显著减少后续的页分裂抖动。合并阈值一般和最小key数挂钩设置为order的一半左右。但真正生产环境里合并操作非常昂贵因为它会触发数据搬移和节点删除所以很多引擎宁可让节点暂时低于最小占用率也不急着合并。InnoDB的做法是删除记录时只打标记由后台purge线程异步清理这个设计就让“合并抖动”和“锁竞争”都变得没那么尖锐了。关于链表方向教材里常写单向链表但InnoDB的叶子节点实际上用双向链表。为什么要双向因为order by ... desc这种反向扫描以及一些需要从后往前回溯的查询场景双向都能高效处理。你看工程实现永远会为了具体业务多做几步优化。6. 常见问题与排查技巧实录6.1 为什么有索引却失效EXPLAIN实战排查很多开发者背了无数遍“最左前缀、函数索引”的规则真到线上慢查询依然一脸蒙。我的建议是任何SQL性能问题先跑EXPLAIN别凭感觉猜。举个例子。一张订单表有1000万行字段user_id、status、create_time索引只建了idx_user_id(user_id)。执行下面这条SQLSELECT * FROM orders WHERE user_id 1001 AND status 1 ORDER BY create_time DESC LIMIT 20;EXPLAIN结果可能是typerefkeyidx_user_idrows120000Extra里有Using filesort。这意味着MySQL用索引框定了某个用户的上万条记录然后全部取出来在内存临时文件里排序再取20条。实际耗时可能就几百毫秒但数据量再大几倍就会失控。优化方法是在联合索引里同时覆盖过滤和排序ALTER TABLE orders ADD INDEX idx_user_status_time (user_id, status, create_time);这下EXPLAIN的Extra会变成Using index condition不再filesortrows锐减。原理就是B树的底层结构天然有序联合索引的叶子节点先按user_id排、再按status排、最后按create_time排排序需求直接被索引顺序满足。这算是“让B树的叶子有序性干活”最典型的一课。6.2 那些年被面试官反复追问的对比题“B树为什么比B树更适合做数据库索引”我听到过很多版本的答案最核心的我认为是两个内节点不存数据带来的扇出提升以及叶子链表带来的范围查询能力。“B树是红黑树吗”真不是。红黑树是二叉平衡树用于内存B树是多路搜索树用于磁盘。差异的根源是访问介质的物理特性。空闲时可以做一个对比表格来整理结构节点键数典型树高(100万数据)使用场景红黑树1约20层内存map/setB树(order1000)9992到3层数据库索引跳表平均2层指针约20层Redis有序集合另一个高频题是“B树和B树能否互相替代”。如果场景是内存型字典用红黑树更省事如果场景是点查询多而且不做范围扫描B树不存多余value行理论上能让内节点存更多key但B树工程成熟度太高数据库普遍还是选B树。技术选型从来不是单纯的理论最优而是要综合工程生态。6.3 InnoDB的聚簇索引和二级索引叶子节点里到底放着什么InnoDB里主键索引叫聚簇索引叶子节点的value就是整行数据二级索引的叶子节点value存的是主键值。这个设计非常巧妙用二级索引查到主键后还要再回聚簇索引查一次这个过程叫回表。所以“覆盖索引”优化才那么有用。比如查询只要求select user_id和status而联合索引刚好包含这两个字段那二级索引的叶子就能直接给出结果根本不用回表。这就是EXPLAIN里Using index的含义。反观MyISAM索引和表数据分开存放索引叶子存的是行指针通常是记录在文件里的偏移量。这种设计让索引更紧凑但每次查询都要多一次指针解引用。InnoDB放弃行指针、改用主键值换来的是主键变更时不需要大量更新二级索引代价是二级索引体积会大一些。6.4 一次真实的慢查询优化复盘最后分享一个我处理过的线上案例。某app的消息表msg行数接近8000万线上告警一条SQL频繁慢查询SELECT * FROM msg WHERE user_id 8888 AND is_read 0 AND create_time 2024-05-01 00:00:00 ORDER BY create_time DESC LIMIT 30;原索引是idx_user_id(user_id)。用户8888是一个重度用户一个月消息上百万条每次查询都要把一百万条记录从二级索引里捞出来排序再丢到临时表取30行。当时Explain显示rows1200000Extra里有Using filesort一看就知道问题出在哪。我把索引改成了idx_user_time(user_id, create_time)is_read条件靠Extra里出现Using index condition的ICP索引条件下推过滤掉大部分无用行。改成后同样的SQL耗时从900毫秒降到20毫秒以内rows从120万降到个位数。最快的优化往往是让数据结构顺势而为B树的有序键值和索引条件下推正好能应付这种“大用户小结果”的场景。聊到这儿B树和B树从原理到实现的核心脉络算是走完了一遍。最后说点个人的体会学数据结构不能只看理论图一定要动手把插入分裂的每个边界情况写出来把删除的借位合并逻辑补完整。我在写教学版B树时最大的收获不是“写出来了”而是终于理解为什么B树在磁盘场景是不可替代的——高扇出、叶子链表、稳定时延这些特性不是孤立的设计而是环环相扣地指向“最小化磁盘IO”这个终极目标。希望这篇长文也能让你把这块地基打得比别人结实一点。