m 分查找
一个比较产生两个决策结果,二-决策的计算机硬件实现更高效。
我们可以想象给一个 array, 一个 key, 在某台 god machine 上有一个操作:cmp-multi array, key, n, m
它能在一个时钟周期内决策出 key 是落在 n-elem array 的 m 等分(最后一分要小点)的哪一份,那在这种情况下 m 分查找就比 2 分查找要快。
实际上,B-Tree 的搜索可以看成是这样的一个 m 分搜索。
一个比较产生两个决策结果,二-决策的计算机硬件实现更高效。
我们可以想象给一个 array, 一个 key, 在某台 god machine 上有一个操作:cmp-multi array, key, n, m
它能在一个时钟周期内决策出 key 是落在 n-elem array 的 m 等分(最后一分要小点)的哪一份,那在这种情况下 m 分查找就比 2 分查找要快。
实际上,B-Tree 的搜索可以看成是这样的一个 m 分搜索。