文章来源s默心的编程开发笔记​​​​​​​B树B 树又叫平衡多路查找树如果每个节点最多有 m个孩子那么这样的树就是 m阶 B 树。上图是一个3阶 B 树的当然现实中索引每个节点的孩子数上限肯定是远大于3的。每个存储块中主要包含了关键字和指向孩子的指针最多能有几个孩子取决于每个存储块的容量以及数据库的相关配置。通常情况下这个 m是很大的B 树的特征根节点至少包括两个孩子树中每个节点最多含有 m个孩子m2这个就是咱们说的 m阶树的含义了m取决于节点的容量以及相关配置。除根节点和叶节点外其他每个节点至少有ceil(m/2)个孩子每个非根非叶子节点至少具备两个孩子其中这个 ceil 这个函数表示取上限。比如 m为3m/21.5那我们取它的上限就是2它并不是四舍五入比如说等于1.2它取上限也是2。所有叶子节点都位于同一层叶子节点的高度都是一样的假设每个非终端节点中包含有n个关键字信息其中a)Ki(i1...n)为关键字且关键字按顺序升序排序K(i-1)Kib)关键字的个数n必须满足[ceil(m/2)-1] n m-1c)非叶子节点的指针P[1],P[2],...,P[M]其中P[1]指向关键字小于K[1]的子树P[M]指向关键字大于K[M-1]的子树其它P[i]指向关键字属于(K[i-1],K[i])的子树。可以看一下上图所示的3阶B树通过这个树来检查和理解一下上述这几个特征可以看到 B 树的前4条规则主要是用来限定 B 树的孩子数的每个节点的孩子数和 B 树的深度的。而它的最后一条规定则是用来限定 B 树节点关键字数量以及大小的。当我们要查找数据的时候这个 B 树它跟二叉查找树的查询效率是一样高效的。它的这个查找效率同样是O(logn)。当数据发生变动的时候必然会存在现有结构被打乱的情况。二叉查找树它就会有可能被打乱成线性的。由于 B 树有这5个规定存在所以b 树就会有相应的策略通过这个合并分裂上移下移节点来保持它的这个特征使B树的高度远比我们的二叉树矮得多。并且不会经过数据不断变动后变成线性的这种情况。由于我们重点关注索引所以具体的这些策略以及它的实现大家有时间可以去了解一下面试的时候这类数据结构的实现有时候也会作为面试官的利器来考大家。B树B树是B树的变体其定义基本与B树相同除了以下几个特点非叶子节点的子树指针与关键字个数相同此特点表明B树相对于B树能存储更多的关键字非叶子节点的子树指针P[i]指向关键字值[K[i],K[i1])的子树非叶子节点仅用来做索引数据都保存在叶子节点中B 树所有的检索都是从根部开始检索到叶子节点才能结束。同时非叶子节点仅用来存储索引非叶子节点不存储数据又能存储更多的关键字。也就使得我们的 B 树相对于 B 树来说更矮。B 树的搜索可以在任意一个非叶子节点就终结掉也就是它可能把数据文件存储到非叶子节点上所有的叶子节点均有一个链指针指向下一个叶子节点并按大小顺序链接大家可以看到 B 树的叶子节点都是按照大小顺序来做排列的大家可以看到589然后再到101518都是按照这个大小顺序来排列的叶子节点链接起来能够方便我们直接在叶子节点做范围统计就比如说我们要搜索大于或者等于10的这些数据我们定位到存储10的这一个叶子节点之后它就会直接从这里往后统计也就是说它支持范围统计例如这里的大于等于10。也就是说一旦定位到某个叶子节点呢便可以从该叶子节点开始横向的去跨子树去做统计。通过对比二叉查找树、平衡二叉树、B树和B树很明显B树更适合用来做存储索引理由如下B树的磁盘读写代价更低B 树的内部结构并没有指向关键字具体信息的指针也就是不存放我们的数据只存放索引信息因此其内部节点相对 B 树更小。如果把所有同一内部节点的关键字存放在同一盘块中这个盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说io 读写次数也就降低了。B树的查询效率更加稳定由于内部节点并不是最终指向文件内容的节点而只是叶子节点中关键字的索引。所以任何关键字的查找必须走一条从根节点到叶子节点的路。所有关键字查询的长度相同导致每一个数据的查询效率也几乎是相同的稳定的O(logn)。B树更有利于对数据库的扫描B 树在提高了磁盘 io 性能的同时并没有解决元素遍历的效率低下的问题而 B 树只需要遍历叶子节点就可以解决对全部关键字信息的扫描。所以对于数据库中频繁使用的范围查询以上图B树为例要查询大于或者等于10的数据。由于它的每个叶子都是用指针来连接起来的我们就可以从这个10开始顺着它的指针直接在叶子里面去做范围查询这样是非常方便的也就表明了 B 加树在做范围查询时有着更高的性能这也是为什么我们在数据库选择 B 树作为主流索引数据结构的原因。