当前位置: 首页 > >

二叉树 和 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 树处于会用在少部分的文件索引(数据库索引)外,应用的最多的就是文件系统了。



友情链接: