B 树与 B+ 树

数据结构 · 数据库与文件系统的索引

什么是 B 树

二叉查找树一个节点只存 1 个值、2 个孩子，数据一多就长得又瘦又高，查一次要走很多层。B 树反其道：一个节点存「一排有序 key + 一排孩子指针」，又矮又宽。所有叶子在同一层，几层就能在海量数据里定位——这正适合磁盘：一次 IO 读一个节点（能装几十上百个 key），层数越少 IO 越少。

B+ 树：数据全在叶子 + 叶链

B+ 树是 B 树的改良：内部节点只存「路标」做路由、不存数据，所有数据都落在叶子；叶子之间还用链表串起来。这样区间查询特别快——定位到起点叶子后，顺着叶链一路扫过去即可。MySQL InnoDB 主键索引、很多文件系统的目录索引，用的都是 B+ 树。

下面是一棵装了 12 个数的 B+ 树（2 层）。填 a 点「查找」看它从根下钻几层就命中；填 a、b 点「范围查」看它定位起点叶后顺着叶链横扫一段。

查找：从根开始，在节点的有序 key 里比较，决定走哪个孩子指针，几层就到叶子——O(log n)，但因为「多路」底数大，层数比二叉树少得多。范围查询：B+ 树定位一次再顺叶链扫，省去回树。插入太满时节点会「分裂」、删空会「合并」来保持平衡（这里是固定结构，分裂/合并只作了解）。

B 树 / B+ 树在哪里用

它把「多路 + 平衡 + 磁盘友好」做到了极致——这趟结构之旅里工程味最浓的一站。