hash表：
特点：范围查询效率很低；因为hash之后的数没有顺序
完全平衡二叉树（AVL）：
AVL
特点：插入效率比较低，范围查找速度比较快（一个节点大于左边的子节点，小于右边的子节点）
B树：
B树（维度为3）
B+树：
B+树（维度为3）
特点：与B树相比，非叶子节点的数据会冗余到叶子节点，并且叶子节点会有指针指向下一个节点；而且B树本来就是有序的，所以叶子节点也是有序的。
查询效率对比（查询0006）：
完全平衡二叉树：4次磁盘IO
B/B+树：3次磁盘IO
范围查找效率：B+树 > B树 （因为B+树叶子节点的特性）
高度：完全平衡二叉树 > B+树 B树
1）查找一个数据，B/B+树产生的磁盘IO次数比完全平衡二叉树少，因为索引底层不会用到完全平衡二叉树；
2）范围查询中，B+树效率 > B树
小结：所以mysql索引采用B+树结构进行存储。
问题：一个B+树节点大小为多大合适？
操作系统读取硬盘数据，以“页”为单位（一般一页的大小为4kb），不管用户实际需要多少数据，操作系统都会以页的单位给你读取数据。因此mysql一个节点的大小是4kb的倍数，这样不会造成读取数据的浪费。
通过 SHOW GLOBAL STATUS like 'Innodb_page_size'可以查询到mysql一页的大小是16kb，而mysql默认的一个节点的大小为mysql定义的一页 = 16kb。
myisam与innodb的索引的区别：
1、非叶子节点存储的不是数据，为了降低树的高度，增加查询效率。
2、myisam主键索引：叶子节点存储的是数据的地址
3、myisam辅助索引：叶子节点存储的也是数据的地址
4、innodb主键索引：叶子节点存储的是真实的数据，而不是地址
5、innodb辅助索引：叶子节点存储的是主键，然后再利用主键索引查询到数据
6、innodb中，如果没有定义主键，mysql会利用唯一标识创建主键索引
ps. B+树的高度为3的情况下，可以存储2000多万条数据
