10分钟梳理关系数据库基础知识 三：B＋树

更多腾讯海量技术文章，请关注云加社区：https://cloud.tencent.com/developer

作者：刁寿钧

存在的意义

上一篇《10分钟梳理关系数据库基础知识（二）：存储结构》中有强调，我们优化的目标，是尽量减少磁盘 IO 的次数。B+树这种数据结构就很适合这种场景。因为它高扇出，长得矮矮胖胖的，一层是一次IO。

为了直观地展现效果，我们可以做一个简单的估算。之前提到的块（block），在 InnoDB 中被称作页（page），大小是可以设的，默认为16KB。假设一行记录为100个 Byte，即每个块中能存160行记录。高度为4的 B+树，可存放的记录数就是：160×160×160×160=655360000行。而目前机械盘的IOPS一般在100～200，即使以100计算，4次IO意味着时间只需要0.04秒。是不是很美好？

当然这只是一个粗略的估算，大家感受下B+树存在的意义就好。

+在哪里

B+树是B-树的一个变种。与B-树主要有两个值得一提的不同，一是为了存放更多的指针，B+树在非叶子节点中只存放key，叶子节点中才有数据；二是叶子节点之间是有指针相联系的，这就方便了范围查询。

来，种一棵树

为了让大家有个更直观的认识，我手工画了一棵B+树构造的过程：

上图做了简化，没有考虑填充因子（fill factor）。填充因子指的是叶子节点满的程度，要求是在半满和全满之间，方便插入和删除。具体数值在InnoDB中是可以指定的，一般是75%，当然，要求至少半满，所以可设的最小值是50%。