1-3 B+树索引（1）在线视频

与顺序索引相对应的是一种简单的辅助索引结构

这种索引结构一般建立在非码属性上，是一种非聚集的稠密索引

因为是在非码属性上，非聚集的索引

所以索引的顺序与文件的存储顺序是不一样的

也因此呢，这种索引必须是稠密索引

如图所示，那么索引文件的顺序与数据文件的顺序是不一样的

那么正因为它建立在非码属性上

所以非码属性就有可能会取重复的值

比如说这里面10有两个，20有三个等等

有的时候为了减小这个索引文件的大小

我们只为每一个码值建立索引，那么加入一个中间层

这个中间层就存储每一个键值所对应记录的所有的指针

那么这就是简单的辅助索引结构

下面我们要为大家介绍一种比较重要的索引结构，B+树索引

这种索引结构在数据库领域里面运用的非常广泛

很多的商用数据库管理系统，比如像SQL Server，ORACLE等等

都使用它作为这个索引结构，那么B+树索引是一种多级索引

它采用的是平衡树结构

那么在这个树中，每一个节点它的结构都是相同的

像这个图所示，每一个节点都包含n个指针和n－1个键码

这n－1个键码它都是从小到大依次排列

B+树它的节点类型包含三种

第一种呢，是根节点，第二种是非叶节点，第三种是叶节点

根节点我们分别来说一下，根节点的结构呢

和叶节点，非叶节点它们都是不同的

首先对于根节点来说，从充满度上来讲，根节点可以少于半满

但是除非这棵树只有一个节点，否则这棵树必须至少要包含两个指针

比如这个图所示，那么根节点的每一个指针都指向

叶节点或者是非叶节点，那么这是根节点的结构

那么下面我们来看一下它的叶节点的结构

从充满度上来讲，每一个叶节点它必须包含的键指数达到半满以上

另外呢，叶节点和叶节点之间必须要通过指针连接起来

也就说每一个叶节点都通过最后一个指针和下一个叶节点连接起来

这样呢，所有的叶节点就会按照搜索码值从小到大的顺序连接起来

形成一个稠密索引，那么叶节点的其他指针指向什么地方呢

每一个叶节点的其他指针比如说像pi

它指向的是码值为ki的所在记录的存储地址

比如这个图所示，比如说，Brighton这个码值前面的这个p

它指向的是Brighton所在的这条记录的存储地址

这就是叶节点的结构，下面我们来看一下非叶节点的结构

B+树的非叶节点呢，是在叶节点的基础之上形成的一个多级索引结构

从充满度上来讲，非叶节点也需要键码的总数要达到半满以上

非叶节点的每一个指针都指向叶节点或者是下一个非叶节点

这就是B+树的非叶节点的结构

根据这样的一些要求呢，我们就可以建立一个完整的B+树

这样的一个索引结构，那么下面我们来看一下B+树索引的特点

那么整个B+树既可以作为主索引，也就是聚集索引

也可以作为辅助索引使用，也就是说它可以建立在码属性上

也可以建立在非码属性上，但是作为主索引的时候，它可以是稀疏索引

也可以是稠密索引，也就是说它的叶子节点可以是按块建立索引

也可以按照搜索码值来进行建立

那么下面我们来看一下B+树的查询

B+树它可以支持范围查询，也可以支持随机查询

支持范围查询，比如说它可以支持某一个搜索码值大于A小于B

这样的一种查询，那么针对这样的一种查询

我们只要找到A和B所在的叶节点

在这棵树的叶节点它的范围，那么A和B之间的所有叶节点

这些记录都是我们要寻找的结果，所以它支持范围查询是没有问题的

那么当然，它也支持随机查询

比如要支持一个搜索码值等于A，这是非常容易

那么我们直接从根节点遍历到叶节点

找到键值等于A的这样一条记录就可以了

所以从这个查询这个角度来说，B+树的查询功能还是比较强大的

B+树的查询是从根节点向叶节点的一个遍历过程

那么它的代价是什么样子的呢

因为B+树的查询是一个遍历的过程

所以查询的代价就是一个遍历树的这样的一种代价

也就是说它的代价就是树的高度，我们用一个公式来表达

这个公式里面呢k代表的是关系里面所有键值的数量

那么n－1是每一个节点键码的数量，也就是说我们查询的树的高度

那么下面呢，我们来看一下B+树的维护过程

B+树的维护是指我们插入或者删除记录的时候

我们如何维持这个索引结构它的标准定义

也就是说B+树的结构不能变化，必须保证它定义的要求

那么一般来说，当我们插入记录的时候，B+树会产生节点的分裂

那么当我们删除记录，键值要删除的时候

会产生节点的合并，下面我们就要用例子来说明一下

那么在插入和删除记录的时候，那么B+树的维护过程