mysql索引机制B+树浅析
索引是什么
索引是为了加速对表中数据行的检索而创建的一种分散存储的 数据结构
为什么要用索引
1.索引能极大的减少存储引擎需要扫描的数据量
2.索引可以把随机IO变成顺序IO
3.索引可以帮助我们在进行分组,排序等操作时,避免使用临时表
索引为什么是B+树
二叉查找树,Binary Search Tree
(第一个插入的数据则为根节点)
二叉树的结构缺点:因为二叉树并不会维护节点的平衡性,而且每个节点存储的有效数据很少.
AVL树
使用AVL树当索引的查询步骤:
缺点:
它太深了
数据处的（高）深度决定着他的IO操作次数，IO操作耗时大
它太小了
每一个磁盘块（节点/页）保存的数据量太小了 没有很好的利用操作磁盘IO的数据交换特性，也没有利用好磁盘IO的预读能力（空间局部性原理），从而带来频繁的IO操作.
磁盘IO的数据交换特性:一次IO操作交换的数据为4K.磁盘IO的预读能力:在去读取操作系统中的数据的时候,如果将磁盘中的头部信息读取完毕之后,操作系统会将相邻的数据会读取到系统中.
多路平衡查找树:B-Tree
多路平衡查找树:所谓的多路相当于有多少条子节点分支.关键字个数为M路-1个.如上图,则为2-3数(2:关键字个数,3(Degree):路数).寻址过程:查找ID=15,则对比小于根节点的17,则寻找P1对应的子节点,对比15大于子节点的12,则寻找P3对应的子节点.之后返回数据.磁盘块内容粗略定义:将磁盘块定义为16K,则该磁盘快能存储的数据为:16*1024byte,ID的数据类型为int 4byte在加上冗余内存4byte,则磁盘块可以保存,16*1024/8,从此看出,定义索引的时候,我们要尽可能的使用精简字段.注意:当我们建立好索引之后,在继续有新的数据入库之后,为了维护B-Tree的平衡性,则会进行大量的分裂聚合操作,则会影响插入效率,因此也可以得出:索引不宜过多的理论.
mysql的B+Tree
寻址过程:获取ID=1的数据,将根节点加载到内存,由于和1相等,则的到P1对应的子节点,之后拿到子节点P1对应的叶子节点,之后拿到ID=1的数据.寻址结束.综上所述,mysql的B+树对应的数据全部保存在叶子节点中.B+TREE和B-TREE的区别:
1，B+节点关键字搜索采用闭合区间(保证查询落到叶子节点.)
2，B+非叶节点不保存数据相关信息，只保存关键字和子节点的引用
3，B+关键字对应的数据保存在叶子节点中
4，B+叶子节点是顺序排列的，并且相邻节点具有顺序引用的关系为什么选用B+tree:
1.B+树是B-树的变种（PLUS版）多路绝对平衡查找树，他拥有B-树的优势
2.B+树扫库、表能力更强(B-tree的每个节点都有数据区,而B+tree只有叶子节点有.)
3.B+树的磁盘读写能力更强
4.B+树的排序能力更强(叶子节点天然存在排序性)
5.B+树的查询效率更加稳定（仁者见仁、智者见智）(B+最终肯定会落到叶子节点.)
Mysql中B+tree索引体现形式
Myisam
Innodb
如果innodb中没有主键索引,则会建立隐式主键索引.