1. 索引的概念：
索引是帮助Mysql高效获取数据的排好序的数据结构
2. 索引存储在文件里：
mysql主要有两种存储引擎： Myisam、Innodb两种
对于存储引擎为Myisam的数据表中，有三种文件格式，以.frm为后缀的表结构文件、以MYD为后缀的数据文件，以MYI为后缀的索引文件；
对于存储引擎为Innodb的数据表中，有两种文件格式，以.frm为后缀的表结构文件、以ibd为后缀的索引与数据合并的文件
myisam索引实现： 非聚集索引（索引文件和数据文件是分离的）
Innodb索引（聚集索引）
二、索引的各种存储结构及其优缺点
在开始讲这一小节之前，我们先来看一下在数据库没有加索引的情况下，SQL中的where字句是如何查找目标记录的。
我们先看下左边表格第二列Col2列的数据时如何查找的，如果我们希望查找where Col2 = 22的记录，我们在没加索引的情况下是按顺序从第一条记录查找，由此可知需要查找5次才能找到；
如果对Col2字段加上索引后，我们假设使用最简单的二叉树作为索引存储方式，再次查找where Col2 = 22的记录这次只需要查找2次就能找到目标记录，效率提高十分明显。
1. 二叉树
二叉树是一种比顺序结构更加高效的查找目标元素的结构，它可以从第一个父节点开始跟目标元素值比较，如果相等则返回当前节点，如果目标元素小于当前节点，则移动到左侧子节点进行比较，
大于的情况则移动到右侧子节点进行比较，反复进行操作最终移动到目标元素节点的位置
二叉树缺点：
在大部分情况下，我们设计索引时，都会在表中提供一个自增索引字段作为建立索引的列，这种情况下所有的只能增节点都会添加到上一节点的右侧，
这种情况下查询节点时跟没有添加索引的情况是一样的。
2. 红黑树
红黑树也叫平衡二叉树，它继承了平衡二叉树的优点，同时也解决了上面二叉树自增整形索引的问题，从下面的动态图可以看出红黑树会不断对树结构进行调整
红黑树的缺点：
在数据量大的时候，树的高度也很大，从图中可以看出每个节点只能有两个子节点，所以红黑树的高度会达到几十以上，增加了磁盘的I/O,降低了查找的效率。
3. HASH
对数据进行Hash散列运算，通过Hash算法计算hash值，再根据hash值从索引文件中获取文件在磁盘的位置并读取，快速定位目标记录，查询效率高。
缺点：
无法解决范围查询的场景、也不支持模糊查询。
4. B-Tree
既然红黑树存在缺点，那么我们可以在红黑树的基础之上构造一种新的存储结构，解决思路：因为树的高度太大，就只需要适当的增加每个树节点可以存储的数据个数即可，
但是数据个数也需要有一个阈值，否则会导致一个节点的数据过多导致其他的问题。
先来了解一下B-Tree的知识点
度（degree）-节点的数据存储个数，每个树节点中数据的个数大于15/16 * degree时会自动分裂，调整结构。
叶节点具有相同的深度
叶子节点的指针为空
节点中的数据key从左到右递增排列
1. 树节点结构：