【数据库复习】索引

索引

写在前面的话

本文是本学渣因为考试需要写的一篇总结，只总结了需要考察的考点，所以可能有的内容引申的不多，请见谅。

一、本节考点

1. b树 b+树的结构
2. 什么时候能用什么时候不能用。
3. 要会画结构
4. 要理解能干什么不能干什么

二、索引是什么

索引是对数据库表中一列或多列的值进行排序的一种结构，使用索引可快速访问数据库表中的特定信息。是一种以原子粒度访问数据的手段（访问少数行），而不是为了大量数据的访问。

三、B树和B+树是什么

3.1 阶的定义

对于B树，我们常常会说是M阶B树，这个M就是阶数，阶数表示了一个节点最多有多少个孩子节点(子树)，也就是有多少查找路径。
注意：一个节点的 关键字数 + 1 = 子树数量
（这是因为关键字两两之间夹一个子树，四个关键字就有五个子树）

因此可以根据阶数的定义得出：
上限：
一颗M阶B树最有多有M-1个关键字，M个子树
下限：
对于根节点，最少有1个关键字，2个子树
对于非根节点，最少有M//2个关键字，M//2+1个子树

3.2B树的结构

3.2.1 B树的规则

B树属于多叉树又名平衡多路查找树（查找路径不只两个），需要满足以下几种规则：

1. 排序规则：所有节点关键字是按递增次序排列，并遵循左小右大原则
2. 子节点数（子树个数）与关键字个数与3.1中所述一致
3. 所有叶节点在同一层；叶子节点指向子树的指针地址都为null，对应下图最后一层节点的空格子
   (每个节点包含三个部分:
   一是用于建立索引的关键字，可以由主键别别的列组合构成
   二是关键字指向的记录的指针，可以通过指针查找相应信息
   三是指向其左右子树的指针)

3.2.2 B树的插入

以5阶B树为例子，插入需要遵循两个规则：

1. 排序规则：左小右大
2. 节点拆分规则：当前是要组成一个5路查找树，那么此时m=5,关键字数必须<=4（也就是说当某个节点有四个关键字的时候，继续要插入的话就需要拆分）

下面是使用3、8、31、11、23、29、50、28 构建5阶B树的步骤：
先插入 3、8、31、11：

然后再插入23、29，由于在上一步进行了拆分，所以得到

再插入50、28，再次拆分

3.2.3 B树节点的删除

此处删除同样需要遵循三个规则：

1. 排序规则：左小右大
2. 节点合并规则：当前是要组成一个5路查找树，则关键字数必须大于等于5//2（也就是说某个节点只有2个关键字的时候，再要删除就要进行节点合并）
3. 关键字数小于2时先从子节点取，子节点没有符合条件时就向向父节点取

例如从B树中删除28

这就是需要进行节点合并，先看子节点，没有子节点，就从父节点取。此时父节点需要合并，就从别的子节点取一个值。

3.3 B+树的结构

B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找，每次查找次数都一样

3.3.1 B+树的规则：

1. 不同于B树每个节点都是三部分组成，B+树的枝节点不包含关键字的内容指针，只有关键字和子树指针进行索引
2. B+树的叶节点包含了父节点的内容指针，所有的内容查询都要到叶节点层才能完成，因此每次查询次数相同
3. 排序规则：依旧是左小右大，但是叶节点左边结尾数据都会保存右边节点开始数据的地址指针，所以每层都是联通的
4. 关键字数 = 子树个数，每个父节点关键字对应子节点的第一个关键字

示意图如下：

四、使用场景

B树和B+树都是多路查找树，目的都是为了解决多次访问磁盘，IO耗时太长的问题

什么是时候使用B树索引：
仅当要通过索引访问表中很少一部分行，用于提高单个数据的查找效率。

什么时候使用B+树索引：
进行范围查找，排序查找，分组查找以及去重查找的时候可以用。
(因为 B+ 树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的)

二者什么时候不能用：

1. 对于复合索引，如果违反最左匹配原则，则不能用。例如，对(x,y)建立索引，但对y进行查询，则不能用。
2. 数据量较小时：因为使用索引拿到rowid后，需要额外一次磁盘IO，所以增加了时间开销。
3. 写密集型事务：频繁修改索引，增加开销

五、聚簇索引与非聚簇索引

以主键作为 B+ 树索引的键值而构建的 B+ 树索引，我们称之为聚集索引
以主键以外的列值作为键值构建的 B+ 树索引，我们称之为非聚集索引

的区别在于非聚集索引的叶子节点不存储表中的数据，而是存储该列对应的主键，想要查找数据我们还需要根据主键再去聚集索引中进行查找，这个再根据聚集索引查找数据的过程，我们称为回表。
也就是说最终都要进行聚集索引