MySQL索引以及InnoDB

二叉树

当数据是自增的时候，二叉树会跟链表没有区别

平衡二叉树

它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。、

红黑数

红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。

优点：不会出现二叉树的极端情况，当两边深度差距太大会选择，维持相对平衡

缺点：当数据量太大的时候，索引的层级会非常深，假设需要查找的数据在叶子节点，进行的I/O会过多，非常影响性能

B-Tree（平衡多路查找树）

B-Tree是为磁盘等外存储设备设计的一种平衡查找树，非叶子节点也会存储数据

系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么。

InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位。InnoDB存储引擎中默认每个页的大小为16KB，可通过参数innodb_page_size将页的大小设置为4K、8K、16K，在MySQL中可通过如下命令查看页的大小：

mysql> show variables like 'innodb_page_size';

而系统一个磁盘块的存储空间往往没有这么大，因此InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB。InnoDB在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘I/O次数，提高查询效率。

B+Tree

是B-Tree的变种，非叶子节点不存储数据，数据存储在叶子节点，同时叶子节点存储全部数据，且叶子节点相互储存左右叶子节点的地址（便于范围查找）