在“问题1-方案3”的基础上，由于所有数据行都存储在叶子节点，B树的叶子节点本身也是有序的，可以增加一个指针，指向当前叶子节点按主键顺序的下一叶子节点；查询时先查到左界，再查到右界，然后从左界到有界线性遍历。
乍一看感觉方案1比方案2好——时间复杂度和常数项都一样，方案1还不需要改动。但是别忘了局部性原理，不管节点中存储的是数据行还是数据行位置，方案2的好处在于，依然可以利用页表和缓存预读下一节点的信息。而方案1则面临节点逻辑相邻、物理分离的缺点。
引出B+树综上，问题1的方案2与问题2的方案1可整合为一种方案（基于B树的索引），问题1的方案3与问题2的方案2可整合为一种（基于B+树的索引）。实际上，数据库、文件系统有些采用了B树，有些采用B+树。
由于某些猴子暂未明白的原因，包括MySQL在内的主流数据库多选择了B+树。即：
主要变动如上所述：
修改key与子树的组织逻辑，将索引访问都落到叶子节点
按顺序将叶子节点串起来（方便范围查询）
B树和B+树的增、删、查过程B树的增删过程暂时可参考从B树、B+树、B*树谈到R 树的“6、B树的插入、删除操作”小节，B+树的增删同理。此处暂不赘述。
Mysql索引优化根据B+树的性质，很容易理解各种常见的MySQL索引优化思路。
暂不考虑不同引擎之间的区别。
优先使用自增key作为主键前面的分析中，假设用4B的自增key作为索引，则m可达到512，层高仅有3。使用自增的key有两个好处：
自增key一般为int等整数型，key比较紧凑，这样m可以非常大，而且索引占用空间小。最极端的例子，如果使用50B的varchar（包括长度），那么m = 4 * 1024 / 54m = 75.85 ~= 76，深度最大log(76/2)(10^7) = 4.43 ~= 5，再加上cache缺失、字符串比较的成本，时间成本增加较大。同时，key由4B增长到50B，整棵索引树的空间占用增长也是极为恐怖的（如果二级索引使用主键定位数据行，则空间增长更加严重）。
自增的性质使得新数据行的插入请求必然落到索引树的最右侧，发生节点分裂的频率较低，理想情况下，索引树可以达到“满”的状态。索引树满，一方面层高更低，一方面删除节点时发生节点合并的频率也较低。
优化经历：
猴子曾使用varchar(100)的列做过主键，存储containerId，过了3、4天100G的数据库就满了，DBA小姐姐邮件里委婉表示了对我的鄙视。。。之后增加了自增列作为主键，containerId作为unique的二级索引，时间、空间优化效果相当显著。
最左前缀匹配索引可以简单如一个列(a)，也可以复杂如多个列(a, b, c, d)，即联合索引。如果是联合索引，那么key也由多个列组成，同时，索引只能用于查找key是否存在（相等），遇到范围查询(>、<、between、like左匹配)等就不能进一步匹配了，后续退化为线性查找。因此，列的排列顺序决定了可命中索引的列数。
如有索引(a, b, c, d)，查询条件a = 1 and b = 2 and c > 3 and d = 4，则会在每个节点依次命中a、b、c，无法命中d。也就是最左前缀匹配原则。
=、in自动优化顺序不需要考虑=、in等的顺序，mysql会自动优化这些条件的顺序，以匹配尽可能多的索引列。
如有索引(a, b, c, d)，查询条件c > 3 and b = 2 and a = 1 and d < 4与a = 1 and c > 3 and b = 2 and d < 4等顺序都是可以的，MySQL会自动优化为a = 1 and b = 2 and c > 3 and d < 4，依次命中a、b、c。
索引列不能参与计算有索引列参与计算的查询条件对索引不友好（甚至无法使用索引），如from_unixtime(create_time) = '2014-05-29'。