索引的介绍

目录

1.索引的介绍

1.1 什么是索引

1.2 为什么要使用索引

2.索引应该选择哪种数据结构

 3.MYSQL中的页

3.1为什么要使用页

3.2页文件头和页文件尾 

 3.3 页主体

3.3页目录

 3.4数据页头

 4.B+在MYSQL索引中的应用

4.1计算三层树高的B+树可以存放多少条记录

5.索引分类

5.1 主键索引

5.2普通索引

5.3 唯一索引

5.4 全文索引

5.5 聚集索引

5.6 非聚集索引

5.7索引覆盖

1.索引的介绍

1.1 什么是索引

        MYSQL的索引是一种数据结构，它可以帮助数据库高效地查询、更新数据表中的数据。索引通过一定的规则排列数据表中的记录，使得表的查询可以通过对索引的搜索来加快速度。MYSQL索引类似于书籍的目录，通过指向数据行的位置，可以快速定位和访问表中的数据，比如汉语字典的目录页，我们可以按照笔画、偏旁部首、拼音等的目录（索引）快速查找需要的字。

1.2 为什么要使用索引

使用索引的目的只有一个，就是提升数据检索的效率，在应用程序的运行过程中，查询操作的频率远远高于增删该的评率

2.索引应该选择哪种数据结构

• HASH

时间复杂度：O（1）

HASH是将存储的元素通过hash函数（存储位置 =  存储元素  % 容量 ）找到存储位置使它们之间形成一种映射关系，查找的时候也是将查找的元素进行hash来查找元素，因此不支持范围查找。

最重要的数据结构没有之一，但是不支持范围查找

• 二叉搜索树

时间复杂度 最好为：O（logN）最坏为一个单边树：O（N）

二叉搜索树的查找是先与根节点比较，再决定是往左还是往右查找。中序遍历是一个有序序列同时支持范围查找 ，但是可能会退化一个单边树使节点数过多让时间复杂度变为最坏情况

使得每次访问子节点都会发生一次磁盘 IO，磁盘IO是制约数据库性能的主要因素

•  N叉树

时间复杂度为：O（logN）

N叉树每个节点可以有超过两个的子节点，可以解决树的高度问题。同时，在数据量相同的情况下，可以有效的控制树的高度，也就是说可以使用更少的IO次数找到目标节点，从而提高数据库的效率

N树的介绍

以上的数字称为度或阶，该数字表示每一个节点最多有多少个子节点，一般子节点的个数小于度的值，如果数字为四最多有三个节点

例如：度为3时先插入两个节点如图所示，接着插入40时变成第二副图

•  B+树

B+数绍 

B+树是一种经常用于数据库和文件系统等场合的平衡查找树，MYSQL索引采用的数据结构，以4阶B+树为例，如图所示：

时间复杂度：O（logN）

优点：可以有效的控制树高

B+树与B树对比

1.  B+树叶子节点之间有一个相互连接的引用，可以通过一个叶子节点找到它相信的兄弟节点    

     MYSQL在组织叶子节点时使用的是双向链表

2.  B+树非叶子节点的值都包含在叶子节点中

     MYSQL非叶子节点只保存了对叶子节点的引用，没有保存真实的数据，所有真实的数据       都保存在叶子节点中

3.  对于B+树而言，在相同树高的情况下，查找任意元素的时间复杂度都一样，性能均衡

 3.MYSQL中的页

3.1为什么要使用页

在.ibd文件中最重要的结构体就是页，页是内存与磁盘交互的最小单位，默认大小为16KB，每次内存与磁盘的交互至少读取一页，所以在磁盘中每个页内部的地址都是连续的，之所以这样做，是因为使用数据的过程中，根据局部性原理，将来要使用的数据大概率与之前访问的数据在空间上是临近的，所以一次从磁盘中读取一页的数据放入内存中，下次查询的数据还在这个页中时就可以从内存中直接读取，从而减少磁盘IO提高性能

 16384（字节）/1024 = 16KB（1024个字节 = 1KB）

 MYSQL中有很多页类型，这里只讨论数据页或称为索引页

