什么是索引
索引是帮助MySQL高效获取数据的排好序的数据结构
索引数据结构（掌握）
前置知识：树的高度越低查询效率越高
二叉树：不能自平衡，极端情况出现倾斜，查询效率和链表类似
红黑树：数据量大不适合
Hash
B树：
- 叶节点具有相同的深度，叶节点的指针为空
- 所有索引元素不重复
- 节点中的数据索引从左到右递增排列
B+树：
- 非叶子节点不存储data，只存储索引（冗余存储），可以放更多的索引
- 叶子节点包含所有索引字段
- 叶子节点用指针连接，提高区间访问的性能
假如树的度是3，在一层添加第四个元素的时候，会将中间节点冗余作为父节点，叶子节点依然保存所有索引。
B+树又称多路/多叉平衡树，上图空白处是下一个字节点的地址，空白处是6byte，一个索引8byte(以bigint为例)。
所有叶子节点是从左到右递增
一颗B+树可以存多少数据
树的高度多少能存放1000万数据
一个节点大小16k，是磁盘存储块的大小，
16k/(6+8)=1170，每个节点放满16k，每个节点可以存储1170个索引。
一个叶子节点中的每个索引和数据大概1k，也就是一个叶子节点可以存放约16个索引和数据。
一个B+树总共可以存放的数据：1170x1170x16=2000万
根节点一般放内存。
第一层，一个节点可以放1170个索引
2000万数据，最多经过IO，可以查到数据。
MyISAM存储引擎索引的实现
MyISAM索引文件和数据文件是分离的(非聚集)
存储引擎是作用于表的
索引文件存放索引，数据文件存放数据，索引和数据不放在一起存
查询：先查询B+树上的索引，再用查询到的位置查询数据文件
Innodb存储引擎索引实现
.ibd 表和数据放一起
叶子节点存放索引的列数据
聚集索引：
- 表数据文件本身就是按B+树组织的一个索引结构文件
- 聚集索引-叶子节点包含了完整的数据记录
- 为什么非主键索引结构叶子节点存储的是主键值？（一致性和节省内存）
聚集索引的意思：叶子节点存放了索引和数据
又叫聚簇索引。非聚集索引又叫稀疏索引。
为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？
主键是InnoDB用来构建B+树的。
如果没有主键，会使用唯一的列作为索引，
如果还是没有，会建立隐藏列，作为索引列。
如果不用整型的自增主键，用UUID作为主键会怎么样？
-
UUID是字符串类型，查询操作会有比较操作，整型比较操作快
-
整型主键比UUID省空间
-
UUID不是自增的
HASH索引：值做hash运算，运算后的值和存储位置一一映射
为什么不用Hash？
Hash对范围查询支持不好。某一列数据是无序的，B+树在构建的时候可以让数据有序。
如何基于B+树精准建立高性能索引
B树
- 叶子节点具有相同的深度，叶子节点的指针为空
- 所有索引元素不重复
- 节点中的数据索引从左到右递增排列
B+树索引
- 非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
- 叶子节点包含所有索引字段
- 叶子节点用指针连接，提高区间访问的性能
为什么data节点挪到叶子节点，一个节点可以存储更多的索引
16^n=2000万，n就是树的高度，
存储同样的数据，B+树的高度远远小于B树