B-tree
0 / 0 / 创建于 4年前
HelloWorld-Q 的个人博客
每个节点维护两个数据，并指向最多 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 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
推荐文章：