db索引文件執行

Question

我正在試驗一個數據庫索引文件的設計，該文件由固定大小的頁面組成，每個頁面都包含指向實際數據文件的（鍵，指針）記錄的集合。

基於頁面的設計使一切變得複雜。在我看來，最天真的做法是我應該保持記錄的排序順序（即像Page0記錄0 1 3 6，第1頁有記錄，7 8 12 15，...等物理排序），但我仍然無法使用例如在排序文件上進行二分搜索，因爲記錄不是順序的，而是駐留在頁面中（頁面標題，空閒空間等）。

任何人都可以提供一些關於如何使用二進制搜索尋找頁面完全排序索引文件的指導嗎？

編輯：基於頁面的btree實現對我來說太複雜了。儘管實現了上述簡單的方法，但我仍希望到達那裏。

Answer 1

我後來成功地做到了這一點。

閱讀中間的頁面。檢查它的第一個和最後一個記錄（或者如果頁面沒有在內部排序，則記錄具有最小/最高索引）。根據您的搜索鍵，向右或向左轉。循環。

Answer 2

B-tree from wikipedia

Answer 3

最簡單的事情通常是建立要使用，並只保留在內存中的索引。這樣，除了索引編制方式之外，您可以優化數據存儲和訪問。

當我實現類似的東西時，我將索引保存爲文件中的一個大塊，然後將數據作爲另一個更大的塊。