每个解决方案都是为了解决某一类问题而创建的，所以在问为什么使用某个解决方案的时候，其实质就是探究这个解决方案是用来满足什么样的需求，解决什么样的问题解决。所以探究InnoDb为什么使用B+树的问题，就是弄清楚B+树是用来满足什么需求，解决什么样的问题。我们来看看一些常用的SQL语句，满足什么样的需求#根据某个值查询相应的信息selectid,name,emailfromuserwhereid=1;#通过区间值查询selectid,name,emailfromuserwhereid>12andid<20#Queryandsortbyrangeselectid,name,emailfromuserwhereid<123orderbyiddesclimit10;从上面几个常用的SQL我们可以看出，在数据库中查找数据的过程中主要有三类需求：基于某个值的准确快速查找基于上位快速查找该范围内的数据以及范围的下限查询符合条件的记录，并按照一定的字段进行排序所以，你需要找到一个满足以上所有要求的方案。目前在查询中常用的数据结构有两种：哈希表树哈希表哈希表（hashtable）是一种基于（key,value）直接访问的数据结构，它使用了哈希函数将key转换成value映射到哈希表的对应位置，查找效率非常高。索引中的一种索引类型，哈希索引是基于哈希表实现的。假设我们在名字上建立一个哈希索引，查找过程如下图所示：对于每一行数据，存储引擎都会计算一个哈希码（上图中哈希表的位置），其中的每个元素哈希表指向数据行的指针。由于索引本身只存储对应的哈希值，因此索引的结构非常紧凑，可以直接基于键值。找到对应的数据记录，使得哈希索引查找速度非常快！但是哈希索引也有它的缺点，如下：只有与索引的所有列完全匹配的查询才有效。比如我在(name,address)列上建了一个hash索引，如果我只查询数据列名，这个索引是用不上的。hash索引不是按照索引值的顺序存储的，即hash函数计算出的key的hash值是没有顺序的，所以不能用来排序，也不能按照区间查找.哈希索引只支持相等比较查询，比如=和in()，不支持范围搜索，比如id>17。因此，哈希索引只适用于特定的场合，它确实可以带来很大的性能提升在合适的场景中使用。例如，在InnoDB中，有一个特殊的功能叫做“自适应哈希索引”。如果InnoDB注意到某些索引列值被频繁使用，它会在基于内存的B+树索引之上创建一个哈希索引，这样B+树也能兼具散列索引的优点。因此，哈希表结构不能满足上述要求。接下来我们看看树。TreeBalancedBinaryTree平衡二叉树可以用于搜索，它的搜索时间复杂度大约为O(log2n)，但是平衡二叉树可以作为索引结构吗？答案是不。因为数据库表中的数据通常很多，所以一般都是存储在磁盘上。磁盘的速度比内存慢很多倍，所以要尽量减少读磁盘的次数，通过从内存中读取数据来提高速度。那么，如何将尽可能多且有效的索引数据放入内存呢？这里需要解决两个问题：1.尽可能多的读取磁盘数据时，是按磁盘块读取（局部性原则和磁盘预读），而不是一个一个读取。当使用树结构作为索引数据结构时，我们每次查找数据都需要从磁盘中读取一个树节点，也就是对应的一个磁盘块，所以如果能把尽可能多的数据放到磁盘块中，那么每次都会读取更多的数据。在一棵平衡二叉树中，每个节点只存储一个键值和数据，也就是说在存储时，每个磁盘块只存储一个键值和数据。如果存储的数据量很大，可想而知平衡二叉树的节点会非常多，树的高度会非常高。查找数据时会进行多次磁盘IO，效率极低。因此，平衡二叉树无法解决在内存中存储尽可能多的索引的问题。2、有效索引数据我们所说的平衡二叉树是指逻辑结构上的平衡二叉树，它的物理实现是一个数组。因此，在逻辑上相似的节点上，它们的物理位置可能相距很远。因此，每次读取的磁盘页数据中有很多可能没有被使用，即有效的索引数据不多，因此在查找过程中仍然需要进行很多磁盘读取操作。所以平衡二叉树也不能解决这个问题。于是，发明了可以解决这两个问题的数据结构——B树。B-treeB-tree（BalanceTree），意为平衡树。B树是从平衡二叉树演化而来的。B树的每个节点可以存储多个关键字。它将节点的大小设置为磁盘页的大小，充分利用了磁盘的预读功能。每次读取磁盘页面时，都会读取整个节点。也因为每个节点存储了很多关键字，所以树的深度会很小。反过来，要进行的磁盘读操作次数会很少，更多的是在内存中查找读取的数据。B-tree的结构示例如下图所示：由于B-tree的每个节点，即每个磁盘块存储的数据较多，所以解决了上面提到的存储尽可能多的索引的问题一定程度上。也在一定程度上解决了存储尽可能多的有效索引的问题。但是B树只是在一定程度上解决了问题，我们还需要更好的解决问题。也就是它能存储更有效的索引吗？答案是肯定的。这时候B+树就需要登场了。更好解决问题的B+树B-tree在一定程度上解决了问题，而由B-tree演化而来的B+树更能解决问题，所以在实际使用中几乎没有使用B-tree。B+树结构示意图如下：那么B+树和B树有什么区别呢？B+树中，非叶子节点上不存储数据，只存储键值。因为数据库中页面的大小是固定的，InnoDB中页面的默认大小是16KB。如果没有存储数据，那么节点可以存储更多的键值，对应树的顺序树就会更大。对于同样的数据量而言，要求的树高会更低，树会更矮更胖。这样在查找数据时会减少磁盘IO次数，提高查询效率。由于B+树的阶数等于键值的个数，假设B+树的一个节点可以存储1000个键值，那么一棵3层的B+树可以存储1000x1000x1000=10亿条数据。而且一般根节点常驻内存，所以要查找10亿条数据，只需要2次磁盘IO。B+这个特性解决了上面说的索引数据存储多少的问题，查询效率也高。B+树的叶子节点中的索引数据是按顺序排列的，叶子节点通过双向链表连接起来。这个特性使得B+树实现范围搜索、排序搜索、分组搜索等操作变得异常简单。但是，由于B树的数据分散在各个节点中，实现这些操作并不容易。由于索引数据是按顺序排列的，即每读取一个数据页，里面的大部分索引数据都需要用到，所以也很好的解决了上面提到的如何存储尽可能多的有效数据.索引数据问题。小结通过上面的分析，我们可以发现，在使用某个方案的时候，这个方案一定是用来满足某个需求的，而在满足需求的过程中会遇到一些问题，最终的方案一定是能够解决的尽可能解决问题并满足需求。所以，如果你探索清楚某个方案是满足什么样的需求，解决什么样的问题，如何解决问题，你就会明白为什么要用这个方案。更多好文，关注公众号获取
