B-树 我们知道B-树每个节点上包含着数据和指针,每个指针指向其一个子节点的位置, B-树的查找需要一次对每个节点进行二分查找,直至找到或返回null。通常,可以引入布朗过滤器等方式加速查找。B-树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点(其搜索性能等价于在关键字全集内做一次二分查找)。 应用场景: 一般B-树常常作为磁盘的查找的数据结构使用。 一般磁盘为了减少寻道时间,往往会进行预读,一次…

2013年8月1日 0条评论 8点热度 阅读全文