我想知道,在使用主键查找记录时,RDBMS是否需要O(1)时间?
不。在我所知道的所有数据库中,主键索引都是B树索引。在这样的索引中查找特定元素是O(log n)操作,而不是O(1)。
请注意,对于数据库的大小,O(log n)非常接近O(1)。毕竟,十亿的对数仅约为30(以2为底)。