好讲解：索引讲解
好讲解2: MySQL 的覆盖索引与回表 - 张德检的文章
DDL：DDL（Data Definition Languages）语句：数据定义语言，这些语句定义了不同的数据段、数据库、表、列、索引等数据库对象。常用的语句关键字主要包括create、drop、alter等。
DML（Data Manipulation Language）语句：数据操纵语句，用于添加、删除、更新和查询数据库记录，并检查数据完整性。常用的语句关键字主要包括 insert、delete、update和select等。
DCL（Data Control Language）语句：数据控制语句，用于控制不同数据段直接的许可和访问级别的语句。这些语句定义了数据库、表、字段、用户的访问权限和安全级别。主要的语句关键字包括grant、revoke等。
定义1：索引是 帮助MYSQL 高效获取数据的排好序的数据结构。
定义2：索引在mysql中是一种键，是存储引擎用来快速找到记录的一种数据结构。
定义3：数据库只做两件事情：存储数据、检索数据。而索引是在你存储的数据之外，额外保存一些路标（一般是B+树），以减少检索数据的时间。所以索引是主数据衍生的附加结构。
目的：索引的目的在于提高查询效率。
一张表可以建立任意多个索引，每个索引可以是任意多个字段的组合。索引可能会提高查询速度（如果查询时使用了索引），但一定会减慢写入速度，因为每次写入时都需要更新索引，所以索引只应该加在经常需要搜索的列上，不要加在写多读少的列上。
1.2 索引优缺点优点
- 大大加快检索速度
- 加快表与表之间的连接
- 使用分组group 和排序order字句的时候，可以显著减少查询中分组和排序的时间
排序查询的sql需求：树形的有序特性，能保持O(log(n))的高效率。
- 分组：group by
- 排序：order by
- 比较<, >
缺点
- 占用物理空间
- 创建和维护索引需要花费时间
按照物理地址和逻辑地址是否一致可以分为：聚集索引、非聚集索引（辅助索引、二次索引、普通索引）
- 聚簇索引：数据存放的物理顺序与逻辑顺序一致。按照主键索引构造B+树（没有就唯一索引、还没有就rowid），树中的叶子节点存放的是所有列的数据，也就是数据所在的物理地址。
- 非聚簇索引：数据存放的物理顺序与逻辑顺序不一致。按照辅助索引构建B+树，树中存放的是主键的索引值，根据主键和物理地址二次查找（即回表查询）去主键索引树查找数据。
非聚簇索引（普通索引、二级索引、辅助索引）需要先找到对应索引的主键，再通过主键索引树找到数据，进行二次查找，就叫回表查询
按功能分类
- 普通索引：它没有任何限制，允许在定义索引的列中插入重复值和空值
- 唯一索引：索引列的值必须唯一，允许有null值，如果是组合索引，列值的组合必须唯一（空值也只能一个字段有空值）
- 主键索引：主键索引是一种特殊的唯一索引，一个表只能有一个主键，不允许有空值，一般是在创建表的时候指定主键，主键默认就是主键索引
- 组合索引：多个字段上创建的索引，只有在查询条件中使用了创建索引时的第一个字段，索引才会被使用
- 全文索引：通过建立倒排索引，,解决判断字段是否包含的问题。
- 覆盖索引：一种特殊的联合索引，即你查询的字段所有数据都在索引上，不需要再进行一次回表查询，这样的索引即为覆盖索引。当sql语句的所求查询字段（select列）和查询条件字段（where子句）全都包含在一个索引中（联合索引），可以直接使用索引查询而不需要回表。这就是覆盖索引。
主键索引和普通索引查询
1 select * from t_user where id=1 2 //即主键查询方式，则只需要搜索id这棵B+树
1 select * from t_user where name="张三" 2 //即普通索引查询方式，则需要先搜索name索引树，得到id的值为3，再到id索引树搜索一次。这个过程称为回表1.4 聚集索引与非聚集索引
聚簇索引的逻辑顺序，就是数据在硬盘上的物理顺序。一般情况下主键就是默认的聚簇索引。对于经常更新的列不宜建立聚簇索引。
一旦具有第一个索引值的记录被找到，具有连续索引值的记录也一定物理地紧跟其后。
如果一张表上还没有聚簇索引，为它新创建聚簇索引时，就需要对已有数据重新进行排序，所以对表进行修改速度较慢是聚簇索引的缺点
如果有主键就使用主键，没有就使用唯一键，没有唯一键就使用6字节的rowid。
非聚集索引的逻辑顺序与数据爱硬盘上的物理顺序不同。
一张表只允许存在一个聚簇索引，因为真实数据的物理顺序只能有一种。
聚簇索引不一定是唯一索引，聚簇索引的索引值并不要求是唯一的，
唯一聚簇索引才是！
1.5.2 唯一索引与主键在一个有聚簇索引的列上是可以插入两个或多个相同值的，这些相同值在硬盘上的物理排序与聚簇索引的排序相同，仅此而已。
唯一索引是在表上一个或者多个字段组合建立的索引，这个（或这几个）字段的值组合起来在表中不可以重复。一张表可以建立任意多个唯一索引，但一般只建立一个。
主键是一种特殊的唯一索引，区别在于，唯一索引列允许null值，而主键列不允许为null值。一张表最多建立一个主键，也可以不建立主键。
1.5.3 索引和主键的区别- 可以在数据库设计器中创建三种索引：唯一索引、主键索引和聚集索引。而主键只是其中的一种。主键属于索引的一种。
- 主键用于强制表的实体完整性，聚集索引用来对数据行排序，方便查询用。
- 一个表最多一个主键，一个表最多一个聚集索引
- 一个表中可以有多个唯一索引，但是只能有一个主键
- 主键列不允许空值，而唯一索引列允许空值。
mysql主要用到B+树和hash两种索引。
memory用hash索引，innodb和mysam是b+树索引。
二叉树->AVL树->红黑树->B-树->B+树
-
二叉树会越查越高。尾部插入会退化为线性。
-
AVL树：带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡。和红黑树相比，它是严格的平衡二叉树。
不适合做数据库索引。因为：
(1) 当数据量大的时候，树的高度会比较高，数据量大的时候，查询会比较慢；
(2) 每个节点只存储一个记录，可能导致一次查询有很多次磁盘IO
(3) 旋转操作效率太低 -
红黑树（弱平衡二叉平衡树）：一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是red或black。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍。它是一种弱平衡二叉树
红黑树问题：数据量越大，树高度越高，性能越低（查找效率低）。
O次数多 -
B树：m叉搜索。叶子节点和非叶子节点都存储数据；中序遍历可以获取所有节点。
①叶节点具有相同的深度，叶节点指针为空；②所有索引元素不重复；③节点中数据索引从左到右递增缺点：
（1）节点要存储数据和索引，一个内存页可存储数据还是少
（2）范围查找需要多次IO
-
B+树（多路平衡查找树）：①非叶子节点不存储data，只存储索引（冗余），可以存放更多索引；②叶子节点包含所有索引字段；③叶子节点用指针连接，提高区间访问性能；
优点：
(1). 只有叶子节点保存数据，可以存放更多索引，
(2). 底层双向链表，方便范围查找。
mysql对叶子节点的冗余索引是加载到内存中的（数据还是在磁盘中），最终做一次IO磁盘查找，效率很高。
b+树一般1-3层就可以实现千万级别的数据查找
哈希桶里面的链表里，也放索引文件对应的磁盘文件地址。
算法时间复杂度是O(1)，hash算法查找效率很高。但是只能查找一条。因为有 hash不支持范围查找——只好全表扫描（如>'Tom’文件的所有文件，无法过滤）、hash冲突为题。
select * from t where name=”shenjian”;
如果只有报表的等值查找，用hash效率可能比较高。但其实现实用的很少。因为实际是要范围查找，有很多有序需求。
不用hash
- 内存上：索引需要把存储在磁盘上的数据都加载进内存，采用Hash索引遇到大数据量的数据时无法一次性加载进内存；B+树的高度低，非叶子节点不存储数据，允许数据分批加载
- 业务上：B+树的叶子节点是有序的，可以在叶子节点上进行范围查找。
mysql现在基本用innoDB
myISAM索引文件和数据文件是分离的（非聚集索引——稀疏索引）
索引元素和数据元素分开存储
frm存储框架，MYI索引，MYD数据
mysam的叶子节点的data放的是索引所在行的磁盘文件地址，然后去查myd文件去定位改行数据的所有数据值（回表）。
InnoDB索引实现（索引）
frm框架，ibd索引和数据都在这个文件里。
如果有主键就使用主键，没有就使用唯一键，没有唯一键就使用6字节的rowid。
和数据放在一起的是聚集索引，而为了避免数据冗余存储，其他的索引的叶子节点中存储的都是聚集索引的key值。因此：innodb中既有聚集索引也有非聚集索引。而myisam中只有非聚集索引。
数据和索引放在一个文件里。表数据文件本身按B+树组织的索引结构文件，来组织数据。
叶子节点除了索引，还放索引所在行的其他所有数据。（聚集索引——聚簇索引）
索引元素和数据元素一起存储
二级索引
innodb的普通索引（二级索引），根据索引b+树来定位到元素拿到主键，然后到主键索引树里定位具体记录所有元素（这也是回表查询），效率比主键查找效率。非聚集索引叶子节点存储的是主键值。
回表查询
3.2 QA先通过普通索引的值定位聚簇索引值，再通过聚簇索引的值定位行记录数据，需要扫描两次索引B+树，它的性能较扫一遍索引树更低。
问题1：一定要建主键，建会比不建好很多。
B+树的元素可以从主键索引里来，没有建主键的话怎么维护数据？mysql会在表里找出一列可以做唯一索引的，用这列数据来组织所有数据，维护到B+树上来。
找不到唯一索引，就后台维护一个隐藏链（自增、唯一的），然后用这个隐藏链来维护b+树。
自家建一个主键，可以提高mysql的性能，减少mysql做维护工作。
问题2：整型？b+树会做大量的查找比对（折半查找、查找等），整型比大小快，字符串比大小慢。存储空间占的小。
问题3：自增？（见下）：B+树适合范围查找，叶子节点尾部双向链表，是相邻节点的磁盘文件地址。而且从左到右依次递增。 双向指针提高区间访问性能。
如果先插8再插7（会做平衡）：维护的不是自增。如果是自增的，永远在后面加元素。很少会导致插入元素后节点分裂（16KB放满），下层层元素还要往上提，上面节点顺序重新排列。效率会掉很多
树结构会分裂、旋转、平衡，效率不会高。
问题4：B+和B树本质区别：B树叶子节点没有双向指针；B树非叶子节点保存data。为什么用B+不用B？
B+树非叶子节点不存储data，只存储索引（冗余），可以放更多的索引。B+树空间利用率更高。
B+树的叶子节点包含所有索引字段。
B+树支持范围查找（多了双向指针），存储索引，B树会更高。在进行范围查找时，B树需要从根节点向下遍历，造成大量随机I/O。而B+树通过双向链表，查找更加便利并且只会产生固定I/O。
高度为3，B+树就可以放2000W个索引。B树的高度会比3大。决定树高度的本质是非叶子节点。非叶子节点可以分叉更多的叶子节点的话，可以存储更多树。
B+树可以达到千万级别的数量的查找，一个块可以存16KB，字数就是a=16*16，总共可以千万级别的数据量。
4 联合索引与覆盖索引 4.1 联合索引索引在id上建的比较多。
代码：
CREATE INDEX 索引名 ON 表名(列名X, 列名Y, 列名Z);
其实这相当于建立了三个索引，分别是：
- 单列索引（列X）
- 复合索引（列X, 列Y）
- 复合索引（列X，列Y，列Z）
联合索引：指的是对表中的多个列进行索引，联合索引也是一棵B+树，不同的是键值数量大于等于1。
select * from table where a=XX and b=XX （联合索引 （a,b））4.2 覆盖索引
覆盖索引：一种特殊的联合索引，即你查询的字段所有数据都在索引上，不需要再进行一次回表查询，这样的索引即为覆盖索引。
当sql语句的所求查询字段（select列）和查询条件字段（where子句）全都包含在一个索引中（联合索引），可以直接使用索引查询而不需要回表。这就是覆盖索引。
1 A: select id from user_table where name= '张三' 2 B: select password from user_table where name= '张三'
A：因为 name索引树 的叶子结点上保存有 name和id的值 ，所以通过 name索引树 查找到id后，因此可以直接提供查询结果，不需要回表，也就是说，在这个查询里面，索引name 已经 “覆盖了” 我们的查询需求，我们称为 覆盖索引。
B： name索引树 上 找到 name=‘张三’ 对应的主键id, 通过回表在主键索引树上找到满足条件的数据
如果查询条件使用的是普通索引（或是联合索引的最左原则字段），查询结果是联合索引的字段或是主键，不用回表操作，直接返回结果，减少IO磁盘读写读取正行数据
select id,age from user where age = 10;
解说：https://www.cnblogs.com/s42-/p/13596212.html
4.3 mysql最左前缀优化原则实际会推荐：联合索引，不要建太多单值索引。
当遇到范围查询(>、<、between、like)就会停止匹配。
主键联合索引：第一个字段相等，则按第二个字段排序。
这里只有第一个走了联合索引，其他因为没符合左前缀原则，因此没走联合索引。
左前缀原则底层原理：age, position不是第一个，在所有叶子节点里没有排好序。跳过了第一个索引，后面的索引中没有排好序，还是要全表扫描。第一个元素找到后，只要在这一个小块里定位查找，后面的不用再找了！
猴哥：只查一次能查出来的叫覆盖索引。
a=1,b>5,c=2
4.4 QA范围查找不可以走索引，只可以命中a的索引。b因为是范围，a>=2也不能走索引。
-
sql为：SELECt * FROM table WHERe a = 1 and b = 2 and c = 3; 如何创建索引？
答案：(a,b,c)或者(c,b,a)或者(b,a,c)都可以，重点要的是将区分度高的字段放在前面，区分度低的字段放后面。 -
sql为：SELECt * FROM table WHERe a > 1 and b = 2; 如何创建索引？
答：对(b,a)建立索引。 最左匹配原则遇到范围查询就停止匹配。 -
sql为：SELECt * FROMtableWHERe a > 1 and b = 2 and c > 3;
答：(b,a)或者(b,c)都可以，要结合具体情况具体分析。 -
SELECt * FROMtableWHERe a = 1 ORDER BY b;
答：一看就是对(a,b)建索引，当a = 1的时候，b相对有序，可以避免再次排序！
SELECt * FROMtableWHERe a > 1 ORDER BY b;
答：对(a)建立索引，因为a的值是一个范围，这个范围内b值是无序的，没有必要对(a,b)建立索引。
- SELECt * FROMtableWHERe a IN (1,2,3) and b > 1;
答：还是对(a，b)建立索引，因为IN在这里可以视为等值引用，不会中止索引匹配，所以还是(a,b)!
阿里规约
表记录很多，又没有很好地索引，表关联的时候可能会做上百万次的数据表扫描和运算。
