dbインデックスファイルの実装

Question

私は実際のデータファイルを指し示す（キー、ポインタ）レコードの集合を保持する固定サイズのページからなるデータベースインデックスファイルの設計を試しています。

ページベースのデザインはすべてを複雑にします。最も単純なアプローチでは、ソートされた順番でレコードを保持する必要がありました（つまり、ページ0はレコード0 1 3 6、ページ1はレコード7 8 12 15 ...など）。レコードはシーケンシャルではなくページ（ページヘッダ、空き領域など）に存在するため、ソートされたファイルのバイナリ検索。

バイナリ検索を使用するページで完全にソートされたインデックスファイルを検索する方法に関するガイダンスはありますか？

編集：ページベースのbtreeの実装は今は私にとっては複雑すぎます。私は上記のような簡単なアプローチを達成した後にそこに行きたい。

Answer 1

これは後で簡単に処理できました。

途中のページを読んでください。最初のレコードと最後のレコード（またはページが内部的にソートされていない場合は、最小または最高のインデックスを持つレコード）を確認します。検索キーに応じて右または左に移動します。ループ。

Answer 2

B-tree from wikipedia

Answer 3

最も簡単な方法は、使用するとメモリだけでそれを維持したいのインデックスを構築することが一般的です。こうすることで、インデックスの作成方法とは別に、データストレージとアクセスを最適化できます。

私が類似のものを実装したとき、私はインデックスをファイルの大きな塊として保存し、次に大きな塊としてデータを入れました。