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

Question

我知道二分搜索的工作原理，但我想知道二分搜索的实际用途......我在互联网上搜索，发现主要用途是数据库索引，但我不明白二分搜索如何帮助数据库索引。

Answer 1

假设键已经排序，二进制搜索允许您通过键快速查找记录。如果键的数量很大，则尤其如此。32 次键读取足以在 20 亿个已排序键的集合中找到任何单个唯一键。

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

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

Answer 2

任何时候你有一个排序列表，你都可以使用二分搜索来有效地搜索列表。数据库索引是排序数据的数据结构。

Answer 3

二分搜索计算每一步的下一个位置（中间点）。

DB 的二叉树预先计算每一步的中间点，直到到达单个项目。将所有中间点填充到树中。查询时，DBMS 会查找树。