Mysql索引
介绍：
索引是帮助mysql高效获取数据数据的排好序的数据结构。
我们从以下数据结构逐步探讨：
演示地址https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
- 二叉树
- 红黑树
- Hash表
- B-Tree
二叉树
特性：右边的子节点大于父元素，这样就会缺点。
如果说插入的子节点一直比父节点大的话，就会形成链表这样，这样在查询的时候就会一个一个查询，非常慢！
红黑树
红黑树就是平衡二叉树。
在插入元素时，平衡二叉树总会以一种平衡的形式展现出来。
缺点：如果是百万级的数据的话，以最坏的打算查询的次数就是这个树的深度，查询的次数就是n，2的n次方 = 100万。
以上的两种数据结构都是没有做到3-5次的查询就可以得到结果的，那么怎么解决呢？
查询次数相当于我们就要控制树的高度，我们就可以去控制数的纵向来控制树的高度。这里就可以用到了B树。
那么mysql真正底层就是用的这个数据类型，但是更加了优化了一凡，称为B+树。
在B+Tree的横向第一个结点中，不能放特别多的数据，因为需要加载到内存中，mysql默认控制的大小是16k。
可以对比b树和b+树的区别是在第一个节点中没有存放数据，这样的做法，就可以让非叶子节点存放更多的索引，所以说会带来冗余。
多插平衡树
一个bigInt大小是8Byte，15左边的那一个指针，就是红线画的那个，大小在6Byte左右。
那么就是说按照mysql的默认16kb，可以存放大概1170个。
data按mysql的存储引擎来说存储的东西的，有的是索引所在行的磁盘文件地址，有的是索引所在行的所有字段。
我们按一个节点1kb来进行计算，那么整个B+tree存放的数据量是：
1170X1170X16=2千一百多万。
这就得到了我们想要的东西！只进行3次深度的查询就可以得到我们想要的数据了！
下面我们再来说说两种存储引擎Myisam和innodb这两种。
其中Myisam不支持事务。innodb是支持事务的。
存储引擎
先来说一下innodb存储引擎。这个存储引擎是聚集引擎。我们来看一下mysql文件中的data文件。
我们可以看到这个test_innodb表由这两个文件组成的，一个是frm文件，主要就是存放表结构定义之类的，与表的存储引擎无关，就是说任何存储引擎的表都会含有这个文件。
然后就是这个ibd文件，在innodb的存储引擎中，我们上文所说的叶子结点的data存储的就是数据和索引，这两个是在一个文件中的，所以说叫聚集引擎。
然后是Myisam存储引擎。这个存储引擎是非聚集引擎。我们来看一下mysql文件中的data文件。
我们再来看一下Myisam的存储引擎，他除了frm文件外，还有两个文件，一个是myd是存放数据的，一个就是myi文件，是存储索引的，他的两个文件不像innodb一样是放一起的，所以说成为非聚集引擎。
叶子结点中的箭头
我们在innodb的那张图片中的第三点，可以看到推荐使用主键递增的。
那么为什么要主键递增呢？
这就是因为叶子结点中的箭头，如果我们是范围查询的话，我们知道主键递增的话，由于箭头的关联，在进行范围查询的时候，我们就可以直接利用这个箭头去进行特别快的查找。
两种索引方法
我们在创建索引的时候，可以看到索引方法不仅有b+tree，还有一个hash，哈希索引的原因就是利用hash值去进行查找的时候特别快，但是！他这种查询是利用哈希值去进行查的，当遇见范围查询的时候，就不行了！这就是为什么大多数数据库创建索引的时候使用B+tree的原因！
