索引为什么用B+树
-
二叉树会出现单点增长的情况，严重影响查询效率
- 红黑树 虽然有自动平衡的特点，但是随着数据量的增长，树的高度不可控，也会影响查询效率
- 用hash也可以但是hash不能查找排序 只是查找单个值的时候快
Btree树
Btree树每个节点可以存储多个数据，从而控制了树的高度，可以通过度来控制每个结点存储数据的个数
思考： 那么是不是设置度越大磁盘一次IO既可以加载越多的数据，其实不然，磁盘每次IO读取数据的大小是有限制的，索引度的大小跟CPU一次IO加载数据的大小有关，由于B-tree树中每个数据中存储着该行数据，所以当每行数据比较大的时候，每个节点也存储不了多少数据，没了解决这个问题引入B+树结构
B+树
如上图，是一颗b+树，浅蓝色的块我们称之为一个磁盘块，可以看到每个磁盘块包含几个数据项（深蓝色所示）和指针（黄色所示），如磁盘块1包含数据项17和35，包含指针P1、P2、P3，P1表示小于17的磁盘块，P2表示在17和35之间的磁盘块，P3表示大于35的磁盘块。真实的数据存在于叶子节点即3、5、9、10、13、15、28、29、36、60、75、79、90、99。非叶子节点只不存储真实的数据，只存储指引搜索方向的数据项，如17、35并不真实存在于数据表中。
b+树的查找过程
如图所示，如果要查找数据项29，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO，在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计，通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘块3的P2指针，通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询，总计三次IO。真实的情况是，3层的b+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高。
b+树性质
局部性原则，磁盘预读，一次IO中认为相邻的一些数据也会在近期被访问。
考虑到磁盘IO是非常高昂的操作，计算机操作系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关，一般为4k或8k，也就是我们读取一页内的数据时候，实际上才发生了一次IO，这个理论对于索引的数据结构设计非常有帮助。
注意：数据路引擎是表级别的
MyISAM引擎
MyIsam中索引文件和数据文件是分离的称作非聚集索引
.frm是存储的是表结构
.MYD MYISAM数据文件
.MYI MYISAM的索引文件
可以看出Myisam引擎索引存储的不是真是数据，而是数据的引用地址
InnoDB引擎
可以看出只有两个文件
InnoDB通过主键将整行数据关联(数据文件与索引文件是一体的)，称作聚集索引
所以InnoDB数据库表是必须要有主键的
- 为什么InnoDB推荐使用整型自增主键？
- 整型相比其他类型比较时速度更快
- 插入数据时直接放到节点数据的右侧，不会分裂，速度更快
- 如上图为什么InnoDB中非主键索引存储的是主键？
- 为了节省空间
- 避免插入数据时每个索引都要维护整行数据，造成数据不一致问题
InnoDB支持事务支持行锁
联合索引底层怎么存储的？
索引的最左原则（左前缀原则），如（c1,c2,c3,c4....cN）的联合索引，where 条件按照索引建立的字段顺序来使用（不代表and条件必须按照顺序来写），如果中间某列没有条件，或使用like会导致后面的列不能使用索引。
索引也能用于分组和排序，分组要先排序，在计算平均值等等。所以在分组和排序中，如果字段顺序可以按照索引的字段顺序，即可利用索引的有序特性。
- mysql联合索引的使用规则
https://blog.csdn.net/wdjxxl/article/details/79790421
MySQL索引学习
https://www.cnblogs.com/bypp/p/7755307.html
