第四章数据库索引_JavaAlenboy

未知 02-07 2010

第四章数据库索引索引是排好序的快速查询的数据结构

什么是索引 ?

最好的例子就是我们从小就用的字典

里面的声母查询方式就是聚簇索引。偏旁部首就是二级索引偏旁部首+笔画就是联合索引。这种方式比较适合人类的思维方式，设计也比较精妙。索引的常见模型

三种常见的数据结构：哈希表、有序数组、搜索树

哈希表

哈希表这种结构适用于只有等值查询的场景

什么是等值查询 ?

等值查询就是例如：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 由于没有其他索引，所以也就不用考虑其他索引的叶子节点大小的问题这时候我们就要优先考虑上一段提到的“尽量使用主键查询”原则，直接将这个索引设置为主键，可以避免每次查询需要搜索两棵树