Mysql中的索引
Mysql索引类型
- Primary key/主键索引,Innodb 中又叫聚簇索引,InnoDB存储引擎的表会存在主键（唯一非null），如果建表的时候没有指定主键，则会使用第一非空的唯一索引作为聚集索引，否则InnoDB会自动帮你创建一个不可见的、长度为6字节的row_id用来作为聚集索引。
- 单列索引:索引中只包含一个列。
- 组合索引:在多个字段上建立的索引,只有在查询条件中顺序的使用了这些索引,索引才有效果。使用组合索引遵循最左前缀原则。
- Unique(唯一索引):索引列必须唯一,但允许有空值,若是组合索引,则列值的组合必须保持唯一。
- Key(普通索引),是MySQL中基本的索引类型,允许列中有空值,重复值。
- FULLTEXT(全文索引):全文索引类型为FULLTEXT，在定义索引的列上支持值的全文查找，允许在这些索引列中插入重复值和空值。全文索引可以在CHAR、VARCHAR或者TEXT类型的列上创建
- SPATIL(空间索引):空间索引是对空间数据类型的字段建立的索引，MySQL中的空间数据类型有4种，分别是GEOMETRY、POINT、LINESTRING和POLYGON。MySQL使用SPATIAL关键字进行扩展，使得能够用于创建正规索引类似的语法创建空间索引。创建空间索引的列必须声明为NOT NULL
image-20210616154139828
常见的问题
索引为什么要使用B+树
聚簇索引和非聚簇索引的区别
索引什么时候会失效,最左匹配原则是什么
sql语句的执行顺序
from
join
on
where
group by(开始使用select的别名,后面的语句都可以使用)
avg,sum...(各种函数)
having
select
distinct
order by
limit
所有的查询都是从
from开始的,在执行过程中,每个步骤都会为下一个步骤生成一个虚拟表vt1(选择相对较小的表做基础表)
一条sql是怎么样执行的
- 应用程序通过账户名,密码连接到Mysql数据库服务器,然后将sql语句发送到Mysql服务器。
- 查询缓存:接着Mysql服务器会去查询缓存,看看是不是有这条sql的缓存结果,key是查询的语句,value的查询到的结果集。如果能直接命中缓存,则直接返回。
- 查询优化:生成执行计划
- 1.解析sql语句,生成解析树,验证语法是否正确(如:select,from关键字)是否正确。
- 2.预处理,进一步检查语法树是否合法,检查所查询的表是否存在,验证用户权限。
- 3.优化sql:决定使用哪个索引,或者多表进行关联的时候决定表的链接顺序。接着生成执行计划。
- 将查询结果返回客户端(如果查询可以被缓存,Mysql也会将结果放到查询缓存)
什么是索引
索引是一种数据结果,用来提高获取数据的效率。
索引的分类
- Btree索引(B+tree,B-tree)
- 哈希索引
- full-index(全文索引)
- Rtree
从应用层次上来分
- 普通索引
- 唯一索引
- 组合索引
- 主键索引
- 空间索引
从记录和索引的排列顺序上来分
- 聚簇索引:索引的排列方式和数据的排列方式是一样的。
- 非聚簇索引:索引的排列方式和数据的排列方式不一样。
聚簇索引和非聚簇索引的区别
- 聚簇索引就是主键上创建的索引。聚簇索引在叶子节点存储的都是表的数据。
- 非聚簇索引就是非主键上创建的索引。非聚簇索引在叶子节点存储的是主键和索引列。
聚簇索引
聚簇索引的排列顺序和记录的排列顺序是一致的，所以查询比较快,只要找到一个索引值记录,其余连续性的记录在物理表也会连续存放
缺点是:新增比较慢,为了保证索引的排列顺序和记录的排列顺序是一致的，在插入数据的时候,会对数据进行重新排序。
非聚簇索引,索引的逻辑顺序和磁盘上物理存储顺序不一样,非聚簇索引在叶子节点存储的是主键和索引列,当我们使用非聚簇索引查询数据时,需要拿到叶子节点上的主键在去表中查需要的数据,这个过程叫做回表。
Mysql创建索引
创建主键索引
> alter table `rumenz` add primary key(`id`);
创建唯一索引
> alter table `rumenz` add unique(`name`);
创建普通索引
> alter table `rumenz` add index index_name(`name`);
添加全文索引
> alter table `rumenz` add fulltext(`content`);
创建联合索引
> alter table `rumenz` add index_name(`name`,`age`);
索引的底层数据结构
哈希索引
采用哈希算法,和hashmap类似,之需要一次哈希算法就可以马上定位,速度非常快,本质就是把索引列换算成哈希值,根据这个哈希值进行定位查找。
哈希索引的缺点
- 哈希索引没有办法利用索引完成排序
- 不能进行多字段查询
- 在有大量重复键值的情况下,哈希索引的效率也是很低的(哈希碰撞问题)
- 不支持范围查询
如何高效设计索引的数据结构
MySQL的存储结构
表存储结构
MySQL为什么要使用B+树索引？
表->段->区->页->行
在数据库中,不论读哪一行数据,还是读多行数据,都是将这些行所在的页进行加载。也就是存储空间的基本单位就是页。
一个页就是一颗B+树的节点,数据库I/O操作的最小单位是页,与数据库相关的内容都会存储在页的结构里。
img
- 在一棵B+树中,每个节点都是一个页,每次新建节点的时候,就会新建一个页。
- B+数的同一层节点中,通过页的结构构成一个双向链表
- 非叶子节点,包括了多个索引行,每个索引行里面存储了索引键和指向下一页面的指针
- 叶子节点存储了关键字和行记录,在节点内部(也就是页结构的内部)记录的是一个单向链表
B+树页节点结构
img
- 将所有的记录分组,每组都会存储多条记录
- 页目录存储的是㯾(slot),㯾相当于分组记录的索引,每个㯾指针都指向每个分组的最后一条记录。
- 我们通过㯾定位到组,然后在分组里面找到记录
页的最主要目录是存储记录,页中的记录是以单链表形式存储的。单链表的有点是插入，删除方便,缺点是检索效率不高,最坏的情况要遍历所有节点。因此页目录中提供了二分查找,来提高检索的效率
B+树的检索过程
- 从B+树的跟开始,逐层找到叶子节点
- 找到叶子节点对应的数据页,将数据页加载到内存中,通过页目录的㯾大致找到数据所在的分组
- 在分组中通过聊表的遍历找到记录
B+树的演变
二叉查找树（二叉搜索树）：不平衡
img
我们为 user 表（用户信息表）建立了一个二叉查找树的索引。
图中的圆为二叉查找树的节点，节点中存储了键（key）和数据（data）。键对应 user 表中的 id，数据对应 user 表中的行数据。
二叉树的特点是:任何节点的左子节点的键值都小于当前节点的键,右子节点的键值都大于当前节点的键值。顶端的节点被称为根节点,没有子节点的节点我们称为叶子节点。
查找 id=12 的用户信息，利用我们创建的二叉查找树索引，查找流程如下
- 将根节点作为当前节点,把12与当前节点的键值10比较,12大于10,接着我们把当前节点的右子节点当成当前节点。
- 继续把12和当前节点的键值13比较,12小于13,接着把当前节点的左子节点当成当前节点。
- 把12和当前节点的键值12比较,12等于12,满足条件,我们从当前节点取出数据,id=12,name=xm
平衡二叉树(AVL树):旋转耗时
利用二叉树可以快速找到数据,但是,如果上面的二叉树是上面的结构,则二叉树就会变成一个链表。如果我们需要查找id=17的用户信息,我们需要需要查找7次,相当于全表扫描了,效率很低。——于是我们就有了平衡二叉树。
2
平衡二叉树又称AVL树,在满足二叉树特性的基础上,要求每个节点的左右子树的高度差不能超过1。
平衡二叉树和非平衡二叉树的对比
3
当不平衡时,则需要调整二叉树的平衡。
红黑树:树太高
红黑树与AVL相比,红黑树并不追求严格的平衡,而是大致的平衡,只是确保从根到叶子的最长路径不多于最短的可能路径的两倍长。红黑树最大的特点是每个节点都属于两种颜色(红色或黑色)之一,且节点颜色的划分需要满足下面的规则。
- 每个节点要么黑色,要么白色
- 根节点是黑色
- 每个叶节点(NIL结点，空结点)是黑色的
- 不能有相邻的两个红色结点
- 在一条路径上不能有相邻的两个红色节点
- 从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点
下面是一颗标准的红黑树
img
红黑树与AVL树相比,红黑树的查询效率会有所下降,这是因为树的平衡性变差,高度更高。
但红黑树的删除效率大大提高了，因为红黑树同时引入了颜色，当插入或删除数据时，只需要进行O(1)次数的旋转以及变色就能保证基本的平衡，不需要像AVL树进行O(lgn)次数的旋转。总的来说，红黑树的统计性能高于AVL。
因此在实际中AVL树使用相对比较少,而红黑树使用非常广泛。如Java中的TreeMap使用红黑树存储排序键值对。Java8中的HashMap使用链表+红黑树解决哈希冲突问题(当冲突比较少的时候,使用链表,当冲突多的时候采用红黑树)
在数据再内存中的情况(如上述的TreeMap和HashMap),红黑树的表现是非常好的。但是对于数据在磁盘等辅助存储的设备情况中(如:Mysql数据库),红黑树并不适用,因为红黑树相对很高。当数据在磁盘中时,磁盘IO会成为性能瓶颈,设计的目标应该是降低IO次数,而树的高度越高,增删改查所需要的IO次数也会越多,会严重影响性能。
B树:降低磁盘IO
- 为什么要使用B树
内存的大小有限,并且容易丢失,所以像数据库这种应用会把数据和索引存放到磁盘这种外围设备中。但是磁盘的读取速度相比与内存会差百,千倍,所以我们应该尽量减少查磁盘的次数。
从磁盘中读取数据时,都是按磁盘块来读取的,并不是一条一条读的,如果我们尽可能多的把数据放进磁盘块中,那么一次磁盘读取就会读取更多的数据,那么查询数据的时间也就会降低。如果我们使用树这种数据结构作为索引的数据结构,那我们每查找一次数据就要从次磁盘中读取一个节点,也就是我们说的磁盘块。平衡二叉树可是每个节点只存储一个键值和数据的。那说明什么？说明每个磁盘块仅仅存储一个键值和数据！那如果我们要存储海量的数据呢？可以想象到二叉树的节点将会非常多，高度也会极其高，我们查找数据时也会进行很多次磁盘 IO，我们查找数据的效率将会极低！
数据库要存海量数据,AVL树每个节点只会存储一个键值和数据,并且数据是存储在磁盘上的,当我们存储一个数据时,速度会很慢,应该减少从磁盘读取数据的次数。当我们使用AVL树,树的高度会很高,会进行多次磁盘IO,效率会很低。
因为要存储的数据是海量的,AVL每个节点只能存储一个键值和数据,并且数据存储在磁盘上,当我们存储一个数据,速度会很慢,我们应该减少读取磁盘的次数,使用AVL树,树的高度会很高,会进行很多次磁盘IO,查找数据的效率会非常的低。
img
为了解决AVL树这个弊端,我们需要找到一个单节点能存储多个键值和数据的平衡树,也就是下面要说的B树
B平衡树,又叫做B-树
img
图中的p节点为指向子节点的指针,二叉查找树和平衡二叉树也有。
图中的每个节点称为页,页就是我们上面说的磁盘块,在MySQL中数据读取的基本单位是页,所以我们这里叫做页更符合MySQL中索引的底层数据结构。
B树相对于平衡二叉树,每个节点存储了更多的键值(key)和数据(data),并且每个节点有更多的子节点,最多子节点的个数一般称为阶。
image-20210621115010194
基于这个特性，B 树查找数据读取磁盘的次数将会很少，数据的查找效率也会比平衡二叉树高很多。
应用：B树在数据库中有一些应用，如mongodb的索引使用了B树结构。但是在很多数据库应用中，使用了是B树的变种B+树。
B+树
img
B+树和B树的区别
- B+树非叶子节点是不存储数据的,仅存储键值和子节点的指针,而B树节点不仅存储键值也会存储数据。
数据库中页的大小是固定的,InnoDB中页的默认大小是16KB,如果不存储数据,就会存储更多的键值,相应的树的阶数(节点的子节点数)就会越大,所构建成的树就会又矮又胖,这样每次查数据的磁盘IO就会更少,数据查询效率更快。
- B+树所有的数据均存储在叶子节点,而且数据是按照顺序存放的。
使用B+树进行范围查找,顺序查找,分组查找,去重相当容易,因为B+树的数据是按顺序存放的。而B树的数据分散在每个节点,要实现这一点很困难。B+树各个页之间之通过双向链表来连接的，叶子节点的数据是用单向链表进行连接的。在 InnoDB 中，我们通过数据页之间通过双向链表连接以及叶子节点中数据之间通过单向链表连接的方式可以找到表中所有的数据。MyISAM 中的B+树和InnoDB中的实现有一点区别,MyISAM中的B+树的叶子节点存放的是数据文件的地址。
为什么B+树比B树更适合做索引
B树在提高了IO性能的同时并没有解决数据遍历效率低下的问题,B+树只需要遍历叶子节点就能遍历真个树,数据的范围查找非常普遍,而B树就不支持这样的操作。
- B+树的非叶子节点不存放数据,B树的非叶子节点存储数据
- B+树的查询效率更高。B+树采用双向链表串联所有的叶子节点,区间查询效率更高,但是B树要通过中序遍历才能完成范围查询
- B+树的查询效率更稳定,B+树每次需要查到叶子节点才能找到数据,而B树查询的数据可能不在叶子节点,所以查询效率不稳定。
- B+树查询数据的磁盘IO更少。B+树内存节点并没有指向具体的数据,因此其内部节点相比B树更小,通常B+树更矮更胖,高度小查询磁盘的IO更少。
聚簇索引和非聚簇索引
在Mysql中B+树索引按照存储方式的不同分为聚集索引和非聚集索引。
- 聚集索引:,以InnoDB作为存储引擎的表,表中的数据都会有一个主键,即使你不创建主键,系统也会隐式的创建一个主键,这是因为InnoDB是把所有的数据都放到了B+树里面,而B+树的键值就是主键,在B+树的叶子节点存放了所有的数据。
- 非聚集索引:以主键以外的键值构建的B+树索引,我们称之为非主键索引。非聚集索引与聚集索引的区别在于非聚集索引的叶子节点不存储表中的数据，而是存储该列对应的主键，想要查找数据我们还需要根据主键再去聚集索引中进行查找，这个再根据聚集索引查找数据的过程，我们称为回表。
相关命令