二叉树 和 Btree的查找性能比较
如果是平衡二叉排序树
则 n个节点的二叉排序树的高度为 Log2(n+1),其查找效率为 O(Log2n)，近似于折半查找。
如果二叉排序树不平衡，
则其深度可达到n，查找效率为O(n)，退化为 顺序查找。
一般的，二叉排序树的查找性能在O(Log2n)到O(n)之间。
因此，为了获得较好的查找性能，就要构造一棵平衡的二叉排序树。
Btree
B树的搜索复杂度为 O(h)=O()，所以树的出度d越大，深度h就越小，I/O的次数就越少。
B+Tree恰恰可以增加出度d的宽度，因为每个节点大小为一个页大小，所以出度的上限取决于节点内key和data的大小：
如果是查找效率（即比较次数）的话，实际上二叉树可以说是最快的了，但是，我们的文件索引是存放在磁盘上的，所以我们不仅要考虑查找效率，还要考虑磁盘的寻址加载次数哦，而这也是我们为什么要用 B 树的原因。
- btree图：
图中是一棵m = 3 的 3 阶 B 树，可以看出，树中有些节点是有多个元素的，并且和二叉查找树一样，左节点的所有元素的值都比父亲元素小。例如对于(3, 7)这个节点。两个元素把这个节点分割成三个值域，即可以有 3 个孩子。2 相当于 3 的左孩子节点，而 （4，6）相当于 3 的右孩子，同时也是 7 的左孩子，而 9 是 7 的右孩子。
和二叉查找树还是很相似滴，都是有序，且左孩子小，右孩子大，只是 B 树的一个节点可以有多个元素，并且有多个分支。而这些分支以及元素的数量规则，可以从上面的五个规则中查找哈。说实话，我也懒的记那些规则，只知道个大概以及 B 树的应用即可。
- 二叉查找树
1、在 B 树中的查找次数。
现在假如我们要查询元素 9,对于 B 树，我们需要进行4次比较，例如：
第一次比较： 10 比较，比 10 小，所以再 10 的左孩子找。
第二、三次比较：和 3 比较，比 3 大，这个时候我们还得和 7 比较。
第四次比较：和 9 比较，相等，找到目标树，返回。
所以最终的结果需要 4 次比较。
2、在二叉树的比较结果
为了节省篇幅，我就不逐个比较了，相信你也一眼就看出来了，也是需要 4 次比较。如图
同样都是四次比较，而且，B 树的每一个节点，如果存放的元素比较多，那么 B 树的比较次数会更多，为什么就说 B 的效率比 二叉查找树快呢？
确实，如果单单从比较次数看的话，二叉查找树确实不比 B 树差，不过你忽略了一个很重要的点，那就是磁盘的寻址加载次数。
我们知道，在把磁盘里的数据加载到内存中的时候，是以页为单位来加载的，而我们也知道，节点与节点之间的数据是不连续的，所以不同的节点，很有可能分布在不同的磁盘页中。所以对于上面的二叉查找树，我们可能需要进行 4 次寻址加载
而对于 B 树，由于 B 树的每一个节点，可以存放多个元素，所以磁盘寻址加载的次数会比较少，例如上面的例子中，用 B 树的话，只需要加载 3 次
我们都知道，在内存的运算速度是非常快的，至少比磁盘的寻址加载速度，快了几百倍，而我们进行数值比较的时候，是在内存中进行的，虽然 B 树的比较次数可能比二叉查找树多，但是磁盘操作次数少，所以总体来说，还是 B 树快的多，这也是为什么我们用使用 B 树来存储的原因
实际上磁盘的加载次数，基本上是和树的高度相关联的，高度越高，加载次数越多，越矮，加载次数越少。所以对于这种文件索引的存储，我们一般会选择矮胖的树形结构。例如有 1000 个元素，如果是二叉查找树的话，高度可能高达 10 层,而如果用 10 阶 B 树的话，只需要三四层即可。
B 树处于会用在少部分的文件索引（数据库索引）外，应用的最多的就是文件系统了。