如何設計索引表？

我正試圖設計一個帶索引的數據庫表的內存模擬。我實現了一個整潔的DSL來查詢表，看起來像這樣如何設計索引表？

table.select do 
    age > 44 
    name == "Adam" 
end

，併產生了一堆Condition類的實例，如EqCondition，GteCondition等嗯，這是比較容易的部分。 Table檢查這些條件並選擇適當的索引來執行查詢。我堅持的是什麼樣的參數Index#select接受？如果它接受與表格的選擇方法相同的參數，它有兩次做同樣的工作。假設我們需要選擇年齡大於25的每個人。首先，Table類確定有一個可以使用的（年齡，名稱）索引。然後，索引應該確定這是一個範圍查詢，只涉及部分密鑰並相應地執行它。

我在問一些關於如何正確設計的想法（或許是在真實數據庫中做了一些簡單的版本）？

PS。這是Ruby，但我認爲它不相關。在Java/C＃它會看起來像table.select(new GtCondition("age", 44), new EqCondition("name", "Adam"))

來源

2012-06-23 synapse

考慮該指數對DBMS的意圖是：

減少IO
優化加入
作爲一個副作用：以幫助執行一些約束條件（如PK/FK）

當您使用內存中的所有數據時，有時只是進行線性掃描就足夠了:)

如果您有疑問，請使用一個分析器...並且您會看到讓1000個元素的內存集合很小。如果你的代碼沒有任何JOIN，那麼使用簡單的collection.filter(condition)就足夠了。

但它如何在數據庫上工作？這裏有一個大概的想法：

首先將SELECT表達式轉換爲「規範樹」。

PROJECT(A.NAME, B.SOMETHING) 
      | 
FILTER(A.NAME=B.NAME, B.OTHER>10) 
      | 
    CARTESIAN PRODUCT 
    |    | 
PROJECT(A.NAME)  PROJECT(B.OTHER,B.SOMETHING)

從這個表達式樹有一些代數規則，而不是可以應用於：例如SELECT A.NAME,B.SOMETHING FROM A, B WHERE A.NAME=B.NAME AND B.OTHER > 10可以作爲代表。我們的目標是避免笛卡爾積，因爲是非常低效的：
```
PROJECT(A.NAME, B.SOMETHING) 
      | 
    EQ-JOIN A,B USING NAME 
    |    | 
PROJECT(A.NAME)  FILTER B.OTHER>10  
        | 
     PROJECT(B.OTHER,B.SOMETHING) 
```

DBMS引擎分析樹和數據庫（如實物指標，記錄數）的元數據，並改變樹優化它（這是查詢計劃）。例如，如果B被其他排序，最好先做好FILTER：

PROJECT(A.NAME, B.SOMETHING) 
      | 
    EQ-JOIN A,B USING NAME (NESTED LOOP JOIN) 
    |    | 
PROJECT(A.NAME) PROJECT(B.OTHER,B.SOMETHING) 
        | 
        FILTER B.OTHER>10 (UNSING INDEX ON OTHER)

不過，如果你這樣做，你必須的B內存的緩衝區，也許你失去的索引信息，你可以不再次使用索引（並且連接的唯一選項是使用嵌套循環）。所以引擎可以檢測到，並選擇更好的計劃，也許：
```
PROJECT(A.NAME, B.SOMETHING) 
      | 
    FILTER B.OTHER>10 
      | 
    EQ-JOIN A,B USING NAME (HASH INDEX EQ-JOIN) 
    |    | 
PROJECT(A.NAME) PROJECT(B.OTHER,B.SOMETHING) 
```

一旦該計劃已準備就緒。它就像一個程序：引擎盲目追隨它。

如何使用它，爲內存引擎？您可以檢測EQUI JOINS，並將「計劃」轉換爲使用散列表。也許你可以使用平衡樹來實現其他類型的索引，但是可能並沒有太多幫助：內存中的O（n）算法很好，O（nxm）順序是你必須避免的順序，這意味着避免笛卡爾產品。

，你可以做一個啓發是：（即名稱==「亞當」）

檢測到所有相同的過濾器，如果你的表有該領域的散列索引...首先使用它，如：table.findUsingHash('name', 'Adam')。
然後，只需掃描和過濾結果（即年齡> 44）：filter(table.findUsingHash('name', 'Adam'), function (e) { return e.age > 44 })

的想法是第一做最有選擇性的指數，所以爲O（n）掃描具有小的N。

注：我不會做很長時間以來這種DBMS的東西。所以我的樹圖可能包含一些錯誤......請參閱DBMS書（如this）以獲得更好的源代碼。

來源

2013-01-18 01:21:31 Diego

如何設計索引表？

回答

相關問題