innodb选择了B+树来作为索引和数据存储的数据结构，这也是今天聊的主题：为什么innodb要选择B+树来作为索引和数据存储的数据结构。下面先来看看B+树是什么样子的，脑海里现有一个概念：
可以看到上图有几个比较显著的特征：
1）是一个有序的2层的树形结构
2）叶子节点根据非叶子节点的key值分布，上层的key值是它下层的起始值
3）叶子节点间有指针相连
4）最后说一个易被误解的地方，叶子节点里看起来是个数组，其实真实结构是个链表
大概知道了B+树是什么样的，接下来就可以来聊聊，数据结构那么多。为什么innodb选择了B+树结构，为何不选择hash结构、或者其他的树形结构呢。我们可以从这三个方向出发考虑：内存大小是有限的、查询效率的瓶颈IO次数、查询效率的提高的重要因素——索引是是否是有序的。
hash表
先说说hash表，我们画一张图来观察下hash表的大体结构：
可以看到上图就是一个典型的hash表，数据根据hash算法散列在hash表中，可以观察看看hash结构是不是有序的。很显然，并不是，hash算法有一个势必会遇到的问题，那就是hash碰撞——hash算法计算出来的值是一样的。通常，hash表的解决方案如上图所示：拉链法，同样的值用链表挂在同一个hash值下面。并且当hash算法不够散列的时候，某条拉链会特别的长。
我们都知道内存速度比磁盘块，但是相应的，内存价格也相当高昂，简而言之内存是有限的，而MySQL作为关系型数据库数据量是相当可观的（行数多，且大部分表每行占用空间不小），当数据量到达一定层级的时候，我们对数据的处理务必会使用分而治之的思想，将他们分块读取。而当hash表的某条拉链特别长，并且拉链上的数据是无序的，那么当我们的需要的数据正好在拉链上时，IO读取的次数便不可控制了。
树结构
当然，这里说的是B+树外的其它树结构，我们先来列举一些比较常见的树形结构：二叉搜索树BST、二叉平衡树AVL、红黑树。它们都是有序的，但是有一个共同的问题：他们都是二叉树。当数据量大时，树的深度会变的非常大。相应的，我们取数据经历的IO次数也是非常的多。相信这时稍微有点脑子的人都想的到，那我把分叉增多不就好了吗？是的，所以B树应时而生，我们来看看B树的结构：
可以看到我白嫖了自己上面B+树的图片对它做了少许调整，没办法画图真的太难了（白嫖真的使我快乐）。B树和B+树其实很像，认真观察还是能发现一些不同点的：
1）B树的叶子节点之间没有指针相连
2）B树上是没有重复节点的
当用B树的结构组织页时，我们可以想象一下数据要如何分布：数据有序的分布在B树上，由于B树是没有重复节点的，所以数据必须放在key的格子里（如上图比如25是主键值，数据值就要放在25的格子里）。但是上一篇聊表空间的时候我们就知道了页的大小是有限制的，B树的节点大小是有限的，将数据放在key的格子里，一个节点的数据行数势必不会大，相应的，分叉数量也不会大。这里我们打一下比方（比方：做个人？）：假设1行数据总大小1k，我们的页是16k，就算无视指针等其它花销，我们一个页即一个节点只能放16行数据，那么，两层的B树能放的数据为：16+16*16 = 272行，三层的B树能放的数据为：272 + 16*16*16 = 4368行......在我们动辄几万几十万条数据的关系型数据库中，这显然是不够放的。然而当树深度增加，那么和上面一样的问题又出现了，树越深，我们要读取页的次数就越多，即IO次数越大。因此，聪明人们又对B树做了一次改进，B+树从此诞生。
B+树
为了方便观察，我们把上面的B+树图片拷贝一份下来。明显的，B+树与B树相比，key值是可以重复的：叶子上的起始点基本都能在上层找出，这意味着B+树的非叶子节点里面仅仅只放key值便可以了，数据统统放在叶子节点上。这里我们打一下比方（比方：没完了是不是？）：key值25(bigint)和它后面的指针为一组数据，这组数据大小为10个字节。那么一页16k可以放1638个key值，两层1638*1638=2683044组key，假设第三层为叶子节点，每行数据1k，那么三层的B+树可存放的数据量即为：2683044*16=42928704，四千两百多万条数据，这已经满足了大部分关系表的需求（再大考虑分库分表）。因此，使用B+树数据结构，查询数据的IO次数基本在3次以内。
此外，在范围查询的时候，由于叶子节点间的指针的存在，范围查询对B+树来说不会又其它什么多余的消耗。所以，显而易见，为什么选择B+数结构？战术后仰。
如有错误，敬请斧正；欢迎转载，但请务必注明出处；最后，在此向神奇的海螺保证，绝不太监！！！