mysql索引概述
什么是索引
索引是一种高效获取数据的数据结构,提高数据查询效率
索引分类
从存储结构上来划分：B-Tree，B+Tree，Hash索引
从应用层次来分：普通索引，唯一索引，复合索引
从数据的物理顺序与键值的逻辑（索引）顺序关系：聚集索引，非聚集索引
Mysql 索引底层数据结构选型
Hash索引介绍
hash索引基于哈希表实现，存储引擎会对索引列使用哈希算法，计算一个哈希码（hash code），并且将所有的哈希码存储在索引中，同时在索引表中保存指向每个数据行的指针
哈希算法也叫散列算法，就是把任意值(key)通过哈希函数变换为固定长度的 key 地址（十六进制表示），通过这个地址进行具体数据的数据结构,哈希表是一种内存地址映射关系
哈希表查找过程:
表中一共有 7 个数据，我们需要检索 id=7 的数据，SQL 语法是：
select * from user where id=7; 哈希算法首先计算存储 id=7 的数据的物理地址 addr=hash(7)=4231，而 4231 映射的物理地址是 0x77，0x77 就是 id=7 存储的数据的物理地址，通过该独立地址可以找到对应 user_name='g'这个数据。这就是哈希算法快速检索数据的计算过程。在查找 id=7 的数据，哈希索引只需要计算一次就可以获取到对应的数据，检索速度非常快。但是 Mysql 并没有采取哈希作为其底层算法，因为考虑到数据检索有一个常用手段就是范围查找，比如以下这个 SQL 语句：select * from user where id >3;
在范围查找过程中,简单的实现思路就是一次把所有数据找出来加载到内存，然后再在内存里筛选筛选目标范围内的数据。这种查找效率低,不能对数据高效范围查找，因此哈希索引是不适合作为 Mysql 的底层索引的数据结构。
- 哈希不支持 范围查询 ,不能做排序
- mysql默认的存储引擎是Inodb,对于频繁访问的表，innodb会建立自适应hash索引，即在B树索引基础上建立hash索引，可以显著提高查找效率，对于客户端，不可控制的，隐式的。
- 哈希存储时会降低磁盘利用率
二叉树
演示： https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
二叉树的特点：
- 一个节点只能有两个子节点，也就是一个节点度不能超过2
- 左子节点 小于 本节点，右子节点大于等于 本节点
在二叉树结构，计算比较 3 次就可以检索到 id=7 的数据，相对于直接遍历查询省了一半的时间，从检索效率上能做到高速检索的。此外二叉树的结构还能提供的范围查找功能，上图二叉树的叶子节点都是按序排列的，从左到右依次升序排列，如果我们需要找 id>5 的数据，那我们取出节点为 6 的节点以及其右子树就可以了，范围查找也是比较容易实现。
缺点:
主键自增情况下会退化为线性链表，二分查找也会退化为遍历查找（全盘扫描），检索性能急剧下降。id主键索引自增情况下二叉树已演化为线性链表，检索速度降低。此时检索 id=7 的数据的所需要计算的次数已经变为 7 了,因此 不能直接用于实现 Mysql 底层索引
二叉查找树存在不平衡问题，让二叉树始终保持基本平衡的状态，就能保持二叉查找树的最佳查找性能了。基于这种思路的自调整平衡状态的二叉树有 AVL 树和红黑树。
红黑树
上图所示，左图在插入数值为3时，红黑树的算法发现有偏向，就会重新调整树结构；调整到右边保持平衡，如持续递增，之前的数据1～7持续递增的树，会变成如下图所示
递增插入过程红黑树会自动左旋右旋节点以及节点变色，调整树的形态，使其保持基本的平衡状态，也就保证了查找效率不会明显减低。如上图所示。红黑树下查找 id=7 的所要比较的节点数为 4，依然保持二叉树不错的查找效率。
红黑树很好的解决线性链表问题，但红黑树问题也比较大。
每次插入都要检查规则，再把树进行重新平衡，这个是非常消耗时间,数据量大的话，红黑树的深度会比较深，并且产生“右倾”,树一旦深就代表着我们读取磁盘次数就会增加，因此 不能直接用于实现 Mysql 底层索引
红黑树的特点会自动平衡树，但是没有做到绝对的平衡，会产生右倾
平衡二叉树(AVL)
AVL 树的特点：
- 平衡二叉树又称AVL树，在满足二叉查找树特性的基础上，要求每个节点的左右子树的高度差不能超过1。
- 很好的查找性能，不存在极端的低效查找的情况。
- 可以实现范围查找、数据排序。
顶端的节点我们称为根节点，没有子节点的节点我们称之为叶节点。
平衡二叉树和非平衡二叉树的对比：
平衡二叉树查找过程:
AVL 树顺序插入 1~16 个节点，查找 id=16 需要比较的节点数为 4。从查找效率而言，AVL 树查找的速度要高于红黑树的查找效率（AVL 树是 4 次比较，红黑树是 6 次比较）。从树的形态看来，AVL 树不存在红黑树的“右倾”问题。大量的顺序插入不会导致查询性能的降低，这从根本上解决了红黑树的问题。
mysql 如果使用的是 AVL 树，我们每一个树节点只存储了一个数据，一次磁盘 IO 只能取出来一个节点上的数据加载到内存里，如查询 id=7 这个数据我们就要进行磁盘 IO 三次，这很消耗时间。所以我们设计数据库索引时需要首先考虑怎么尽可能减少磁盘 IO 的次数。因此 不能直接用于实现 Mysql 底层索引.。
B-Tree 索引原理
磁盘 IO 特点：从磁盘读取1B 数据和 1KB 数据所消耗的时间是基本一样的(空间局部性与时间局部性决定)，根据这个思路，可以在一个树节点上尽可能多地存储数据，一次磁盘 IO 就尽可能多的加载数据到内存，影响数据查询时间的是树的高度，高度越高，比较的次数越多，尽量把树的高度降低。这就是 B 树的的设计原理了
B-Tree特点:
- 叶节点具有相同的深度。
- 节点中的元素从左向右递增排序
- 所有的元素不重复
B-Tree演化过程：
下图所示B-Tree树，每个节点限制最多存储两个 key，一个节点如果超过两个 key 就会自动分裂。比如下面这个存储了 7 个数据 B 树，只需要查询两个节点就可以知道 id=7 这数据的具体位置，也就是两次磁盘 IO 就可以查询到指定数据，优于 AVL 树。
磁盘有预读机制，每次读的时候都是加载一个磁盘页到内存里面，就是一次磁盘I/o读取只能读一个磁盘页大小（4kb）的数据到内存中，也就是8kb的数据，要磁盘i/o的2次操作。就是因为磁盘预读机制，树的节点不能随便我们设置，树节点的数据量正好是一个磁盘页的大小，这样效率最高，一次IO读取一个树节点。这个直接反映到树的结构就是，每个节点能存储的 key 可以适当增加。当我们把单个节点限制的 key 个数设置为 6 之后，一个存储了 7 个数据的 B 树，查询 id=7 这个数据所要进行的磁盘 IO 为 2 次。如下图所示：
MySQL页的大小为16kb，操作系统文件管理系统一次IO读取的数据大小同样为1页（4kb）相当于8个扇区（512bytes ）
一个存储了 16 个数据的 B 树，查询 id=7 这个数据所要进行的磁盘 IO 为 2 次。相对于 AVL 树而言磁盘 IO 次数降低为一半,如下图所示:
索引叶节点数据之间的存储关系，如下图所示:
假如我们要查找id=28的用户信息，那么我们在上图B树中查找的流程如下：
- 先找到根节点也就是页1，判断28在键值17和35之间，我们那么我们根据页1中的指针p2找到页3。
- 将28和页3中的键值相比较，28在26和30之间，我们根据页3中的指针p2找到页8。
- 将28和页8中的键值相比较，发现有匹配的键值28，键值28对应的用户信息为(28,bv)
总结来说，B 树用作数据库索引有以下优点：
- 优秀检索速度
- 尽可能少的磁盘 IO，加快了检索速度；
- 可以支持范围查找。
B+Treee
有了B树知识铺垫，一个树节点我们应该尽可能的包含更多的子节点，但又不能超过一个磁盘页（16kb）的大小。发现B树的节点中还包含了一些关键字信息data，这个data也占据着一定的数据量，r如果把data去掉，这样就又能多加几个子节点了。这也就是B+树的核心思想。
查看页节点大小
注： show GLOBAL STATUS like 'Innodb_page_size';
mysql 一般将根节点 限制的大小是 16kb，根节点的大小存储大约 1000多个，底部含有data的为叶子节点，叶子节点全部放满 大约为2000万个左右。16*1024/(8+6)=1170 主键存储 bigint 为8字节空白部分为索引位置6字节 16kb为总的根节点大小
B+Tree特点：
- 非叶子节点不存储data,只存储索引(冗余),可以放更多的索引
- 叶子节点包含所有索引字段
- 叶子节点用双向指针相连，提高区间访问性
B+树是通过二叉树，平衡二叉树，B树和索引顺序访问演化而来,是对B树的进一步优化。
B+Tree结构图:
根据上图我们来看下B+树和B树有什么不同:
B+树非叶子节点不存储数据的，仅存储键值(索引地址)，而B树节点中不仅存储键值，也会存储数据。B+树之所以这么做是因为在数据库中页的大小是固定的，innodb中页的默认大小是16KB。如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的IO次数会再次减少，数据查询的效率也会更快 。
B+树索引的所有数据均存储在叶子节点，且数据是按照顺序排列的。B+树使得范围查找，排序查找，分组查找以及去重查找变得简单高效
B+树各个页之间是通过双向链表连接，叶子节点中的数据是通过单向链表连接的。我们通过双向链表和单向链表连接的方式可以找到表中所有的数据。
MySql中 B+Tree详解
在 mysql分别创建 以myisam 和 Innodb 作为存储引擎的数据表。
Innodb 创建表后生成的文件有：
- frm:创建表的语句
- idb:表里面的数据+索引文件
Myisam 创建表后生成的文件有：
- frm:创建表的语句
- MYD:表里面的数据文件（myisam data）
- MYI:表里面的索引文件（myisam index）
Myisam不支持事务原因索引与数据分开存储，两个文件无法做到一致性
- MyISAM 引擎的底层实现（非聚集索引方式）
MyISAM 是非聚集索引方式，即数据和索引落在不同的两个文件上。B+树索引的叶子节点并不存储数据，而是存储数据的文件地址，MyISAM 在建表时以主键作为 KEY 来建立主索引 B+树，树的叶子节点存的是对应数据的物理地址。拿到这个物理地址后，就可以到 MyISAM 数据文件中直接定位到具体的数据记录了。下图所示：
Myisam检索数据过程中有 "回表操作"
- Innodb 引擎的底层实现（聚集索引方式）
InnoDB 是聚集索引方式，因此数据和索引都存储在同一个文件里。首先 InnoDB 会根据主键 ID 作为 KEY 建立索引 B+树，如左下图所示，而 B+树的叶子节点存储的是主键 ID 对应的数据，比如在执行 select * from user_info where id=15 这个语句时，InnoDB 就会查询这颗主键 ID 索引 B+树，找到对应的 user_name='Bob'。
这是建表的时候 InnoDB 就会自动建立好主键 ID 索引树，这也是为什么 Mysql 在建表时要求必须指定主键的原因。当我们为表里某个字段加索引时 InnoDB 会怎么建立索引树呢？比如我们要给 user_name 这个字段加索引，那么 InnoDB 就会建立 user_name 索引 B+树，节点里存的是 user_name 这个 KEY，叶子节点存储的数据的是主键 KEY。注意，叶子存储的是主键 KEY！拿到主键 KEY 后，InnoDB 才会去主键索引树里根据刚在 user_name 索引树找到的主键 KEY 查找到对应的数据。
Inodb存储引擎特点:
- 表本身是按B+Tree组织的一个索引结构文件
- 叶子节点包含了完整的数据记录
- 非主键索引结构叶子节点存储的是主键的值，使其保持一致性和节省空间
Inodb查询等于的查询 引擎会自动使用哈希索引进行查询,存储引擎会监控对表上索引的查找，如果观察到建立哈希索引可以带来速度的提升，则建立哈希索引，所以称之为自适应哈希索引。自适应哈希索引通过缓冲池的B+树构造而来，因此建立的速度很快。而且不需要将整个表都建哈希索引，InnoDB存储引擎会自动根据访问的频率和模式来为某些页建立哈希索引。
- 为什么 InnoDB 只在主键索引树的叶子节点存储了具体数据 ?
为节省存储空间，一个表里可能有很多个索引，InnoDB 都会给每个加了索引的字段生成索引树，如果每个字段的索引树都存储了具体数据，那么这个表的索引数据文件就变得非常巨大（数据极度冗余了）。
- 为什么Inodb表必须有主键，且推荐使用整型自增主键?
Inodb 会自动选择不重复的列作为索引列，组织整张表的数据，如果找不到 就会建隐藏列，所以Inodb一般会建主键,整型的数据比较大小速度快，整型存储占用空间小，主键如果不自增，叶子节点 会频繁的发生分裂，或者平衡变化，会降低插入的效率，所以主键选择自增整型
数据表的字段加索引原则：
较频繁的作为查询条件的字段应该创建索引；
唯一性太差的字段不适合单独创建索引，即使该字段频繁作为查询条件；
更新非常频繁的字段不适合创建索引。
联合索引底层数据结构
联合索引的数据结构 也是字典排序法则，将第一个 第二个进行排序，B+之所以高效是借助 叶子节点从左到右的排序，如果跳过 第一个字段，则第二三字段 在叶子节点中的排序 不是按顺序排序，则整个数据不一定是顺序递增的结构，就是说联合索引使用时遵循"最左前缀原则"
非主键索引存储的是主键索引位置，会扫描两棵树 （主键索引, 非主键索引）
