MySQL深入学习 |
您所在的位置：网站首页 › 深入mysql实战 › MySQL深入学习 |
MySQL深入学习
|
一、深入浅出索引1、引出索引：2、索引的常见模型：哈希表、有序数组和搜索树（1）哈希表（2）有序数组（3）二叉搜索树
3、InnoDB 的索引模型问： 那么基于主键索引和普通索引的查询有什么区别呢？
4、索引覆盖5、最左前缀原则问：在建立联合索引的时候，如何安排索引内的字段顺序？
6、索引下推7、索引维护问：但是，哪些场景下应该使用自增主键，而哪些场景下不应该使用呢？
8、总结9、面试题问：为什么MySQL的索引要使用B+树而不是其它树形结构?比如B树？
一、深入浅出索引
1、引出索引：
比如某一个 SQL 查询比较慢，分析完原因之后，你可能就会说“给某个字段加个索引吧”之类的解决方案。但到底什么是索引，索引又是如何工作的呢？ 索引其实就是一种有序的数据结构；它的出现其实就是为了提高数据查询的效率，就像书的目录一样。对于数据表而言，索引其实就是它的“目录”。 2、索引的常见模型：哈希表、有序数组和搜索树 （1）哈希表 哈希表也称散列表，由直接寻址表改进过来的。当关键字的全域U比较小时，它便是一种简单而有效的技术。用一个数组T[0…m-1]表示动态集合，其中每一个位置（或称槽或桶）对应全域U中的一个关键字。下图说明这个方法，槽k指向集合中一个关键字为k的元素。如果该集合中没有关键字k的元素，则T[k]=NULL。 图1：直接寻址表
但是直接存在一个很明显的问题就是，当实际要存储的关键字集合K相对于U来说可能很小，因而分配给T的大部分空间都要浪费掉。 因此，哈希表出现了。在哈希方式下，该元素处于h(k)中，亦利用哈希函数h，根据关键字k计算出槽的位置。函数h将关键字域U映射到哈希表T[0…m-1]的槽位上，如下图所示： 哈希表技术很好解决了直接寻址遇到的问题，但是还有一个小问题，所上图所示两个关键字可能映射到同一个槽上。一般将这种情况称之为发生了冲突。数据库一般采用最简单的碰撞解决技术，称之为链接法。 在链接法中，把散列到同一个槽中的所有元素都放在一个链表中，如下图所示： 哈希表是一种以键 - 值（key-value）存储数据的结构，我们只要输入待查找的键即 key，就可以找到其对应的值即 value。 key-value都放在链表里面，用key算出的哈希值放在数组里。当需要用key查value时，先算出哈希值，找到指定数组，再用key去遍历后面的链表，因为链表中同时包含key-value，就可以找到指定的value了。 例如，你现在维护着一个身份证信息和姓名的表，需要根据身份证号查找对应的名字，这时对应的哈希索引的示意图如下所示： 不可避免地，多个 key 值经过哈希函数的换算，会出现同一个值的情况。处理这种情况的一种方法是，拉出一个链表。这就需要依赖精妙的hash算法来让值均匀的分布了，不然就会出现单链表的情况，所有的值都出现在同一个链表的极端情况。 图中，User2 和 User4 根据身份证号算出来的值都是 N，但没关系，后面还跟了一个链表。假设，这时候你要查 ID_card_n2 对应的名字是什么，处理步骤就是：首先，将 ID_card_n2 通过哈希函数算出 N；然后，按顺序遍历，找到 User2。需要注意的是，图中四个 ID_card_n 的值并不是递增的，这样做的好处是增加新的 User 时速度会很快，只需要往后追加。但缺点是，因为不是有序的，所以哈希索引做区间查询的速度是很慢的。就比如：如果你现在要找身份证号在[ID_card_X, ID_card_Y]这个区间的所有用户，就必须全部扫描一遍了。所以，哈希表这种结构适用于只有等值查询的场景，比如 Memcached 及其他一些 NoSQL 引擎。 （2）有序数组有序数组在等值查询和范围查询场景中的性能就都非常优秀。还是上面这个根据身份证号查名字的例子，如果我们使用有序数组来实现的话，示意图如下所示： 这里我们假设身份证号没有重复，这个数组就是按照身份证号递增的顺序保存的。这时候如果你要查 ID_card_n2 对应的名字，用二分法就可以快速得到，这个时间复杂度是 O(log(N))。 对于查询，有序数组就是最好的数据结构。但是，在需要更新数据的时候就显得非常麻烦了，因为当你往中间插入一条记录就必须的挪动后面所有的记录。所以，有序数组索引只适用于静态存储引擎。 （3）二叉搜索树 还是上面根据身份证号查名字的例子，如果我们用二叉搜索树来实现的话，示意图如下所示： 图 6 二叉搜索树示意图
二叉搜索树的特点是：父节点左子树所有结点的值小于父节点的值，右子树所有结点的值大于父节点的值。这样如果你要查 ID_card_n2 的话，按照图中的搜索顺序就是按照 UserA -> UserC -> UserF -> User2 这个路径得到。这个时间复杂度是 O(log(N))。 二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在内存中，还要写到磁盘上。 为什么数据库存储使用b+树 而不是二叉树，同等结点的条件下，二叉树比 n 叉树的高度更高，这就意味着需要更多的磁盘 I/O，时间更长。举个例子：一棵 100 万节点的平衡二叉树，树高 20。一次查询可能需要访问 20 个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一个行可能需要 20 个 10 ms 的时间，这个查询可真够慢的。 3、InnoDB 的索引模型在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。又因为前面我们提到的，InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的。每一个索引在 InnoDB 里面对应一棵 B+ 树。 假设，我们有一个主键列为 ID 的表，表中有字段 k，并且在 k 上有索引。 create table T ( ID int primary key, k int NOT NULL DEFAULT 0, s varchar(16) NOT NULL DEFAULT '', index k(k)) engine=InnoDB; insert into T values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg'); 表中 R1~R5 的 (ID,k) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，两棵树的示例示意图如下。 图 7 InnoDB 的索引组织结构
现在，我们一起来看看这条 SQL 查询语句的执行流程： 1、在 k 索引树上找到 k=3 的记录，取得 ID = 300； 2、再到 ID 索引树查到 ID=300 对应的 R3； 3、在 k 索引树取下一个值 k=5，取得 ID=500； 4、再回到 ID 索引树查到 ID=500 对应的 R4； 5、在 k 索引树取下一个值 k=6，不满足条件，循环结束。 在这个过程中，回到主键索引树搜索的过程，我们称为回表。可以看到，这个查询过程读了 k 索引树的 3 条记录（步骤 1、3 和 5），回表了两次（步骤 2 和 4）。从图中不难看出，根据叶子节点的内容，索引类型分为主键索引和非主键索引。 主键索引（聚簇索引）： key : 主键的值，value : 页中的整行数据。 非主键索引（二级索引，相当于普通列的索引）： key：索引列的值， value : 主键的值。 问： 那么基于主键索引和普通索引的查询有什么区别呢？答：主键索引 是唯一且有序的，非主键索引，是需要找到结果ID，回表，获取最后的结果的。而回表就是指二级索引数找到 id ，通过id再去主键索引树上找其他数据，这个过程叫回表。 例如： 如果语句是 select * from T where ID=500，即主键查询方式，则只需要搜索 ID 这棵 B+ 树；如果语句是 select * from T where k=5，即普通索引查询方式，则需要先搜索 k 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。总结： 基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。那么，有没有可能经过索引优化，避免回表过程呢？接下来就要讲到索引覆盖了。 4、索引覆盖 如果执行的语句是 select ID from T where k between 3 and 5，这时只需要查 ID 的值，而 ID 的值已经在 k 索引树上了，因此可以直接提供查询结果，不需要回表。也就是说，在这个查询里面，索引 k 已经“覆盖了”我们的查询需求，我们称为覆盖索引。由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。 需要注意的是，在引擎内部使用覆盖索引在索引 k 上其实读了三个记录，R3~R5（对应的索引 k 上的记录项），但是对于 MySQL 的 Server 层来说，它就是找引擎拿到了两条记录，因此 MySQL 认为扫描行数是 2。 5、最左前缀原则 如果为每一种查询都设计一个索引，索引是不是太多了。在一个市民信息表上，如果我现在要按照市民的身份证号去查他的家庭地址呢？虽然这个查询需求在业务中出现的概率不高，但总不能让它走全表扫描吧？反过来说，单独为一个不频繁的请求创建一个（身份证号，地址）的索引又感觉有点浪费。应该怎么做呢？假设这个市民表的定义是这样的： CREATE TABLE `tuser` ( `id` int(11) NOT NULL, `id_card` varchar(32) DEFAULT NULL, `name` varchar(32) DEFAULT NULL, `age` int(11) DEFAULT NULL, `ismale` tinyint(1) DEFAULT NULL, PRIMARY KEY (`id`), KEY `id_card` (`id_card`), KEY `name_age` (`name`,`age`) ) ENGINE=InnoDB 为了直观地说明这个概念，我们用（name，age）这个联合索引来分析。
答： 根据索引的复用能力。因为可以支持最左前缀，所以当已经有了 (a,b) 这个联合索引后，一般就不需要单独在 a 上建立索引了。但是，如果查询条件里面只有 b 的语句，是无法使用 (a,b) 这个联合索引的，这时候你不得不维护另外一个(b) 这个索引。就好比上面这个市民表的情况，name 字段是比 age 字段大的 ，那我就建议你创建一个（name,age) 的联合索引和一个 (age) 的单字段索引。 6、索引下推 当不满足最左前缀原则的时候，那又该怎么办呢？我们还是以市民表的联合索引（name, age）为例。如果现在有一个需求：检索出表中“名字第一个字是张，而且年龄是 10 岁的所有男孩”。那么，SQL 语句是这么写的： select * from tuser where name like '张%' and age=10 and ismale=1;根据最左前缀原则，系统可以帮我们找到第一个满足条件的记录ID3。但是，我们还得判断其它条件是否满足啊。在 MySQL 5.6 之前，只能从 ID3 开始一个个回表。到主键索引上找出数据行，再对比字段值。执行流程如下图所示： 而MySQL 5.6 引入的索引下推优化（index condition pushdown)， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。执行流程如下图所示： 图3中，整个过程InnoDB是并不会去看age的值，而是按顺序把“name 第一个字是’张’”的记录一条条取出来回表。因此，需要回表 4 次。 图4中，InnoDB 在 (name,age) 索引内部就判断了 age 是否等于 10，对于不等于 10 的记录，直接判断并跳过。在我们的这个例子中，只需要对 ID4、ID5 这两条记录回表取数据判断，就只需要回表 2 次。 7、索引维护 B+ 树为了维护索引有序性，在插入新值的时候需要做必要的维护。就拿上图举例：如果插入新的行 ID 值为 700，则只需要在 R5 的记录后面插入一个新记录。如果新插入的 ID 值为 400，就相对麻烦了，需要逻辑上挪动后面的数据，空出位置。而更糟的情况是，如果 R5 所在的数据页已经满了，根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能自然会受影响。当然有分裂就有合并。当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程。所以推荐使用自增主键，就可以保证新的ID一定是在叶子节点最右边，不会影响前面的数据。自增主键是指自增列上定义的主键，在建表语句中一般是这么定义的： NOT NULL PRIMARY KEY AUTO_INCREMENT。 问：但是，哪些场景下应该使用自增主键，而哪些场景下不应该使用呢？答： （1）插入记录，因为每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。 （2）业务逻辑的字段做主键时，就好比字符串类型的身份证号，如果用身份证号做主键，那么每个二级索引的叶子节点占用约 20 个字节，而如果用整型做主键，则只要 4 个字节，如果是长整型（bigint）则是 8 个字节。显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。 （3）当该字段只有一个索引，并且该索引必须是唯一索引的时候。这时就可以直接将这个索引设置为主键，可以避免每次查询需要搜索两棵树。 8、总结（1）索引的作用：提高数据查询效率 （2）常见的索引模型：哈希表、有序数组、搜索树 （3）哈希表：key-value形式，用一个哈希函数将key换算成一个确定的位置，然后把value放在数组中的这个位置，如果有冲突的情况，则使用链接法解决，使用场景在只有等值查询的时候 （4）有序数组：按顺序存储，使用二分法就可以快速查询，但是更新效率低，使用场景在静态存储引擎的时候 （5）二叉搜索树：查询时间和更新时间复杂度都为O(log(N))，但数据库存储大多数不适用二叉树，因为树高度过高，这就意味着需要更多的磁盘 I/O，时间更长。 （6）InnoDB中的索引模型：B+树，其索引类型有主键索引和非主键索引，主键索引的叶子节点存的是页，页里面有很多行的数据，非主键索引的叶子节点内容是主键的值。 （7）主键索引和普通索引的区别：主键索引只要搜索ID这个B+Tree即可拿到数据。普通索引先搜索索引拿到主键值，再到主键索引树搜索一次(回表) （8）联合索引的技巧： 1、覆盖索引：如果查询条件使用的是普通索引（或是联合索引的最左原则字段），查询结果是联合索引的字段或是主键，不用回表操作，直接返回结果，减少IO磁盘读写读取正行数据2、最左前缀：联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符3、联合索引：根据创建联合索引的顺序，以最左原则进行where检索，比如（age，name）以age=1 或 age= 1 and name=‘张三’可以使用索引，单以name=‘张三’ 不会使用索引，考虑到存储空间的问题，还请根据业务需求，将查找频繁的数据进行靠左创建索引。4、索引下推：like 'hello%’and age >10 检索，MySQL5.6版本之前，会对匹配的数据进行回表查询。5.6版本后，会先过滤掉age |
图2：哈希表
图3：链接法解决碰撞哈希表
图 4 哈希表示意图
图 5 有序数组示意图
图 8 （name，age）索引示意图
图 9 无索引下推执行流程
图 10 索引下推执行流程【本文地址】
今日新闻 |
推荐新闻 |