2.txt

锅包肉包锅

先说B树，理解较浅，只能简单形容，B树就是类似于一个我的电脑，电脑里面有四个区分盘，每个盘下面有若干个文件夹，文件夹下面还是一堆文件夹。
B-（杠）不是减
B-树一个节点可以有多个数，每个节点上也都是关键字，关键字不能重复。
一个几点中的多个数，任意相邻两个数为范围例如：
	12		15		18
<12		 12~15	     15~18	    >18
m-路查找树，高度为h
拥有的关键字最大个数为m^n-1(不是异或)

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，一般已启动的时候，就会主动换入内存。

为什么说B+tree比B树更适合实际应用中操作系统的文件索引和数据库索引？
第一，节点没有关键字的具体信息，内部节点少。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
第二，查询效率稳定，每一次查询都必须从根节点到叶子节点，所以查询时间都差不多。
第三，方便扫描数据库，B树每次扫描数据库都需要中序遍历，而B+树可以直接在叶子节点扫描。

饼神辛苦