前言：
B树和B＋树的概念在算法第四版和大话数据结构中我没有见过，但是在国内计算机系的数据结构这门课里，所用的教材大部分都提到了B树和B＋树，在学到mysql的相关知识时，我才第一次深入了解这两种树形结构。
B树和B＋树的特点
B-树有如下特点:
- 所有键值分布在整颗树中（索引值和具体data都在每个节点里）；
- 任何一个关键字出现且只出现在一个结点中；
- 搜索有可能在非叶子结点结束（最好情况O(1)就能找到数据）；
- 在关键字全集内做一次查找,性能逼近二分查找；
B+树的特点:
与B树不同之处在于，B＋树
- 所有关键字存储在叶子节点出现,内部节点(非叶子节点并不存储真正的 data)
- 为所有叶子结点增加了一个链指针
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。
为什么说B+树比B树更适合数据库索引？
1、 B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。
2、B+树的查询效率更加稳定：由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
3、由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。
也可以这么表达：
- b+树的中间节点不保存数据，所以磁盘页能容纳更多节点元素，更“矮胖”；
- b+树查询必须查找到叶子节点，b树只要匹配到即可不用管元素位置，因此b+树查找更稳定（而且B＋树并不慢）；
- 对于范围查找来说，b+树只需遍历叶子节点链表即可，b树却需要重复地中序遍历，
注：
磁盘块是个虚拟出来的概念，是操作系统中的。操作系统为什么要虚拟个这样的概念出来呢？操作系统与磁盘打交道的最小单位是磁盘块。目前是4k大小。
操作系统操作磁盘，也需要通过磁盘驱动器进行。所以离不开扇区的。
扇区是真实的东西。磁盘驱动器操作磁盘数据，每次都按照扇为最小单位操作。
B树索引相对于哈希索引的优势。
1、因为Hash索引比较的是经过Hash计算的值，所以只能进行等式比较，不能用于范围查询
1、每次都要全表扫描
2、由于哈希值是按照顺序排列的，但是哈希值映射的真正数据在哈希表中就不一定按照顺序排列，所以无法利用Hash索引来加速任何排序操作
3、不能用部分索引键来搜索，因为组合索引在计算哈希值的时候是一起计算的。
4、当哈希值大量重复且数据量非常大时，其检索效率并没有Btree索引高的。
注：想了解哈希值可以参考算法第四版中散列表中提到的散列函数。
注：这篇文章摘录了好几篇文章，并做了相应的修改。所摘录文章的来源已无法考证。如有雷同，私密马赛。