如何在数据库索引中使用二进制搜索

Question

我知道二进制搜索是如何工作的,但我想知道二进制搜索的实际用途......我通过互联网搜索,我发现主要用途是数据库索引,但我无法理解二进制搜索如何帮助数据库索引.

Answer 1

二进制搜索使您可以快速地按记录的键查找记录，前提是键已排序。如果键的数量很大，则尤其如此。读取32个键就足以在二十亿个排序键的集合中找到任何单个唯一键。

二进制搜索以这种方式工作，因为每次搜索尝试都会将要搜索的记录数减少一半。

也就是说，数据库通常使用一些其他类似于二叉树的数据结构（例如b树或红黑树）来执行索引。使用二叉树消除了在搜索之前对键列表进行排序的要求。

Answer 2

只要您有排序列表，您就可以使用二分搜索来有效地搜索列表。数据库索引是排序数据的数据结构。