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%。

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20180116A0F4VV00?refer=cp_1026

同媒体快讯

相关快讯

扫码关注云+社区