3.2页文件头和页文件尾 

页文件头和页文件尾中包含的信息，如下图所示：当前页文件的主要信息，这里我们只关注上一页页号和下一页页号，通过这两个属性可以把页与页之间连接起来，形成一个双向链表。

 3.3 页主体

页主体部分是保存真实数据的主要区域，每当创建一个新页，都会自动分配两个行，一个是页内最小行Infimun，另一个是页内最大行Supremun，这两个行并不储存任何真实信息，而是做为数据行链表的头和尾，第一个数据行有一个记录下一行的地址偏移量的区域next_record将页内所有数据行组成一个单向链表，此时新页的结构如下所示：

 当向一个新页插入数据时，将Infimun连接第一个数据行，最后一行真实数据行连接连接Supremun，这样数据行就构成了一个单向链表，更多的行数据插入以后，会按照主键从小到大的顺序进行连接，如上图所示。

3.3页目录

 3.4数据页头

数据页头记录了当前页保存数据相关的信息，如下图所示

 4.B+在MYSQL索引中的应用

非叶子节点保存索引数据，叶子节点保存真实数据，如下图所示

4.1计算三层树高的B+树可以存放多少条记录

理论上：

一个数据页默认16KB，假设一条数据1KB，一页中至多可以存16条数据

• 假设⼀条⽤⼾数据⼤⼩为1KB，在忽略数据⻚中数据⻚⾃⾝属性空间占⽤的情况下，⼀⻚可以存16 条数据
• 索引⻚⼀条数据的⼤⼩为，主键⽤BIGINT类型占8Byte，下⼀⻚地址6Byte，⼀共是14Byte，⼀个 索引⻚可以保存 16*1024/14 = 1170 条索引记录
• 如果只有三层树⾼的情况，综合只保存索引的根节点和⼆级节点的索引⻚以及保存真实数据的数据 ⻚，那么⼀共可以保存 1170*1170*16 = 21,902,400 条记录，也就是说在两千多万条数据的 表中，可以通过三次IO就完成数据的检索

5.索引分类

5.1 主键索引

1. 当在一个表上定义一个主键PRIMARY KEY时（自动创建索引，索引的值是主键列的值），InnoDB使用它作为聚集索引。
2. 推荐为每个表定义的一个主键。如果没有逻辑上唯一且非空的列或列集可以使用主键，则添加一个自增例。

5.2普通索引

1. 最基本的索引类型，没有唯一性的限制。
2. 可能为多列创建组合索引，称为复合索引或组全索引（创建索引之后会生成一颗索引树，创建多少索引生成多少棵索引树）

为了提升查询效率。工作中通常为查询频繁的列创建索引，列的重复度不高可以包含一个列也可以包含多个列

5.3 唯一索引

1. 当在一个表上定义一个唯一键UNQUE时，自动创建唯一索引。
2. 与普通索引类似，但区别在于唯一索引的列不允许有重复值。

5.4 全文索引

1. 基于文本列（CHAR、VARCHAR 或 TEXT列）上创建，以加快对这些列中包含的数据查询和DML操作
2. 用于全文搜索，仅MylSAM和InnoDB引擎支持

5.5 聚集索引

1. 与主键索引是同义词
2. 如果没有为表定义PRIMARY KEY，InnoDB使用第一个UNIOUE和NOT NULL的列作为聚集索引
3. 如果表中没有PRIMARY KEY 或者合适的 UNIOUE 索引，InnoDB会为新插入的行生成一个行号并用6字节的ROW_ID（数据行中的一个隐藏列之一）单调递增，并使用ROW_ID做为索引。

5.6 非聚集索引

1. 聚集索引以外的索引称为非聚集索引或者二级索引
2. 二级索引中的每条记录都包含该行的主键列，以及二级索引指定的列
3. InnoDB使用这个主键值来搜索聚集索引中的行，这个过程称为回表查询

5.7索引覆盖

当一个select语句使用普通索引且查询列表的列刚好是创建普通索引时的所有或部分列，这时就可以直接返回数据，而不是用回表查询，这样的现象称为索引覆盖