mysql - 在主键上搜索时从 MySQL 数据库中获取一行的时间复杂度是多少？

Question

我有一个庞大的数据库，想要快速检索数据(只根据主键搜索)。数据库的时间复杂度为 O(1) 是因为它就像一本字典吗？ (因为只会获取一行，因为我只在主键上进行搜索)

Answer 1

可以通过不同的方式在主键中搜索一条记录，具体取决于查询优化器决定的最有效方式。对于小表，可以选择索引扫描。但是，对于大多数表，更有可能进行索引查找。这是一个二进制搜索。

二分查找的时间复杂度大概在 O(log n) 左右。

从索引中检索到一个键后，获取单个记录的非键字段将是 O(1)。