5.索引的代价
索引的代价主要是空间与时间代价。
空间上：创建索引需要存储空间。一个数据页的存储空间是16kb，如果一棵B+树有很多数据页，将会消耗较大的存储空间。
时间上：进行数据的增删改操作，同时需要对索引进行维护。主要是页面移动、页面回收、页分裂等代价。
后面的博客中，我们也将一起学习在哪些字段上适合创建索引。
6.B+树与常见的查找数据结构对比
Mysql索引的作用就是减少I/O次数，从而实现数据查找速度的提升。因此我们将以这个作为目标深入对比Hash索引,ALV树，B树和B+树，从而剖析为什么要选择B+树作为Mysql的索引底层数据结构。
6.1 Hash结构
一般提到要加快查找的速度，我们都会考虑两种数据结构：树和哈希。哈希算法的查找效率很高，可以很快的定位到数据的具体位置,通常1次检索，时间复杂度平均为
O(log2n)
而B+树还需要多次I/O,时间复杂度为O(n)
HashMap就是典型的Hash算法应用实例，下图展示了HashMap的数据结构。
哈希算法可以通过计算使一个key对应唯一value。这样我们就可以通过哈希算法计算数据应该存储的地址，把一个数据映射到一个地址。
但有时候，可能会出现两个key计算得到的地址相同的情况，我们称之为碰撞。这时我们
可以通过链接法解决。
如下Demo01是采用普通算法进行搜索，输出时间是1604ms.
public class Demo01 { public static void main(String[] args) { int [] arr = new int [100000]; for (int i = 0; i < 100000; i++) { arr[i] = i ; } long start = System.currentTimeMillis(); for (int i = 0; i < 100000; i++) { // search 10000 times int temp = i; for (int j = 0; j < arr.length; j++) { if(temp == arr[j]) { break; } } } long end = System.currentTimeMillis(); System.out.println("cost " +(end - start) + " ms."); } }
下面算法则花费时间9ms,显然hash算法的查找效率比全表扫描快很多
public class Demo02 { public static void main(String[] args) { HashSet set = new HashSet(100000); int [] arr = new int [100000]; for (int i = 0; i < 100000; i++) { set.add(i); } long start = System.currentTimeMillis(); for (int i = 0; i < 100000; i++) { // search 10000 times int temp = i; set.contains(temp); } long end = System.currentTimeMillis(); System.out.println("cost " +(end - start) + " ms."); } }
既然hash算法的查询效率这么高，为什么InnoDB、MyISam的索引结构要设计成为树型解构呢？
hash算法主要适用于等值判断(==，In查询)，对于范围查询，还是只能通过全表扫描来完成，时间复杂度将会退化为O(n).
Hash算法存储元素是无序的，如果需要进行OrderBy等操作无法完成。
Hash算法不适合进行联合索引的查询。
当索引列重复元素较多时(比如性别)，会造成大量的哈希冲突,解决哈希冲突将导致效率较低，查找效率也会变低。
总结来说，索引操作并不是只进行等值判断，或者重复元素较多的列，不适合使用hash索引。
索引引擎对于hash索引的支持情况如下图。
hash结构的索引适用于key-value型的数据库，Redis是现在很火的非关系型数据库，它的底层核心就是hash索引。Mysql中如果需要频繁的对索引进行等值判断，可以考虑使用Memory引擎。
另外，InnoDB虽然不支持Hash结构的索引，但是它提供了自适应哈希索引(Adapter Hash Index).如果某个数据页经常被访问，其地址就会被存储到哈希表中，这样下次访问时就可以直接找到这个页面的位置，这也使B+树具备了hash索引的优点。其过程可以参考下图理解。
可以通过如下命令查看数据库中是否开启了自适应hash索引。
6.2 二叉搜索树
二叉搜索树具有如下特点：
- 一个节点最多有两个子节点，也就是节点的度不能超过2
- 每个节点左子结点<本节点<右子节点。
其结构可以参考下图。
二叉搜索树的查找很简单，从根节点开始查找，如果查找元素比当前节点小，则在左子树中查找，如果查找元素比当前节点大，则去右子树中找。如果相等，则返回当前节点。二分查找就是利用二叉搜索树实现的。其平均时间复杂度也是O(log2n)
但是二叉搜索树的最大时间复杂度也是O(n)
因为当数据是有序时，构建的二叉搜索树会退化为线型结构哦。
为了避免出现上面的情况，我们需要对二叉搜索树的深度进行限制，AVL树就做到了这一点。
6.3 AVL树
AVL树即平衡二叉搜索树。AVL树可以是空树，除了这种特殊情况外，它要求：
- 左、右子树的高度差不能超过1
- 左、右子树也都是一棵平衡二叉树
上面的平衡二叉树查找一个元素最多需要五次I/O操作，有没有办法让其查找效率更高呢？
我们可以把二叉树变成m叉树，比如同样多数量的节点，在下图的三叉树中只需要四次I/O操作就可以查找到一个元素了。
基于这种把树变矮胖，从而减少树的层数的思想，我们设计了B树。
6.4 B树
B树的英文是Blance Tree，又称为多路平衡查找树。B树的结构如下图。
我们可以观察下它的特点。上面磁盘块1中有两个元素，分别是17和35，磁盘块2的元素都小于17，磁盘块3的元素位于17与35之间，磁盘块4的元素都大于35.
在一棵B树中，子结点数量的最大值称为阶，上图中B树的阶为3.
我们不妨回顾下B+树，然后看看B树与B+树有何不同。
我们看到，页30的节点中存储了index和page_no,而它的子结点页10则存储了具体的记录数据。但B树的叶子节点与非叶子节点存储的信息都完全独立。换句话说，B树的节点不存在上下级关系。如果使用B树作为索引的数据结构，我们需要在每个节点中存储完整的记录信息。
B树具有如下特性。
- 如果插入数据、删除数据导致树不平衡，会自动调整至平衡。
- 关键字集合在整个树中，即叶子节点与非叶子节点都存放数据，搜索可能在叶子节点中结束。
6.6 B+树
B+树其实是在B树的基础上进行的改进。B+树更加适合文件索引的系统。现在总结下B树与B+树的区别。
在B+树中，一个节点有k个孩子(子结点)就有k个关键字(data)，而在B树中，一个节点的孩子树=关键字数+1。
B+树非叶子节点只用于索引，不存储数据.而B树中各个节点存储的都独立存储数据。
B+树所有关键字都在叶子节点出现，并且叶子节点之间通过双向链表来彼此链接，叶子节点内的数据按照顺序使用单链表连接。
上面我们提到了B+树的中间节点只用于索引，不存储数据，这有什么好处呢？
B+树的查询效率更加稳定。每次查找的I/O次数更少。
B+树的查询时I/O次数更少，查询效率更快。因为B+树的非叶子节点只用于索引，不存储数据的信息，就可以有更多的子树，这会使其更加矮胖，也就是阶数更低，查询时I/O次数更少。
B+树的范围查询效率更高，由于B+树的叶子节点存储了所有的记录信息，并且是按照顺序排列，我们在查找时通过链表指针就可以快速进行范围查询了。
6.7 R树
另外对于地图等高维搜索空间问题一般使用R树作为索引的数据结构，MySQL不支持使用R树作为索引。
