Mysql-索引数据结构选择合理性
前述
磁盘IO时间才是大头
hash结构
加快查找速度的数据结构，常见的有两类：
(1) 树，例如平衡二叉搜索树，查询/插入/修改/删除的平均时间复杂度都是
O(log2N);(2)哈希，例如HashMap，查询/插入/修改/删除的平均时间复杂度都是
O(1); (key, value)
上图中哈希函数h有可能将两个不同的关键字映射到相同的位置，这叫做 碰撞 ，在数据库中一般采用 链 接法 来解决。在链接法中，将散列到同一槽位的元素放在一个链表中，如下图所示： 
Hash结构效率高，那为什么索引结构要设计成树型呢？
不支持范文查询，数据没有维护顺序，如果进行了order by 还要对数据进行排序，在没有重复值的情况下，等值查询效率较高，但是如果重复值较多的话，需要遍历链表，效率也不高，在联合索引方面，只能对这个联合索引进行查询，无法对其中的某个索引进行查询。
Hash索引适用存储引擎如表所示：
| 索引 / 存储引擎 | MyISAM | InnoDB | Memory |
|---|---|---|---|
| HASH索引 | 不支持 | 不支持 | 支持 |
Hash索引的适用性：
InnoDB不支持Hash索引，但InnoDB支持自适应Hash索引，当某个数据经常被访问时，就会把该页的地址存到Hash表中，下次查询就可以直接找到该页的位置
二叉搜索树
如果我们利用二叉树作为索引结构，那么磁盘的IO次数和索引树的高度是相关的。
1. 二叉搜索树的特点
一个节点只能有两个子节点，也就是一个节点度不能超过2
左子节点 < 本节点; 右子节点 >= 本节点，比我大的向右，比我小的向左，即左孩子<根节点<右孩子
但是特殊情况，就是有时候二叉树的深度非常大，比如下图这种情况，为了提高查询效率，就需要 减少磁盘IO数 。为了减少磁盘IO的次数，就需要尽量降低树的高度 ，需要把 原来“瘦高”的树结构变的“矮胖”，树的每层的分叉越多越好。
AVL树
主要是为了控制树的高度，减少IO次数
每访问一次节点就需要进行一次磁盘 I/O 操作，对于上面的树来说，我们需要进行 5次 I/O 操作。虽然平衡二叉树的效率高，但是树的深度也同样高，这就意味着磁盘 I/O 操作次数多，会影响整体数据查询的效率。针对同样的数据，如果我们把二叉树改成 M 叉树 （M>2）呢？当 M=3 时，同样的 31 个节点可以由下面 的三叉树来进行存储：
你能看到此时树的高度降低了，当数据量 N 大的时候，以及树的分叉树 M 大的时候，M叉树的高度会远小于二叉树的高度 (M > 2)。所以，我们需要把 `树从“瘦高” 变 “矮胖”。
B-Tree
B 树的英文是 Balance Tree，也就是 多路平衡查找树。简写为 B-Tree。它的高度远小于平衡二叉树的高度。
你能看出来在 B 树的搜索过程中，我们比较的次数并不少，但如果把数据读取出来然后在内存中进行比 较，这个时间就是可以忽略不计的。而读取磁盘块本身需要进行 I/O 操作，消耗的时间比在内存中进行 比较所需要的时间要多，是数据查找用时的重要因素。 B 树相比于平衡二叉树来说磁盘 I/O 操作要少 ， 在数据查询中比平衡二叉树效率要高。所以 只要树的高度足够低，IO次数足够少，就可以提高查询性能 。
B+Tree
B+ 树和 B 树的差异在于以下几点：
有 k 个孩子的节点就有 k 个关键字。也就是孩子数量 = 关键字数，而 B 树中，孩子数量 = 关键字数 +1。
非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大（或最 小）。
非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中。而 B 树中， 非叶子节点既保存索引，也保存数据记录 。
所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字的大小从小到大顺序链接。
思考题
B+树的存储能力如何？为何说一般查找行记录，最多只需1~3次磁盘IO
Innodb存储引擎默认根页面常驻于内存中，页的大小是16kb，目录项一般就存储两个整数，页号和指向的数据页最小主键值，差不多就是16b，16kb/16b=1k，也就是说一个目录项能指向1k个具体的数据页，而一个数据页又能指向1k条数据，根节点又能指向1k目录页，差不多能存1亿条记录，可能有些数据页不会存满，需要再下一层，所以就是1~3层磁盘IO
