MySQL理解Btree的索引机制
一、索引
1、索引的定义
1.1 索引是为了加速对表中数据行的检索而创建的一种分散存储的数据结构，硬盘级存储方式
1.2 正确的创建合适的索引 是提升数据库查询性能的基础
2、索引如何实现的
索引是由插拔式的存储引擎来实现的，存储引擎可以定义在表结构中，一个库可以定义多个存储引擎。
如图：索引能够记录磁盘位置，根据对应关系，每个id有一个磁盘位置
3、为什么要用索引
3.1 索引能极大的减少存储引擎需要扫描的数据量
3.2 索引可以把随机IO变成顺序IO 索引
3.3 可以帮助我们在进行分组、排序等操作时，避免使用临时表
4、为什么选择 B+tree 数据结构作为索引机制
在讲B + Tree之前先来看下其它几种二叉树运行机制
4.1 二叉查找树 Binary Search Tree
如图： 二叉树先进行根节点比较，再进行子节点比较。假如这是一幅id为索引的二叉树索引结构，比如我现在要查找id为7的位置，先从根节点10出发，发现7比10小，再比较左边的子节点5，发现7比5大，再比较5的右边子节点，此时刚好命中7，就定位到了要查找的数据位置。
注：父子节点的位置看插入的顺序和数值大小，比如第一个插入的就是根节点，小于上一个节点数值放在左边节点位置，大于等于上一个节点数值放在右边节点位置
问题：假设数据表主键id为唯一索引并且自增，那么此时二叉树根据ID的查找效率和全表扫描没有任何区别，会有很多IO的访问，如图
总结：采用二叉树作为数据结构检索效率必须强依赖数据的分布，如果数据分布呈现一种线性链表的结构，那么效果就看不出来了，所以二叉树不适合作为mysql索引的索引机制。
4.2 平衡二叉查找树 Balanced Binary Search Tree
平衡二叉树 两种定义 有 相对平衡二叉树（平衡二叉树 某一个节点的高度差不会超过1） 和完全平衡二叉树AVL（整棵树的高度差不超过一个节点）
- AVL 完全平衡二叉树，依次插入8个数字呈现效果如图，为了保证数据的平衡，会变动数据的位置
- 相对平衡二叉树
一个节点就是一个磁盘块，一个磁盘块保存的数据是关键字和数据区，通过数据区加载数据，先比较根节点，加载到内存中，一般数据区放的是磁盘位置也可能放的是直接数据，p1和p2是指向子节点引用的指针地址，
总结：平衡二叉树虽然解决了出现线性链表的问题，但是树太高了，数据处的（高）深度决定着他的IO操作次数，IO操作耗时大，假设数据量较大此时的IO操作次数也会很多。每一个磁盘块（节点/页）保存的数据量太小了 没有很好的利用操作磁盘IO的数据交换特性， 也没有利用好磁盘IO的预读能力（空间局部性原理），从而带来频繁的IO操作，保存到数据量小同时也导致着空间的浪费。
4.3 多路平衡查找树 B-Tree
B-Tree 是一个绝对平衡树(即所有的子节点都在同一个高度)
多路表示的是不再和二叉树每个节点只有两条路，每个磁盘块存储这关键字和子节点引用指针，如下图的根节点，关键字为17、35，子节点引用指针为p1、p2、p3，关键字和路数的关系是： M条路数 M-1 个关键字
检索过程：B-Tree为了保证绝对平衡关系，如果插入或者删除的数据不满足平衡关系，整个索引的数据结构会发生节点的左旋和右旋来维持整棵树的平衡，所以索引不能随意建立。
路数的确定：假设一个磁盘块大小为4k，该索引是一个int的主键索引，4byte的数据区加上 假定的子节点引用指针等所占用的大小4byte，那么此时的路数为：4k1024/8 = 512路，所以在建数据表的时候尽可能的减少列的数据长度，这样能够增加路数，减少IO操作，提高检索效率。(这里的磁盘大小不全是存储关键字和数据区，也会存储子节点的引用指针和部分冗余，考虑会考虑到磁盘IO操作局部性原理和磁盘预读。另外每个磁盘块的大小可以通过参数指定，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页，在许多操作系统中，页得大小通常为4k)
4.4 加强版多路平衡二叉树B+Tree
- B+节点关键字搜索采用闭合区间
- B+非叶节点不保存数据相关信息，只保存关键字和子节点的引用
- B+关键字对应的数据保存在叶子节点中
- B+叶子节点是顺序排列的，并且相邻节点具有顺序引用的关系
- B+树是B-树的变种（PLUS版）多路绝对平衡查找树、拥有B-树的优势
- B+树扫库、表能力更强
- B+树的磁盘读写能力更强 B+树的排序能力更强
- B+树的查询效率更加稳定（仁者见仁、智者见智）
二、Mysql 中B+Tree索引体现形式
1、Mysql中B+Tree索引体现形式-MyISAM
数据和索引分别存储，表定义文件 .frm，数据保存在MYD文件中，索引保存在MYI文件中，在MyISAM中索引数据结构B+Tree的叶子节点数据区存储的是MYD文件的磁盘位置的指针引用
2、Mysql中B+Tree索引体现形式-InnoDB
除了表信息frm文件，只有ibd文件，索引结构文件和数据文件保存在一起。nnodb使用了聚集索引（clustered index）存储数据，如果一个主键被定义了，那么这个主键就是作为聚集索引，如果没有主键被定义，那么该表的第一个唯一非空索引被作为聚集索引，如果没有主键也没有合适的唯一索引，那么innodb内部会生成一个隐藏的主键作为聚集索引，这个隐藏的主键是一个6个字节的列，改列的值会随着数据的插入自增。
数据会保存在主键索引的叶子节点上， 其它的索引的都是辅助索引，然后再关联到主键索引
聚集索引： 数据库表行中数据的物理顺序与键值的逻辑（索引） 顺序相同（因为索引和数据是保存在一起的），一个表只能有一个聚集索引，因为一个表的物理顺序只有一种情况，所以，对应的聚集索引只能有一个。
两种引擎的展现形式
三、索引机制的一些原则
1、列的离散型：count(distinct col) : count (col)
越大离散型越好 结论： 离散性越高 选择性就越好，第一列name列离散型最好
选择性最好（离散性最好）原则
2、最左匹配原则
根据排序规则进行比较，比如ASCall码，从左往右一次比较，且不可跳过
