一: B - 树是一种平衡的多路查找树, 它在文件系统中很有用.
定义: 一棵 m 阶的 B - 树, 或者为空树, 或为满足下列特性的 m 叉树:
树中每个结点至多有 m 棵子树.
若根结点不是叶子结点, 则至少有两棵子树.
除根结点之外的所有非叶结点至少有[m/2] 棵子树;
所有的非终端结点中包含以下信息数据:(n,A0,K1,A1,K2,...,Kn,An)
其中: n 为关键码的个数, Ki(i=1,2,...,n)为关键码且 Ki<Ki+1,Ai 为指向子树根结点的指针(i=0,1,...,n), 且指针 Ai-1 所指子树中所有结点的关键码均小于 Ki 大于 Ki-1.
所有的叶子结点都出现在同一层次上, 并且不带信息(实际上这些结点不存在, 指向这些结点的指针为空). 即所有叶节点具有相同的深度, 等于树高度.
如一棵四阶 B - 树, 其深度为 4, 如下图:
B - 树的查找类似二叉排序树的查找, 所不同的是 B - 树每个结点上是多关键码的有序表, 在到达某个结点时, 先在有序表中查找, 若找到, 则查找成功; 否则, 到按照对应的指针信息指向的子树中去查找, 当到达叶子结点时, 则说明树中没有对应的关键码.
在上图的 B - 树上查找关键字 47 的过程如下:
1)首先从更开始, 根据根节点指针找到 *a 节点, 因为 *a 节点中只有一个关键字, 且给定值 47> 关键字 35, 则若存在必在指针 A1 所指的子树内.
2)顺指针找到 *c 节点, 该节点有两个关键字(43 和 78), 而 43 < 47 < 78, 若存在比在指针 A1 所指的子树中.
3)同样, 顺指针找到 *g 节点, 在该节点找到关键字 47, 查找成功.
二: B + 树是应文件系统所需而产生的一种 B - 树的变形树.
一棵 m 阶的 B + 树和 m 阶的 B - 树的差异在于:
有 n 棵子树的结点中含有 n 个关键码;
所有的叶子结点中包含了全部关键码的信息, 及指向含有这些关键码记录的指针, 且叶子结点本身依关键码的大小自小而大组成顺序链表.
在 B + 树上进行随机查找, 插入和删除的过程基本上与 B - 树类似. 只是在查找时, 若非叶结点上的关键码等于给定值, 也并不终止, 而是继续向下直到叶子结点. 因此, 在 B + 树中, 不管查找成功与否, 每次查找都是走了一条从根节点到叶子结点的路径.
如图一棵 3 阶的 B + 树: 通常在 B + 树上有两个头指针, 一个指向根节点, 另一个指向关键字最小的叶子节点. 因此可以对 B + 树进行两种查找运算: 一种是从最小关键字起顺序查找, 另一种是从根节点开始, 进行随机查找.
三: 下面来介绍 B + 树在数据库索引中的典型应用.
数据库索引常用 B + 树来实现. 数据库索引分为聚集索引 (也叫聚簇索引) 和非聚集索引 (非聚簇索引) 两种类型.
InnoDB 引擎使用的是聚集索引. 所谓聚集索引: 就是 B + 树的叶子节点的 data 域中存放的是完整的数据记录.
对于聚集索引, 按照 B + 树中关键字的不同分为主键索引和辅助索引. 使用主键属性作为 B + 树的关键字就是主键索引, 使用非主键属性作为 B + 树的关键字就是辅助索引. 如下图:
上图是 InnoDB 主键索引
上图是 InnoDB 辅助索引
聚集索引这种实现方式使得按主键的搜索十分高效, 但是辅助索引搜索需要检索两遍索引: 首先检索辅助索引获得主键, 然后用主键到主索引中检索获得记录. 从上面的数据结构也可以理解, 用来做索引的属性列的字段越短性能越好.
MyISAM 引擎使用的是非聚集索引. 所谓非聚集索引: 就是 B + 树的叶子节点的 data 域中存放的是数据记录的地址. 按照 B + 树中关键字的不同也可以分为主键索引和辅助索引. 如图所示:
上图是 MyISAM 主键索引
上图是 MyISAM 辅助索引
InnoDB 索引和 MyISAM 索引的区别:
1) InnoDB 是聚集索引, B + 树的叶子节点的 data 域中保存的是完整的数据记录. MyISAM 是非聚集索引, B + 树的叶子节点的 data 域中保存的是数据记录的地址.
2) InnoDB 的辅助索引中, B + 树的叶子节点的 data 域中保存的是对应的主键, 因此在 InnoDB 中使用辅助索引需要两边检索. 而对于 MyISAM 索引, 无论是主键索引还是辅助索引对需要一次检索即可.
3) 对于聚集索引, 因为它的主键索引的 data 域中存储的是完整的行信息, 因此不会再单独存储行信息, 这也是它的辅助索引的 data 域中存储的是主键值的原因. 对于非聚集索引, 它的主键索引和辅助索引的 data 域中存储的都是行信息的地址, 因此需要单独的空间来存储行信息. 如下图:
B-Tree 索引适用于全键值, 键值或前缀查找. 其中键前缀查找只适用于根据最前缀的查找. 前面所述的索引对如下类型的查询有效:
1. 全值匹配: 全值匹配指的是和索引中的所有列进行匹配.
2. 匹配最左前缀: 即仅仅匹配索引的最左侧列.
3. 匹配最左前缀的一部分: 即仅仅匹配索引的最左侧列的一部分.
4. 匹配范围值: 指定索引的最左侧列的范围.
5. 精确匹配前几列并范围匹配后一列
将上面的叙述总结起来, 可以归纳出 B-Tree 索引的限制:
1. 如果不是按照索引的最左列开始查找, 则无法使用索引.
2. 查询时不能跳过索引中的列.
3. 如果查询中有某个列的范围查询, 则其右边所有的列都无法使用索引优化查找.
读者应该明白, 索引列的顺序是很重要的, 在性能优化的时候, 可以建立相同的列但顺序不同的索引来满足不同的需求.
来源: http://www.bubuko.com/infodetail-2593280.html