第四章 数据库索引
索引是排好序的快速查询的数据结构
什么是索引 ?
最好的例子就是我们从小就用的字典
- 里面的声母查询方式就是聚簇索引。
- 偏旁部首就是二级索引
- 偏旁部首+笔画就是联合索引。
- 这种方式比较适合人类的思维方式，设计也比较精妙。
索引的常见模型
三种常见的数据结构：哈希表、有序数组、搜索树
哈希表
哈希表这种结构适用于只有等值查询的场景
什么是等值查询 ?
- 等值查询就是例如：
select name from T where id = 12 - 等值查询就是用
等号来匹配查询结果，分为单条件查询、多条件查询
有序数组
有序数组在 等值查询 和 范围查询 的性能都非常优先，但是有序数组的更新（插入和删除）成本就比较高了，所以有序数组索引只适用于静态存储引擎
什么是静态存储引擎 ?
- 比如你要保存的是 2017 年某个城市的所有人口信息，这类不会再修改的数据。
搜索树
MySQL的存储结构
- 表存储结构
- 单位：
表 > 段 > 区 > 页 > 行 - 在数据库中， 不论读一行，还是读多行，都是将这些
行所在的页进行加载。也就是说存储空间的基本单位是页 - 一个页就是一棵
B+树的节点，数据库I/O 操作的最小单位是页，与数据库相关的内容都会存储在页的结构里
B+树的索引结构
- 在一棵
B+树中，每个节点都是一个页，每次新建节点的时候，就会申请一个页空间 - 同一层的节点之间，通过页的结构构成了一个
双向链表 - 非叶子节点：包括了多个索引行，每个索引行里存储了
索引键和指向下一层页面的指针 - 叶子节点：存储了
关键字和行记录，在节点内部 (也就是页结构的内部) 记录之间是一个单向链表
B+树 页节点结构
- 将所有的记录分成几个组， 每组会存储多条记录
- 页目录存储的是
槽(slot)，槽相当于分组记录的索引，每个槽指针指向了不同组的最后一个记录 - 我们通过槽定位到组，再查看组中的记录
- 页的主要作用是存储记录，在页中记录着以单链表的形式进行存储
- 单链表的优点是插入、删除方便，缺点是检索效率不高，最坏的情况要遍历链表所有的节点。
- 因此页目录中提供了
二分查找的方式，来提高记录的检索效率。
B+树的检索过程
- 从B+树的根节点开始，逐层找到叶子节点
- 找到叶子节点对应的数据页，将数据页加载到内存中，通过页目录的槽采用
二分查找的方式先找到一个粗略的记录分组 - 在分组中通过链表遍历的方式进行记录的查找
为什么要用
B+树索引 ?
- 数据库访问数据要通过页，一个页就是一个B+树节点，访问一个节点相当于一次
I/O操作，所以越快能找到节点，查找性能越好 - B+树的特点就是
够矮够胖，能有效地减少访问节点次数从而提高性能
下面，我们来对比一个二叉树、多叉树、B树和B+树
二叉树
- 二叉树是一种二分查找树，有很好的查找性能，相当于二分查找
- 但是当N比较大的时候，树的深度比较高。数据查询的时间主要依赖于
磁盘IO的次数，二叉树深度越大，查找的次数越多，性能越差 - 最坏的情况是退化成了链表，如下图
- 为了让二叉树不至于退化成链表，人们发明了AVL树(平衡二叉搜索树)：任何结点的左子树和右子树高度最多相差1
多叉树
- 多叉树就是节点可以是M个，能有效地减少高度，高度变小后，节点变少
I/O操作自然少，性能比二叉树好了
B树
- B树简单地说就是多叉树，每个叶子会存储数据，和指向下一个节点的指针
例如要查找9，步骤如下：
- 我们与根节点的关键字 (17，35)进行比较，9 小于 17 那么得到指针 P1
- 按照指针 P1 找到磁盘块 2，关键字为(8，12)，因为 9 在 8 和 12 之间，所以我们得到指针 P2
- 按照指针 P2 找到磁盘块 6，关键字为(9，10)，然后我们找到了关键字 9
B+树
- B+树是B树的改进，简单地说就是：只有叶子节点才存储数据，非叶子节点是存储的指针；所有叶子节点构成一个
有序链表
例如要查找关键字16，步骤如下：
- 与根节点的关键字 (1，18，35) 进行比较，16 在 1 和 18 之间，得到指针 P1(指向磁盘块 2)
- 找到磁盘块 2，关键字为(1，8，14)，因为 16 大于 14，所以得到指针 P3(指向磁盘块 7)
- 找到磁盘块 7，关键字为(14，16，17)，然后我们找到了关键字 16，所以可以找到关键字 16 所对应的数据
B+树与B树 的区别 ?
- B+树非叶子节点
不存储数据只存储索引，B树非叶子节点存储数据 - B+树使用
双向链表串连所有叶子节点，区间查询效率更高，因为所有数据都在B+树的叶子节点，但是B树则需要通过中序遍历才能完成查询范围的查找 - B+树每次都必须查询到叶子节点才能找到数据，而B树查询的数据可能不在叶子节点，也可能在，这样就会造成查询的效率的不稳定
- B+树查询效率更高，因为B+树矮更胖，高度小，查询产生的
I/O操作最少
InnoDB 的索引模型
举例
- 假设，我们有一个主键列为 ID 的表，表中有字段 k，并且在 k 上有索引。
mysql> create table T(
id int primary key,
k int not null,
name varchar(16),
index (k))engine=InnoDB;
- 表中 R1~R5 的 (ID,k) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，两棵树的示例示意图如下。
- 每一个索引在 InnoDB 里面对应一棵 B+ 树
- 根据叶子节点的内容，索引类型分为
主键索引和非主键索引 - 主键索引的叶子节点存的是
整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index） - 非主键索引的叶子节点内容是
主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）
基于主键索引和普通索引的查询有什么区别 ?
- 如果语句是
select * from T where ID=500;，即主键查询方式，则只需要搜索 ID 这棵 B+ 树 - 如果语句是
select * from T where k=5;，即普通索引查询方式，则需要先搜索 k 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表 - 基于
非主键索引的查询需要多扫描一棵索引树 - 在应用中应该尽量使用主键查询
关于 InnoDB 的表结构
- 在 InnoDB 中，每一张表其实就是多个
B+ 树，即一个主键索引树和多个非主键索引树 - 执行查询的效率，使用
主键索引 > 使用非主键索引 > 不使用索引 - 如果不使用索引进行查询，则从主索引 B+ 树的叶子节点进行遍历
索引维护
什么是索引维护 ?
- B+ 树为了维护索引
有序性，在插入新值的时候需要做必要的维护 - 所以推荐使用
自增主键，就可以保证新的ID一定是在叶子节点最右边，不会影响前面的数据 - 以上面这个图为例，如果插入新的行 ID 值为 700，则只需要在 R5 的记录后面插入一个新记录。如果新插入的 ID 值为 400，就相对麻烦了，需要
逻辑上挪动后面的数据，空出位置 - 如果 R5 所在的数据页已经满了，根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂，性能会受到影响
- 页分裂操作还会影响数据页的利用率
- 当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程
需要逻辑上挪动后面的数据 ? 这句话是什么意思 ?
- 所谓的逻辑上挪动，就是指
逻辑删除 - 很多数据表删除数据都是
逻辑删除而非物理删除 Innodb存储引擎下，所有表都是这样的，当删除的记录达到页体积的百分之50才会尝试页合并逻辑删除是指只是删除了指向这片内存的指针，也就是说，CPU无法通过原来的指针索引到这片内存了(并且操作系统已经认为这片内存已经被释放了)- 其实，这片内存上还是有值的，就是你原来程序给这片内存赋的值，但是操作系统会认为这是一片没有数据的空闲内存
哪些场景下应该使用
自增主键?
- 自增主键是指自增列上定义的主键，在建表语句中一般是这么定义的：
not null primary key auto_increment - 插入新记录的时候可以不指定 ID 的值，系统会获取当前 ID 最大值加 1 作为下一条记录的 ID 值。
- 每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。
- 如果主键自增的话，MySQL 在写满一个数据页的时候，就会直接申请另一个新的数据页接着写就可以了 ！
**旧数据页的数据不分离！不存在分页！** - 从性能和存储空间方面考量，自增主键往往是更合理的选择
哪些场景下不应该使用
自增主键?
- 一般不用业务字段做主键
业务字段不一定是递增的，有可能会造成主键索引的页分裂(往中间的地方插入)，导致性能不稳定- 二级索引存储的值是主键，如果使用业务字段占用大小不好控制，如果业务字段过长可能会导致二级索引占用空间过大，利用率不高。
什么场景下适合用业务字段直接做主键呢 ?
- 只有一个索引
- 该索引必须是唯一索引
- 这就是典型的 KV 场景
- key value场景就是存在业务唯一字段列，然后整行数据相当于value
- 由于没有其他索引，所以也就不用考虑其他索引的叶子节点大小的问题
- 这时候我们就要优先考虑上一段提到的“尽量使用主键查询”原则，直接将这个索引设置为主键，可以避免每次查询需要搜索两棵树