B-tree
每个节点维护两个数据,并指向最多 3 个子节点。如图 3 个子节点的数据分别为:小于 17, 17 ~ 35 ,大于 35。
假设,从上图中查找 10 这个数,步骤如下:
找到根节点,对比 10 与 17 和 35 的大小,发现 10 < 17 在左子节点,也就是第 2 层节点;
从根节点的指针,找到左子节点,对比 10 与 8 和 12 的大小,发现
8 < 10 < 12
,数据在当前节点的中间子节点,也就是第 3 层节点;通过上步节点的指针,找到中间子节点(第 3 层节点),对比 10 与 9 和 10 的大小,发现
9 < 10 == 10
,因此找到当前节点的第二数即为结果。
加上忽略的 12 个数据,从 26 个数据中查找一个数字 10,仅仅用了 log3(26)≈ 3
次,而如果用平衡二叉树,则需要log2(26)≈ 5
次,事实证明,多叉树确实可以再次提高查找性能。
多叉树是在二分查找树的基础上,增加单个节点的数据存储数量,同时增加了树的子节点数,一次计算可以把查找范围缩小更多。
优点:二叉平衡树的基础上,使加载一次节点,可以加载更多路径数据,同时把查询范围缩减到更小。
本作品采用《CC 协议》,转载必须注明作者和本文链接
推荐文章: