B 树和 B + 树

[TOC]

参考：B 树、B+ 树详解

前言

B+ 树是一种存储构造，罕用在数据库建设索引。

筹备常识

m 阶的树：树最大分叉有 m 个，即子节点数最大为 m 个；

根节点：没有父节点的节点；

叶节点：没有子节点的节点；

外部节点：不是根、叶节点的节点；

二叉搜寻树：左子树中的值要比根节点值 小 ，右子树中的值要比根节点值 大；

均衡二叉树：二叉搜寻树的非凡状况，左右子树 高度 一样；

一、B 树

B 数是均衡 多叉树，一个 m 阶的 B 树，有如下个性：

1. 外部节点起码得有 ceil(m/2)个子节点；
2. 根节点不是叶节点时，至多得有 2 个子节点，即 2 阶；
3. m 阶的节点中蕴含 m - 1 个数据；
4. 所有叶子节点高度一致；

二、B+ 树

B+ 树是 B 树变体，对其规定做了些扭转。扭转如下：

1. 叶子结点由一个有序数组和指向其左边一个叶子结点的指针组成；

2. 非叶子节点由一个有序数组组成，然而数组元素由一个 索引值 一个指针组成；

   1. 指针：指向一个叶子节点；
   2. 索引值：指向的那个叶子节点中最小的索引值；
3. 非叶节点，是工具节点，用于疾速找到指定叶节点，只有叶节点才存储真正的数据（一行数据）；
4. 叶子 节点们 相似一个有序链表;
5. m 阶的节点中蕴含 m 个数据;

2.1 为什么 B + 树适宜数据库？

1. B+ 树便于范畴查问，这是最次要的。

只须要查找最右边范畴即可，查到后遍历往右遍历叶子结点，晓得碰到左边范畴完结，这样就筛出了所有范畴内数据。

B 树的范畴查找用的是中序遍历，而 B + 树用的是在链表上遍历；

2. B+ 树的磁盘读写代价更低。

B+ 树的外部结点并没有指向关键字具体信息的指针。因而其外部结点绝对 B 树更小。如果把所有同一外部结点的关键字寄存在同一盘块中，那么盘块所能包容的关键字数量也越多。一次性读入内存中的须要查找的关键字也就越多。相对来说 IO 读写次数也就升高了；

3. B+ 树查问效率更加稳固

因为非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查问的门路长度雷同，导致每一个数据的查问效率相当；