索引本质
- 索引是帮助Mysql高效获取数据的排好序的数据结构
- 索引数据结构
- 二叉树
- 红黑树
- Hash表
- B-Tree（b树）
没有索引会发生什么
当我们查询数据的时候，如果没有索引的话，会一行一行的查询，这样的查询就会很慢
索引数据结构
二叉树
二叉树是树的特殊一种，具有如下特点：
1、每个结点最多有两颗子树，结点的度最大为2。
2、左子树和右子树是有顺序的，次序不能颠倒，左小右大。
3、即使某结点只有一个子树，也要区分左右子树。
如果我们使用二叉树作为索引的数据结构的话，一般会比没有索引查询要快，但是如果索引的自增的话怎么样
你看，这样索引的话和无索引并没有什么区别，还是会逐行寻找
红黑树
红黑树（Red Black Tree） 是一种自平衡二叉查找树，什么叫自平衡，我们来试一下
当我们增加节点的时候，红黑树会通过自旋来重新排序，这样确实比二叉树的查询效率要快很多，但是如果我的数据库有一百万的数据呢，树的高度n大概是多少，2^n=100万，n大概是20，如果我要查询的数据刚好在叶子节点（没有子树的节点）的话，也就是说要查询20次，磁盘就要做20次io，这样的话，效率也还是很慢
Hash表
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
Hash表会把索引进行hash运算，当我们要查询某条索引时，会先进行hash运算，然后通过hash碰撞来找到这个索引的位置，这样就只要进行一次磁盘io就能找到所需要的数据，听着是不是很快，但是，这种高效是有条件的，即只在“=”和“in”条件下高效，对于范围查询、排序及组合索引仍然效率不高。如果我们要进行范围查询呢，在项目中，范围查询是必不可少的，因为hash值是无序的，是不是也要经过多次的磁盘io
B Tree
我们先来看下这张图
navicat里面只提供了两种索引，我们项目中99%用的都是BTree
BTREE索引就是一种将索引值按一定的算法，存入一个树形的数据结构中（二叉树），每次查询都是从树的入口root开始，依次遍历node，获取leaf。这是MySQL里默认和最常用的索引类型。
- 叶子节点具有相同的深度
- 叶子节点的指针为空
- 节点中的数据索引为左到右递增排序
这是b树的一个简单结构，mysql会把上最简单的根节点放到内存中，这样的话就会很快，只需要经过一次磁盘io就会找到数据，有的人就会问，如果把所有索引都放到根节点会怎样，这样不就可以快速查询吗。
首先，再看这张图，索引和数据其实是一起的，如果把他们都放到内存中，是不是要非常大的内存，加内存的土豪当我没说啊。
其次mysql官方给根节点的大小设置的最大是16k
还有，范围查询的话，这样是不是也挺麻烦，因为叶子节点没有指针，是不是也要进行多次的磁盘io
B+Tree
B树的变种
- 非叶子节点不存储data，只存储索引，可以放更多的索引
- 叶子节点不存储指针
- 顺序访问指针，提高区间访问的性能
如果我们使用B+树的话，是不是三次就能找到数据，不，两次，首行根节点是存储在内存中，范围查询的效率是不是也很快，直接在叶子节点就能找到范围数据
问题
- 有人会问，如果我的索引是字符串类型怎么办，因为我们的数据库还有部分用的是UUID作为主键
- mysql官方推荐主键的是自增整型，如果用字符串的话会先转换为ASCII码
