Mysql的索引采用B+tree的结构，因为索引需要自持范围查寻、等值查询，支持快速的添加、删除，且时间复杂度不能太高，同时占用的空间不能太大。
b+tree做索引的实现原理
查询
- 保存在文件中，采用时间换空间的思路，支持大的索引;
- 由于节点在磁盘中，每次访问节点都需要一次磁盘的IO，所以b+tree是多叉树，有效降低了树的高度，极大减小了磁盘IO的次数提高了性能;
- b+tree每个节点的大小都对应一个内存的PAGE_SIZE,保证每次加载只有一次磁盘IO
b+tree只保存索引所以，叶子节点由链表串联起来，所以支持范围查找，并且修改值不用改动索引，且索引很小。
添加:添加如果节点超过了Page容纳的范围，就将原有节点分裂成俩个不同的节点，逐层向父级分裂知道满足需求
删除：设置一个阈值，如果b+tree节点数量小于阈值就进行合并，如果合并后节点数超过PAGE_SIZE在和添加一样进行分裂
b+tree和b-tree的区别
- b+tree的节点保存索引，btree保存值。
- b+tree的叶子节点由链表串联起来。
索引的选型
索引是所有的数据存储系统的关键，直接关乎查询的效率，常用的适合做索引的数据结构有：
- 散列表：查询修改复杂度都是O(1),适合nosql的存储，如redis，memcached等，大部分索引都在内存中
- 红黑树：适合做文件系统的索引，插入、修改、查询的事件复杂度都是O(LogN)，也适合构建内存索引
- B+tree：适合构建磁盘索引，如mysql等
- 还有布隆过滤器、位图等：虽然有误判，但是我们可以选择他做二级索引，因为索引很小，且效率很高，判断下数据是否存在，如果返回存在在调用其他索引查找。