为什么要使用索引
MySQL官方定义为：索引(Index)是帮助 MySQL 高效获取数据的数据结构，类似于书的目录结构一样。
如果向mysql发出一条sql语句请求，查询的字段没有创建索引的话，可能会导致全表扫描，这样的话查询效率非常低。
索引的存放位置
索引是存放在硬盘上的/var/lib/mysql目录下
MyISAM引擎的文件：
.frm 表结构
.myd 即 my data，表数据文件
.myi 即my index，索引文件
InnoDB引擎的文件：
.frm 表结构
.ibd文件：存放用户数据库表数据和索引。
索引文件为什么要放到硬盘上?
a、可以永久保存
b、如果文件很大，放到内存中容易导致内存溢出
索引的数据结构【数据结构模拟】
1.Hash算法【等值查询效率较高，但不能进行范围查找】
下标index=Hash(key)，内容存具体的值，这样的数组叫做散列表，也叫哈希表，映射的函数叫做散列函数。
优点：通过字段的值计算的hash值，定位数据非常快。
缺点：不能进行范围查找，因为散列表中的值是无序的，无法进行大小的比较。
2.二叉树
特性：分为左子树、右子树和根节点，左子树比根节点值要小，右子树比根节点值要大，正常查询时间复杂度log2n
缺点：有可能产生不平衡 类似于链表的结构 时间复杂度为o(n)
2.平衡二叉树(AVL树)【效率还可以，同时解决了hash算法不能范围查找的问题】
特点：
a、它的左子树和右子树都是平衡二叉树
b、左子树比中间小，右子树比中间值
c、左子树和右子树的深度之差的绝对值(平衡因子)不超过1。也就是说AVL树每个节点的平衡因子只可能是-1、0和1(左子树高度减去右子树高度)。
优点：平衡二叉树算法基本与二叉树查询相同，效率比较高
缺点：
a、插入操作需要旋转
b、支持范围查询，但回旋查询效率较低，比如要查找大于5的，会回旋到父节点6、8。
c、如果存放几百条数据的情况下，树高度越高，查询效率会越慢【核心原因是每个节点只存放一个数据】
查询原理【折半查找、二分查找】：
假设查询10 (需要经历4次IO操作)
1次 从硬盘中读取4 (内存)，判断下10>4，取右指针
2次 从硬盘中读取8 (内存)，判断下10>8，取右指针
3次 从硬盘中读取9 (内存)，判断下10>，取右指针
4次 从硬盘中读取10 (内存)，判断下10=10，定位到数据
规律：如果树的高度越高，那么查询IO次数会越多。
3.B树【节点增加元素，减少了树的高度，加快IO操作】
优点：B树的节点中可以有多个元素，从而减少树的高度，减少IO操作，从而提高查询效率
缺点：范围查询效率还是比较低。
4.B+树【解决范围查询问题、减少IO查询的操作】
和B树相比优点：
a、新增叶子节点与非叶子节点关系，叶子节点中包含了key和value，非叶子节点中只是包含了key，不包含value。
b、所有相邻的叶子节点包含非叶子节点，使用链表进行结合，有一定顺序排序，从而范围查询效率非常高。
缺点：有冗余节点数据，所以会比较占用硬盘大小。但取舍相比，这样效率还是高的。
为什么MySQL底层要使用B+树索引结构
B+树索引具有范围查找和前缀查找的能力，相当于二分查找。
而Hash索引只能支持等于查询，无法支持范围查询，B树的范围查找使用回旋效率较低。
1.支持范围查询
2.降低树的高度 减少磁盘io的次数
MyISAM和InnoDB对B+Tree索引不同的实现方式
Myisam的key存放的是数据库的key，value存放的是数据库记录的地址，在通过地址定位到数据。
InnoDB的key存放的是数据库的key，value存放的是数据库记录的内容，相比MyISAM效率要高一些，但是比较占硬盘内存大小。
MySQL常用索引类型
Hash索引和B+树索引
MySQL的B+树能够存放多少字节数据
操作系统对数据的操作都是按页读取的，大部分是一页4K，Mysql的InnoDB页大小默认为16K，当然也可以通过参数设置：show variables like 'innodb_page_size'; 16384/1024=16kb;
如果读取内容超过1页就会读取2页，小于1页会读取1页，所以B+树的每一个节点是页的倍数是最佳的。
非叶子节点存放索引和指针，索引值(bigint 8b)和指针(6b)，一页16*1024/(8+6)=1170指针。
假设一行为1kb，那么一页可以读取16行数据，一个叶子节点可以存放16条数据
B+树 高度为2 117016=18720条数据
B+树 高度为3 11701170*16=21902400条数据(2千万)
所以在InnoDB中B+树高度一般为1-3层，它就能满足千万级的数据存储。在查找数据时一次页的查找代表一次IO，所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。
为什么InnoDb引擎表必须有主键，并且推荐使用整型的自增方式？
A.不建议使用uuid使用数据库主键，不支持范围查询
B.B+树底层搜索的时候可能会发生值比较判断
非主键索引是如何造成二次查找的？
