B+树
平衡二叉树
二叉树的查找的时间复杂度是O(log2N)，其查找效率与深度有关，而普通的二叉树可能由于内部节点排列问题退化成链表，这样查找效率就会很低。因此平衡二叉树是更好的选择，因为它保持平衡，即通过旋转调整结构保持最小的深度。其查找的时间复杂度也是O(log2N)。
但实际上，数据库中索引的结构也并非AVL树或更优秀的红黑树，尽管它的查询的时间复杂度很低。
B-树
局部性原理与磁盘预读：
由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：
当一个数据被用到时，其附近的数据也通常会马上被使用。
程序运行期间所需要的数据通常比较集中。
由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。数据库的瓶颈在磁盘IO，平衡二叉树没有很好的解决这个问题，所以诞生了B-树。
B-树巧妙地利用磁盘预读原理，B树的每个节点可以存储多个关键字，将节点大小设置为磁盘页大小，每次读取磁盘页就会读取一整个节点，这使得树深度非常小。进而磁盘IO就非常少，更多的是在内存中对取出来的数据进行查找。
B+树
为什么会出现B+树？
B-树：有序数组+平衡多叉树
B+树：有序数组链表+平衡多叉树
B+树关键数据存储在叶子节点，非叶子结点只用来做索引，而叶子节点包含一个指向下个叶子节点的指针，这个优化使得B+树区间查找变的更快。
走进搜索引擎的作者梁斌老师针对B树、B+树给出了他的意见（为了真实性，特引用其原话，未作任何改动）： “B+树还有一个最大的好处，方便扫库，B树必须用中序遍历的方法按序扫库，而B+树直接从叶子结点挨个扫一遍就完了，B+树支持range-query非常方便，而B树不支持。这是数据库选用B+树的最主要原因。
比如要查 5-10之间的，B+树一把到5这个标记，再一把到10，然后串起来就行了，B树就非常麻烦。B树的好处，就是成功查询特别有利，因为树的高度总体要比B+树矮。不成功的情况下，B树也比B+树稍稍占一点点便宜。
B树比如你的例子中查，17的话，一把就得到结果了，
有很多基于频率的搜索是选用B树，越频繁query的结点越往根上走，前提是需要对query做统计，而且要对key做一些变化。
另外B树也好B+树也好，根或者上面几层因为被反复query，所以这几块基本都在内存中，不会出现读磁盘IO，一般已启动的时候，就会主动换入内存。”为什么InnoDb使用B+树做为索引底层结构，而不是平衡二叉树和B-树？
首先为什么不用平衡二叉树，因为平衡二叉树没有充分利用磁盘预读，导致需要磁盘io次数更多，由于磁盘IO操作非常耗时，导致性能不好。
B+树查找过程
上图是一个b+树，如果要查找29，首先将根节点通过一次IO操作加载到内存，通过二分查找确定29在17和35之间，通过中间的p2指针，将它指向的节点加载到内存，此时两次IO操作；在通过二分查找确定在26和30之间，再通过指针将它指向的节点加载到内存，此时第三次IO操作；再通过二分查找找到29。
字符串索引也是一样，底层也是二进制存储，也可以通过二分查找；不同的是，字符串可以通过模糊查找，对前n个字符建索引，需要注意的是：前缀索引不能用在排序和覆盖索引上，并且字符串索引有长度限制：
innodb引擎的每个索引列长度限制为767字节（bytes），所有组成索引列的长度和不能大于3072字节
myisam引擎的每个索引列长度限制为1000字节，所有组成索引列的长度和不能大于1000字节
一颗B+树可覆盖的数据量
innoDB存储引擎一页大小是16k，B+树一个节点为一页，一页可以存多少数据？
假设主键为bigint类型，8字节，指针在innoDB是6字节，所以一个完整单元就是14字节。一页可以有多少个单元呢？16✖️1024/14=1170，假设一条数据大小为1k，那么每个叶子节点可以存16k/1k=16条记录，高度为2的b+树可以存储1170×16=18720条记录。高度为3的b=树可以存储1170×1170×16=21902400条记录。