database - 二进制搜索如何用于数据库索引

Question

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

Answer 1

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

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

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