database - データベースはクラスター化インデックスを使用してどのようにレコードを検索しますか?

Question

非クラスター化インデックスでは、各エントリは固定長であるため、データベースはバイナリ検索を使用して O(nlogn) 時間でレコード アドレスを見つけることができます。

テーブルには可変長のレコードがあり、クラスター化インデックスは基になるテーブル自体を検索に使用するため (または間違っていますか?)、データベースは O(nlogn) 時間で特定のキーのレコードをどのように見つけますか?

Answer 1

各エントリは固定長です

実際のデータベースには当てはまりません。

行はページと呼ばれるグループに分割されます。ページのサイズは固定されています（〜8KB）。それらはツリー構造を形成し、最上位レベルが最下位レベルのページの物理的な場所にリンクしています。

これにより、ツリーを上から下にトラバースし、各ステップで関連するブランチに入ることができます。

クラスター化インデックスは通常、非クラスター化インデックスとまったく同じ物理構造を持っています。