database - 数据库如何使用聚集索引定位记录？

Question

在非聚集索引中，每个条目都是固定长度的，因此数据库可以使用二进制搜索在 O(nlogn) 时间内找到记录地址。

由于表具有可变长度记录，并且聚集索引使用基础表本身进行搜索（或者我错了吗？），数据库如何在 O(nlogn) 时间内找到特定键的记录？

Answer 1

每个条目都是固定长度的

对于现实世界的数据库而言并非如此。

行被分成称为页的组。页面具有固定大小 (~8KB)。它们形成一个树结构，顶层链接到底层页面的物理位置。

这允许树从上到下遍历，在每一步进入相关分支。

聚集索引通常具有与非聚集索引完全相同的物理结构。