究极无敌细节版 Mysql索引( 二 ) _生活百科

文章插图
但是二叉搜索树在插入，删除节点的时候可能出现树极度不平衡的情况，出现树退化成链表。

文章插图
这个时候就需要维持树的平衡——AVL:在满足二叉搜索树的条件下，要求任何节点的两个子树高度差不超过1 。平衡二叉树的查找是趋近于O(log(N))，但是需要维护一颗树为AVL需要进行左旋，右旋的操作，更新的时间复杂度也是 O(log(N)) 。
为什么不使用AVL做索引：节点存储的数据内容太少。因为操作系统和磁盘之间一次数据交换是以页为单位的，一页 = 4K，即每次IO操作系统会将4K数据加载进内存。但是，在二叉树每个节点的结构只保存一个关键字，一个数据区，两个子节点的引用，并不能够填满4K的内容。幸幸苦苦做了一次的IO操作，却只加载了一个关键字，在树的高度很高，恰好又搜索的关键字位于叶子节点或者支节点的时候，取一个关键字要做很多次的IO 。
5.B-树， B+树B-树就是B树，英文是B-Tree，所以国内有许多人称之为B-树。B树和B+树是多路平衡查找树，之所以多路，是为了契合磁盘的io操作——操作系统和磁盘之间一次数据交换是以页为单位的，多路能让读取一页能获取更多的数据，让树的高度更低。

文章插图

文章插图
【究极无敌细节版 Mysql索引】上面两图，我们可以看出B树和B+树的区别

B+树叶子节点使用双向指针串联起来，这让B+树相比于B树更加适合范围查找
B+树非叶子节点并不存数据，所以每次查找数据都必须遍历到叶子节点，时间复杂度稳定为O(logN) ， B-树在运气好的时候可以在根节点直接拿到数据。但是正是因为非叶子节点不存储数据，可以让一次磁盘读取一页中包含的索引数据更多，每个节点能索引的范围更大更精确，让我们可以更改定位到期望的数据。由于B+树的叶子节点的数据都是使用链表连接起来的，而且他们在磁盘里是顺序存储的，所以当读到某个值的时候，磁盘预读原理就会提前把这些数据都读进内存，使得范围查询和排序都很快

B+树在更改数据的时候，为了保证树的平衡可能存在节点的分裂和合并，所以我们一般建议使用自增主键，在插入的时候，不会频繁的发生节点的分裂。
三丶InnoDB索引方案1.InnoDB行结构InnoDB存储引擎存储一行数据使用的数据结构称为行结构。