數據庫索引

9

忍受着我，這將需要一段時間:-)。

一個簡單的地址簿，你只需添加上新的朋友或同事到達結束記錄的認爲（下一個條目會去5）：

1. Bob Smith, 7 Station St, Wotahole, NJ 
2. Greg Jones, 3 Railway Pde, Boot Hill, KA 
3. Allan Brown, 27 Carriage Court, Washington, DC (home) 
4. Allan Brown, 1066 Hastings Street, Washington, DC (work) 
5.

現在，你需要找人的地址。沒問題，我聽到你說，只是掃描名單尋找名稱，然後讀取地址。

現在，如果你非常受歡迎以至於你有1,024位像我這樣的朋友（我是這樣一個極客，我只分配兩個冪級別的朋友 - 我實際上有2,024個，但其中有1,000個正在我可以再一次找到24個:-)。

爲了找到一個特定的朋友，你必須平均掃描512個條目（使用中的一半）。這很乏味。最糟糕的情況是掃描全部1,024個，找到您添加的最後一個人。

現在讓我們添加該索引。每當你添加一個新朋友/同事（或者如果他們導致你太多麻煩，刪除他們），你更新這個索引，只存儲排序順序的名字以及完整條目的行號（地址中的索引頁書是魔法並自動分類你寫的所有內容）。

用於輸出迷你列表索引上面會：

1. Allan Brown, 3 
2. Allan Brown, 4 
3. Greg Jones, 2 
4. Bob Smith, 1

的名稱和行號佔用較少的空間比全項，但最重要的方面是這樣的。

爲了找到一個條目，您只需掃描，最壞的情況下，10個條目（日誌 1024）。首先，檢查索引號碼512.如果您要查找的名稱大於該名稱，則只需查看條目513-1024。如果少了，你現在只對條目1-511感興趣。無論哪種情況，您都會立即將搜索空間減半。

使用原始方法，您只能丟棄您檢查的方法，因爲您沒有可用的訂購信息。

所以搜索空間的大小是這樣的（我實際使用的兩個大國的索引方法，但它比這稍好）：

+-----------+----------------+------------+ 
| Iteration | Indexed method | Old method | 
+-----------+----------------+------------+ 
| 0  | 1024   | 1024 | 
| 1  | 512   | 1023 | 
| 2  | 256   | 1022 | 
| 3  | 128   | 1021 | 
| 4  |  64   | 1020 | 
| 5  |  32   | 1019 | 
| 6  |  16   | 1018 | 
| 7  |  8   | 1017 | 
| 8  |  4   | 1016 | 
| 9  |  2   | 1015 | 
| 10  |  1   | 1014 | 
+-----------+----------------+------------+

一旦你找到了指數，從中提取行號，並且由於您知道每頁有16個條目，因此條目號275（例如）位於第18頁的第4行。您可以直接到那裏而無需進一步搜索。

因此，以更多的存儲空間和一些維護索引爲代價，大大提高了搜索速度。這也是索引在數據庫中的作用。

來源

2009-04-16 05:41:04 paxdiablo

3

我會使用經典解釋：

索引提供一個有序和迅速的方法來遍歷一個數據集。

典型的例子是電話本 - 按字母順序按名稱INDEXED - 這可以加快您的訪問速度，因爲您可以直接使用索引方法直接找到想要查找的名稱。

數據庫真的沒有什麼不同 - 您不必爲僱員的EmployeeId = 123掃描整個表。您只需掃描索引，按已知順序存儲，最終表現會更好。

來源

2009-04-16 04:37:27

+0