Video在线视频

同学们

大家好

我是来自云南大学软件学院的何婧老师

今天我们来学习一种常用的数据索引结构

B+树索引

B+树索引是一种基于平衡树结构的索引

许多数据库管理系统

默认创建的索引就是B+树索引

我们先来看一下

B+树索引的结构是什么样的

B+树的节点

由key和pointer两部分组成

key表示索引键

在B+树中key是有序的

K1小于K2一直小于Kn–1

Pointer表示指针

在一棵B+树中

节点划分为根节点

分支节点和叶子节点三种类型

分支节点也可以称为内部节点

根节点位于索引树的最顶端

一棵B+树只有一个根节点

叶子节点位于索引树的最底端

中间的是分支节点

B+树是一棵多叉平衡树

B+树的分支数目称为它的阶

一棵最多有m个分支的B+树

称为一棵m阶的B+树

它满足以下性质

第一

所有从根节点到叶子节点的路径一样长

也就是说B+树是平衡树

第二

一个分支节点最少有二分之m个孩子节点

最多有 m 个孩子节点

第三

一个叶子结点最少包含

二分之m–1个索引键

最多包含m–1个索引键

特殊情况下

如果根节点之下还有孩子节点

那么一个根节点最少有二个孩子节点

如果根节点就是叶子结点

之下没有孩子节点了

那么一个根节点最少有零个索引键

最多有m–1个索引键

下面

我们具体分析一下

B+树中三类节点的结构和性质

我们先来看叶子节点

一棵m阶的B+树

其叶子节点最少包含

二分之m–1个索引键

最多包含m–1个索引键

叶子节点包含m个指针

第1个指针到第m-1个指针

指向索引键值对应的数据行或者是数据块

第m个指针指向下一个叶子节点

如果i小于j

那么第i个叶子节点中的索引键值

小于等于第j个叶子节点中的索引键值

例如

我们在图中看到的这棵

建立在教师姓名上的B+树索引

在索引叶子节点中

姓名按字典序排序

指针指向该姓名对应的数据行

接下来

我们分析B+树的分支节点

一棵m阶的B+树

其分支节点最少有二分之m个指针

最多有 m 个指针

第1个指针指向的子树中的索引键值

小于索引键值K1

对于第2到第m-1个指针中的

任意一个指针i而言

第i个指针指向的子树中的索引键值

大于等于第i-1个索引键值

小于第i个索引键值

最后

第m个指针指向的索引键值

大于等于第m-1个索引键值

就根节点而言

如果没有孩子节点了

那么

整个B+树索引就只有根节点一个节点

它最少有零个索引键

最多有m–1个索引键

如果根节点有孩子节点

那么至少应该有两个孩子节点

例如

图中展示的是一棵6阶的B+树索引

该索引建立在教师表的教师姓名列上

根据前面我们讲过的B+树的性质

每个叶子节点必须包含3到5个索引键

因为

计算当中二分之(6-1)等于3

6减1等于5

每个分支节点必须包含3到6个指针

根节点至少有两个指针

在学习了B+树的基本结构之后

我们来看看

基于B+树的查找操作是怎样进行的

查找首先从根节点开始

根据所要查找的键值

判断其所在的下一层分支节点

然后

访问对应的分支节点

以此类推

直到访问到叶子节点

就可以根据叶子节点的指针

找到想要查找的数据了

在图中

我们看到的是一棵4阶的B+树

根节点仅有两个指针

恰好是允许的最小数目

根节点最多可以有4个指针

小于13的索引键值

可以通过根节点的第一个子树找到

大于等于13的索引键值

可以通过第二个子树找到

假设我们要查找索引键7对应的数据

那么从根节点出发

由于7小于13

所以找到根节点的第一个子树

然后

由于7等于7

从当前节点的第二个指针

找到叶子节点上的索引键7

根据7对应的指针找到它指向的数据块

假设我们要查找的是37

那么由于37大于13

从B+树的根节点出发

找到其第二个指针指向的分支节点

由于37又大于31

小于43

找到当前节点的第三个指针

指向的叶子节点

在叶节点中找到索引键值37

可以看出

B+树的查找时间是稳定的

所有索引键的查找路径长度相同

总是从根节点到叶节点的路径长度

也就是B+树的树高

B+树不仅支持单键值的查询

对键值的范围查询也很有效

如果想在B+树叶节点上找到大于等于a

小于等于b的所有键值

那么

就要首先从B+树的根节点出发

找到键值a所在的叶子节点

如果a不存在

就是找到叶子节点上大于a的最小的键值

然后

还需要回到根节点找键值b吗

是的

不需要了

B+树的叶节点上的键值是排好序的

而且

B+树的叶节点上的最后一个指针

是指向兄弟节点的

这样

我们沿着叶节点顺序向后查找

就能找到键值b了

如果b不存在

就是找到小于b的最大的键值

在叶节点查找过程中

遍历的这些键值

就是满足范围查询的键值

例如

在如图所示的B+树中

查找范围在10到25之间的键值

我们从B+树的根节点开始查找

因为10小于13

所以找到根节点的第一个指针指向的节点

因为10大于7

所以沿着该节点的第二个指针

找到叶子节点

叶子节点中没有键值10

那么

我们找到的

第一个满足查找条件的键值就是11

这时候

我们不需要再回到根节点了

沿着叶子节点的指针依次向后查找

找到满足查找条件的键值

是

11

13

17

19

23

接下来的键值29大于范围上界25了

因此

整个查找过程结束

可见

B+树的设计是非常巧妙的

它不仅单键值的查找效率高

范围查找的效率也很高

一棵m阶的B+树

如果有N个键值

那么树高是log二分之m为底N的

这样的一个查找效率

比二叉树要好得多

另外

更重要的是

B+树索引有效地

降低了磁盘I/O的次数

假设指针需要占用4个字节

键值也要占用4个字节

这里是对于整型键而言

如果对于字符串索引键

那么键值占用的存储空间会更多

这样我们看到

每一个索引项是8个字节

一个2KB的磁盘页面

最多可以存放256个索引项

那么

对100万个索引项

二分查找法首先检查

其中的524287

那一项中的索引键的值

与x进行比较

接着根据比较的结果

向左或者向右移动262144项

每一次后续检测

移动的距离是上一次的一半

图中显示了后续检测的模式

即每一次从前一次检测移动距离的情况

可以看出

一直到第13次

前一次的和当前的行指针指向的项

才有可能在同一个页面上

这是因为

每一个页面上最多可以存放256项

所以前12次中

该算法都是不停地

在不同页面之间来回切换

如果我们假设

访问过的页面不会驻留在内存中

那么

这就意味着

我们至少要作12次I/O操作

我们再来看一下B+树中的执行情况

同样假设指针需要占用4个字节

键值也要占用4个字节

每一个索引项是8个字节

假设一个2KB的磁盘页面

最多可以存放256个索引项

一百万个索引项总共就需要占用

3907个页面

因此B+树的叶子层有3907个页面

3907个索引项大概就需要16个页面

建立这些索引项的上层节点

需要16个索引项

这个数目保证在一个页面中

就可以保存得下

这就是B+树的根节点

因此

索引100万个索引项

B+树只有3层

那么

也就是我们只需要进行三次I/O操作

就可以访问到所需要的数据项了

同学们

B+树索引就介绍到这里

我们下节课再见