索引是什么?为什么要使用索引?
以前学数据结构时学了ArrayList,我们可以往里面存放数据
但是有问题,也就是说当程序重启或是电脑关机之后,数据就没有了,为什么?
因为他的数据是保存在内存中的
数据库把数据保存在磁盘中,就可以完成对数据的持久化
内存与外存的区别 内存：容量小造价高速度快，断电后数据丢失 外存：容量大造价低速度慢断电后数据不丢失,只要写入就是永久保存索引是一种特殊的文件,包含着对数据表里所有记录的引用指针。可以对表中的一列或多列创建索引，并指定索引的类型,各类索引有各自的数据结构实现。
索引作用：
数据库中的表、数据、索引之间的关系,类似于书架上的图书、书籍内容和书籍目录的关系。
索引所起的作用类似书籍目录,可用于快速定位、检索数据。
索引对于提高数据库的性能有很大的帮助。MySQL的索引是一种数据结构,它可以帮助数据库高效地查询、更新数据表中的数据。索引通过一定的规则排列数据表中的记录,使得对表的查询可以通过对索引的搜索来加快速度。
不同的数据结构都有自己实现的规则,不同的规则导致不同数据结构的效率不同
最终时间复杂度和空间复杂度不同2.2为什么要使用索引? MySQL实现的两个关键目标,安全,效率 显而易见,使用索引的目的只有一个,就是提升数据检索的效率,在应用程序的运行过程中,查 询操作的频率远远高于增删改的频率。
索引应该选择哪种数据结构
1.HASH
时间复杂度是0(1),查询速度非常快,但是MySQL并没有选择HASH做为索引的默认数据结
构,主要原因是HASH不支持范围查找2.二叉搜索树
中序遍历是一个有序序列-->支持范围查找
时间复杂度:可能会退化成一个单边树O(N)
节点个数过多时,无法保证树的高度
由于数据库中的数据是在磁盘上保存的,每一次访问子节点都会发生一次磁盘IO
磁盘IO是制约数据库性能的主要因素3.N叉树
每个节点可以有超过两个的子节点,可以解决树高的问题
度或阶,每一个节点最多有多少个子节点,一般子节点的个数小于度的值
时间复杂度:0(logN)
在数据量相同的情况下,可以有效的控制树高,也就是说可以使用更少的IO次数找到目标节点,从而提高数据库的效率通过观察,相同数据量的情况下,N叉树的树高可以得到有效的控制, 也就意味着在相同数据量的情况下可以减少IO的次数,从而提升效率。 但是MySQL认为N叉树做为为索引的数据结构还不够好。
B+树
B+树是一种经常用于数据库和文件系统等场合的平衡查找树,MySQL索引采用的数据结构,以4阶B+树为例,如下图所示:
B+树的特点！！！！！！
能够保持数据稳定有序,插入与修改有较稳定的时间复杂度
非叶子节点仅具有索引作用,不存储数据,所有叶子节点保真实数据
所有叶子节点构成一个有序链表,可以按照key排序的次序依次遍历万全部数据B+树与B树的对比！！！！
B+树与B树对比
1.叶子节点之间有一个相互连接的引用,可以通过一个叶子节点找到它相信的兄弟节点，MySQL在组织叶子节点时使用的是双向链表
2.非叶子节点的值都包含在叶子节点中，MySQL非叶子节点只保存了对子节点的引用,没有保存真实的数据,所有真实的数据都保存在叶子节点中
3.对于B+树而言,在相同树高的情况下,查找任一元素的时间复杂度都一样,性能均衡时间复杂度:0(logN)：可以有效的控制树高
MySQL中的页
为什么要使用页：
在.ibd文件中最重要的结构体就是Page(页),页是内存与磁盘交互的最小单元,默认大小为16KB，每次内存与磁盘的交互至少读取一页,所以在磁盘中每个页内部的地址都是连续的,之所以这样做,是因为在使用数据的过程中,根据局部性原理,将来要使用的数据大概率与当前访问的数据在空间上是临近的,所以一次从磁盘中读取一页的数据放入内存中,当下次查询的数据还在这个页中时就可以从内存中直接读取,从而减少磁盘l/0提高性能！！！
Linux操作系统中管理文件的最小单位是4KB MySQL作为一个数据库程序,以4KB大小管理数据显然太少了,所以定义 了16KB一页的默认页大小当从内存中往磁盘里写数据页的时候,写到一半操作系统挂了,这时MySQL应该如何保证数据安全?
在落盘之前会记录各种日志,保证重启之后可以找到没有落盘的数据内容！！！！在MySQL中有多种不同类型的页,最常用的就是用来存储数据和索引引的"索引页",也叫做"数据页",但不论哪种类型的页都会包含页头和页尾,页的主体信息使用数据"行"进行填充,数据页的基本结构如下图所示:
页文件头和页文件尾
这里我们只关注,上一页页号和下一页页号,通过这两个属性可以把页与页之间链接起来,形成一个双向链表。
通过页号和页大小,可以计算出下一页和上一页在磁盘上的偏移量
页主体 页目录
页主体部分是保存真实数据的主要区域,每当创建一个新页,都会自动分配两个行,一个是页内最小行Infimun,另一个是页内最大行Supremun,这两个行并不存储任何真实信息,而是做为
数据行链表的头和尾,第一个数据行有一个记录下一行的地址偏移量的区域next_record将页
内所有数据行组成了一个单向链表,此时新页的结构如下所示:
页中的数据行是一个单向链表
页目录：
计算三层树高的B+树可以存放多少条记录
索引页中存的是主键值和子节点的引用,也就是下一节点的偏移(地址)
主键bigint 8Byte,下一页地址6Byte,也就是说一条索引记录占8+6=14Byte
一个索引页可以存16*1024/14=1170
理论上一个三层树高的B+树可以存:1170*1170*16=21,902,400条记录在当前的场景下,表中有21,902,400条记录的情况下,通过三次IO就可以完成数据的查询
以上的I0过程,加载索引页1-->加载索引页2-->加载数据页3 3次IO
把索引页加载到内存中进行缓存,当查一条没有加载过的数据时,一次真实IO就可以搞定这里查询1次是因为 索引页已经被缓存了 当索引内缓存到内存后 查询数据时 会在内存中遍历索引 这里没有IO 通过索引来找到目标数据页的磁盘地址,然后再从磁盘中进行IO读取这里的IO表示的是磁盘IO 因为MySQL的数据其实是存在硬盘中的 这也就是在大型项目中为什么使用redis作为缓存的原因 因为从磁盘读取数据太慢了 redis也是依靠内存的nosql数据库 查询起来会很快
索引分类
1主键索引
自动创建索引,索引的值是主键列的值！！！
当在一个表上定义一个主键PRIMARYKEY时,InnoDB使用它作为聚集索引--聚簇索引
推荐为每个表定义一个主键。如果没有逻辑上唯一且非空的列或列集可以使用主键,
则添加一个自增列。2普通索引
为了提升查询效率,工作中通常为查询频繁的列创建索引
普通索引是最基本的索引类型,没有唯一性的限制。可以包含一个列也可以包含多个列。
可能为多列创建组合索引,称为复合索引或组全索引3.唯一索引
当在一个表上定义一个唯一键UNQUE时,自动创建唯一索引。
与普通索引类似,但区别在于唯一索引的列不允许有重复值。目的是为了去标识唯一性
4.全文索引
基于文本列上创建,以加快对这些列中包含的数据查询和DML操作
用于全文搜索,仅MyISAM和InnoDB引擎支持。6.5聚集索引
与主键索引是同义词
如果没有为表定义PRIMARYKEY,InnoDB使用第一个UNIQUE和NOT NULL的列作为聚集索引。聚集索引可以标识数据行的唯一性
如果表中没有PRIMARY KEY或合适的UNIQUE索引,InnoDB会为新插入的行生成一个行号并
用6字节的ROW_ID字段记录,ROW_ID单调递增,并使用ROW_ID做为索引。6非聚集索引
聚集索引以外的索引称为非聚集索引或二级索引
二级索引中的每条记录都包含该行的主键列,以及二级索引指定的列。
InnoDB使用这个主键值来搜索聚集索引中的行,这个过程称为回表查询
7索引覆盖
当一个select语句使用了普通索引且查询列表中的列刚好是创建普通索引时的所有或部分列,这时
就可以直接返回数据,而不用回表查询,这样的现象称为索引覆盖
