MySQL索引
生活中的索引
MySQL官方对索引的定义为
索引(Index)是帮助MySQL高效获取数据的数据结构。可以得到索引的本质:索引是数据结构。上面的理解
比较抽象,举一个例子,平时看任何一本书,首先看到的都是目录,通过目录去查询书籍里面的内容会非常的迅速。
上图就是一本书籍的目录是按顺序放置的,有第一节,第二节它本身就是一种顺序存放的数据结构,是一种顺序结构。
另外通过目录(索引),可以快速查询到目录里面的内容,它能高效获取数据,通过这个简单的案例可以理解所以就是高效获取数据的数据结构。
再来看一个发杂的情况
我们要去图书馆找一本书,这图书馆的书肯定不是线性存放的,它对不同的书籍内容进行了分类存放,整索引由于一个个节点组成,根节点有中间节点,中间节点下面又由子节点,最后一层是叶子节点。
可见,整个索引结构是一棵倒挂着的树,其实它就是一种数据结构,这种数据结构比前面讲到的线性目录更好的增加了查询的速度。
MySql中的索引
MySql中的索引其实也是这么一回事,我们可以在数据库中建立一系列的索引,比如创建主键的时候默认会创建主键索引,上图是一种BTREE的索引,每一个节点都是主键的ID。当我们通过ID来查询内容的时候,首先去查索引库,在到索引库后能快速的定位索引的具体位置。
谈下B+Tree
要谈B+TREE说白了还是Tree,但谈这些之前还要从基础开始讲起
二分查找
二分查找法(binary search) 也称为折半查找法,用来查找一组有序的记录数组中的某一记录。
其基本思想是:将记录按有序化(递增或递减)排列,在查找过程中采用跳跃式方式查找,即先以有序数列的中点位置作为比较对象,如果要找的元素值小于该中点元素,则将待查序列缩小为左半部分,否则为右半部分。通过一次比较,将查找区间缩小一半。
举例
给出一个例子,注意该例子已经是升序排序的,且查找 数字 48
数据 | 下标 |
---|---|
5 | 0 |
10 | 1 |
19 | 2 |
21 | 3 |
31 | 4 |
37 | 5 |
42 | 6 |
48 | 7 |
50 | 8 |
52 | 9 |
操作步骤
步骤一:设 low 为下标最小值 0 , high 为下标最大值 9 ;
步骤二:通过 low 和 high 得到 mid ,mid=(low + high) / 2,初始时 mid 为下标 4 (也可以=5,看具体算法实现);
步骤三 : mid=4 对应的数据值是31,31 < 48(我们要找的数字);
步骤四:通过二分查找的思路,将low设置为31对应的下标 4 ,high 保持不变为9,此时mid为 6 ;
步骤五 :mid=6 对应的数据值是42,42 < 48(我们要找的数字);
步骤六:通过二分查找的思路,将low设置为42对应的下标6 ,high保持不变为9,此时mid为7 ;
步骤七 :mid=7对应的数据值是48,48 == 48(我们要找的数字),查找结束;
通过3次 二分查找 就找到了我们所要的数字,而顺序查找需8
二叉树(Binary Tree)
每个节点至多只有二棵子树;
• 二叉树的子树有左右之分,次序不能颠倒;
• 一棵深度为k,且有 个节点,称为满二叉树(Full Tree);
• 一棵深度为k,且root到k-1层的节点树都达到最大,第k层的所有节点都 连续集中 在最左边,此时为完全二叉树(Complete Tree)
平衡二叉树(AVL-树)
- 左子树和右子树都是平衡二叉树;
- 左子树和右子树的高度差绝对值不超过1;
平衡二叉树
非平衡二叉树
平衡二叉树的遍历
- 前序 :6 ,3, 2, 5,7, 8(ROOT节点在开头, 中 -左-右 顺序)
- 中序 :2, 3, 5, 6,7, 8(中序遍历即为升序,左- 中 -右 顺序)
- 后序 :2, 5, 3, 8,7, 6 (ROOT节点在结尾,左-右- 中 顺序)
平衡二叉树的旋转
B + Tree
需要通过旋转(左旋,右旋)来维护平衡二叉树的平衡,在添加和删除的时候需要有额外的开销。
B+ Tree 介绍
B+ 树是 B 树的变形。一棵 m 阶 B+ 树和 m 阶 B 树的异同点如下:
有 n 个子结点的 B+ 树有 n 个关键字,而 B 树则是有 n -1 个关键字;
B+ 树的内结点不存储 data ,只存储 key;
B+ 树的所有叶子结点中包含所有信息,叶子结点本身依关键字大小依次顺序链接;
B+ 树所有的非终端结点可 以看成是索引部分,结点中仅含有其子结点的最大(或最小)关键字。
用图片描述 B+ Tree
B+ Tree查找过程及其效率
上图中,假设需要查询 key 为 80 的数据,首先需要将根结点加载,通过比较,80 大于 65,则会通过 P3 指针再加载对应的结点,在将结点上的 key 与 80 比较,最后定位在 P2 指针对应的区域在进行加载获取数据。
上述查找过程,一共进行了 3 次加载过程,加载次数本质上 B+ 树的树高。实际上,B+ 树的查找效率取决于树高 h。
假设当前数据表的数据量为 N,每个结点的关键字数量是 m,则树高 :
在根据对数函数的函数特性:
B+ Tree 的作用
在块设备上,通过B+树可以有效的存储数据;
所有记录都存储在叶子节点上,非叶子(non-leaf)存储索引(keys)信息;
B+树含有非常高的扇出(fanout),通常超过100,在查找一个记录时,可以有效的减少IO操作;
B+ Tree 的扇出(fan out)
- 该 B+ 树高度为 2
- 每叶子页(LeafPage)4条记录
- 扇出数为5
- 叶子节点(LeafPage)由小到大(有序)串联在一起
扇出:是每个索引节点(Non-LeafPage)指向每个叶子节点(LeafPage)的指针
扇出数 = 索引节点(Non-LeafPage)可存储的最大关键字个数+ 1
图例中的索引节点(Non-LeafPage)最大可以存放4个关键字,但实际使用了3个;
B+ Tree 的插入操作
B+ 树大致的插入算法如下:
- 寻找需要插入数据的目标叶节点;
- 判断插入的数据是否比 B+ 树目前最小值还小,如果是更新全树非叶结点的最小值;
- 判断目标叶结点是否数据满,未满的情况下直接插入数据;
- 在叶结点已经满的情况下,分裂叶结点,将包括待插入数据在内的数据均分成两个新结点;
- 在分裂的情况下,将新的结点在父节点未出现的最小值插入父节点;
- 父节点重复插入数据的过程,直到没有新结点需要分裂的情况;
- 如果是根结点需要分裂,将它视为有一个空的父节点,重复上述插入数据的过程。
下面以具体的数据演示插入数据的过程
插入数据 7,更新所有所有非叶结点最小值,然后插入 7
![]](../images/mysql/mysql157.png)
更新最小值
插入数据 6,更新所有非叶节点最小值,然后拆分叶结点
更新最小值
拆分结点,将两个结点中未在父节点出现的最小值插入父结点
拆分结点
将拆分的新结点中未在父节点(空结点)出现的最小值插入父节点
当然,为了减少结点的拆分,提高磁盘利用率,减少磁盘 I/O 次数,B+ 树的插入还提供了旋转功能。当叶结点已满但其左右兄弟节点没有满的情况下,B+ 树并不急于去做拆分操作,而是将记录移到当前所在页的兄弟节点上。通常情况下,左兄弟会被先检查用来做旋转操作。
例如如下情况,在插入 85 的情况下可以进行左旋操作
左旋示例 B+ 树
插入85
B+ Tree 在 Mysql 中的应用
在 Mysql 中,索引是采用 B+ 树的结构进行组织,从而形成索引文件。索引是属于存储引擎级别的概念,下面主要介绍 MyISAM 和 InnoDB 两个存储引擎的索引实现方式。
非聚集索引存储引擎 MyISAM
此处借用他人的图片进行说明,MyISAM 存储引擎在 B+ 树的叶结点,存放的是数据记录的地址。下面两种张图分别展示了主键与辅助索引的 B+ 树的结构。
所谓的聚集非聚集是针对叶结点的 data 中是否存储有完整的数据记录来区分的,MyISAM 中 data 只存储数据记录的地址,因而是非聚集索引。
聚集索引存储引擎 InnoDB
此处同样借用他人的图片进行说明。
索引详解
索引分类
普通索引和唯一索引
普通索引
数据库中的基本索引类型,允许在定义索引的列中插入重复值和空值
唯一索引
索引列的值必须唯一,但允许有空值,主键索引是一种特殊的唯一索引,不允许有空值(比如自增ID)
单列索引和组合索引
单列索引
即一个索引只包含单个列,一个表可以有多个单列索引
组合索引
指在表的多个字段组合上创建的索引,只有在查询条件中使用了这些字段的左边字段时,索引才会被使用
聚簇索引与非聚簇索引
聚簇索引
以innodb为例,在一个数据table中,它的数据文件和索引文件是同一个文件。即在查询过程中,找到了索引,便找到了数据文件。**在innodb中,即存储主键索引值,又存储行数据,称之为聚簇索引**。
innodb索引,指向主键对数据的引用。非主键索引则指向对主键的引用。innodb中,没有主见索引,则会使用unique索引,没有unique索引,则会使用数据库内部的一个行的id来当作主键索引。
在聚簇索引中,数据会被按照顺序整理排列,当使用where进行顺序、范围、大小检索时,会大大加速检索效率。非聚簇索引在存储时不会对数据进行排序,相对产生的数据文件体积也比较大。
非聚簇索引
不是聚簇索引,就是非聚簇索引
以myisam为例,一个数据表table中,它是有table.frm、table.myd以及table.myi组成。table.myd记录了数据,table.myi记录了索引的数据。在用到索引时,先到table.myi(索引树)中进行查找,取到数据所在table.myd的行位置,拿到数据。所以myisam引擎的索引文件和数据文件是独立分开的,则称之为非聚簇索引,myisam类型的索引,指向数据在行的位置。即每个索引相对独立,查询用到索引时,索引指向数据的位置。
全文索引
类型为FULLTEXT
,在定义索引的列上支持值的全文查找,允许在这些索引列中插入重复值和空值。全文索引可以在CHAR、VARCHAR或者TEXT类型的列上创建,MySQL中只有MyISAM存储引擎支持全文索引
覆盖索引
覆盖索引(Covering Index),一说为索引覆盖。
理解方式一:就是select的数据列只用从索引中就能够取得,不必读取数据行,MySQL可以利用索引返回select列表中的字段,而不必根据索引再次读取数据文件,换句话说查询列要被所建的索引覆盖。
理解方式二:索引是高效找到行的一个方法,但是一般数据库也能使用索引找到一个列的数据,因此它不必读取整个行。毕竟索引叶子节点存储了它们索引的数据;当能通过读取索引就可以得到想要的数据,那就不需要读取行了。一个索引包含了(或覆盖了)满足查询结果的数据就叫做覆盖索引
注意
如果要使用覆盖索引,一定要注意select列表中只取出需要的列,不可select ,因为如果将所有字段一起做索引会导致索引文件过大,查询性能下降。
所以,千万不能为了查询而在所有列上都建立索引,会严重影响修改维护的性能。
设计原则
索引设计不合理或者缺少索引都会对数据库和应用程序的性能造成障碍,高效的索引对于获得良好的性能非常重要。
- 索引并非越多越好,一个表中如有大量的索引,不仅占用磁盘空间,而且会影响
INSERT、DELETE、UPDATE
等语句的性能,因为当表中的数据更改的同时,索引也会进行调整和更新 - 避免对经常更新的表设计过多的索引,并且索引中的列尽可能要少,而对经常用于查询的字段应该创建索引,但要避免添加不必要的字段
- 数据量小的表最好不要使用索引,由于数据较少,查询花费的时间可能比遍历索引时间还要短,索引可能不会产生优化效果
- 在条件表达式中经常用到的不同值较多的列上建立索引,在不同值较少的列上不要建立索引,比如性别字段只有男和女,就没必要建立索引。如果建立索引不但不会提高查询效率,反而会严重降低更新速度
- 当唯一性是某种数据本身的特征时,指定唯一索引。使用唯一索引需能确保定义的列的数据完整性,以提高查询速度
- 在频繁排序或分组(即group by或order by操作)的列上建立索引,如果待排序的列有多个,可以在这些列上建立组合索引
创建表时创建索引
使用 CREATE TABLE 创建表的时候,除了可以定义列的数据类型,还可以定义主键约束、外键约束或者唯一性约束,而不论创建哪种约束,在定义约束的同时相当于在指定列上创建了一个索引。
语法
创建表时创建索引的基本语法如下
1 | CREATE TABLE table_name[col_name data_type] |
释义
- UNIQUE、FULLTEXT和SPATIAL为可选参数,分别表示唯一索引、全文索引和空间索引
- INDEX和KEY为同义词,二者作用相同,用来指定创建索引
- col_name为需要创建索引的字段列,该列必须从数据表中该定义的多个列中选择
- index_name为指定索引的名称,为可选参数,如果不指定则MySQL默认col_name为索引值
- length为可选参数,表示索引的长度,只有字符串类型的字段才能指定索引长度
- ASC或DESC指定升序或者降序的索引值存储
查看索引
1 | SHOW INDEX FROM table_name |
普通索引
1 | -- 这句作用是,如果 customer1 存在就删除 |
唯一索引
单列索引是在数据表中的某一个字段上创建的索引,一个表中可以创建多个单列索引,前面两个例子中创建的索引都是单列索引,比如:
1 | DROP TABLE |
这样就代表在表的customer_id
字段上创建了一个名为idx_customer_id
的唯一索引
组合索引
组合索引是在多个字段上创建一个索引,比如:
1 | DROP TABLE |
这就为customer_id、customer_name
两个字段成功创建了一个名为idx_group_customer
的组合索引,通过SHOW INDEX FROM customer1;
全文索引
全文索引可以对全文进行搜索,只有MyISAM存储引擎支持全文索引,并且只为CHAR、VARCHAR和TEXT列,索引总是对整个列进行,不支持局部索引,比如:
1 | DROP TABLE |
因为默认的存储引擎为InnoDB
,而全文索引只支持MyISAM
,所以这里创建表的时候要手动指定一下引擎。
看到这么创建,就在info字段上成功建立了一个名为idx_fulltext_customer_name
的FULLTEXT全文索引,全文索引非常适合大型数据库,而对于小的数据集,它的用处可能比较小。
已存在的表上创建索引
在已经存在的表上创建索引,可以使用ALTER TABLE语句或者CREATE INDEX语句,所以,分别讲解一下如何使用ALTER TABLE和CREATE INDEX语句在已知的表字段上创建索引。
语法
ALTER TABLE创建索引的基本语法为:
1 | ALTER TABLE table_name ADD [UNIQUE|FUUTEXT|SPATIAL] |
普通索引
1 | ALTER TABLE customer1 ADD INDEX idx_customer_id(`customer_id`); |
意思是查询的时候,只需要检索前面50个字符。这里专门提一下,对字符串类型的字段进行索引,如果可以尽可能的指定一个前缀长度,例如,一个CHAR(255)的列,如果在前10个或者前30个字符内,多数值是唯一的,则不需要对整个列进行索引,短索引不仅可以提高查询速度而且可以节省磁盘空间、减少I/O操作。
唯一索引
1 | ALTER TABLE customer1 ADD UNIQUE INDEX `idx_customer_id` (`customer_id`); |
组合索引
1 | ALTER TABLE customer1 ADD INDEX `idx_group_customer` (`customer_id`,`customer_name`); |
创建索引
CREATE INDEX语句可以在已经存在的表上添加索引,MySQL中CREATE INDEX被映射到一个ALTER TABLE语句上。
语法
1 | CREATE [UNIQUE|FULLTEXT|SPATIAL] INDEX index_name ON table_name(col_name[length],...)[ASC|DESC] |
看到和ALTER INDEX语句的语法基本一样,下面把 customer1
表删除了再创建,所有字段都没有索引,用CREATE INDEX语句创建一次索引:
普通索引
1 | CREATE INDEX idx_customer_id ON customer1(`customer_id`); |
唯一索引
1 | CREATE UNIQUE INDEX idx_customer_id ON customer1(`customer_id`); |
组合索引
1 | CREATE INDEX idx_group_customer ON customer1(`customer_id`,`customer_name`); |
删除索引
最后一项工作就是删除索引了,可以使用
ALTER TABLE和DROP INDEX
删除索引。
ALTER TABLE 语法
ALTER TABLE的基本语法为:
1 | ALTER TABLE table_name DROP EXISTS index_name; |
建议大家使用第二条
DROP INDEX 语法
DROP INDEX的基本语法为:
1 | DROP INDEX index_name ON table_name |
建议大家使用第二条
注意一个细节,删除表中的列时,如果要删除的列为整个索引的组成部分,则该列也会从索引中删除;如果组成索引的所有列都被删除,则整个索引将被删除