数据库索引

Question

您如何向某人解释索引在明智地使用时如何提高数据库的性能？我正在寻找一个好的、清晰的解释，因为它在书中太复杂了。

Answer 1

请耐心等待，这需要一段时间 :-)。

想象一个简单的地址簿，当新 friend 或同事到达时，您只需在末尾添加记录(下一个条目将在 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 个像我这样的 friend 怎么办(我真是个极客，我只按 2 的幂分配 friend - 我实际上有 2,024 个，但其中 1,000 个处于不确定状态unitl 我可以再凑齐 24 个 :-)。

为了找到一个特定的 friend ，您平均需要扫描 512 个条目(其中一半正在使用)。这很乏味。最坏的情况是扫描全部 1,024 个以找到您添加的最后一个人。

现在让我们添加该索引。每次你添加一个新 friend /同事(或者如果他们给你带来太多麻烦就删除他们)，你更新这个索引，它只存储按排序顺序排列的名字以及完整条目的行号(你地址中的索引页这本书很神奇，它会自动排序您在其中写的所有内容)。

上面的迷你列表的索引是:

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

名称和行号占用的空间比完整条目少，但最重要的方面是这一点。

为了找到一个条目，您只需扫描，最坏的情况下，10 个条目 (log₂1024)。首先，检查索引号 512。如果要查找的名称大于该名称，则只需查看条目 513-1024。如果小于，您现在只对条目 1-511 感兴趣。无论哪种情况，您都会立即将搜索空间减少一半。

使用原来的方法，您只能丢弃您检查的那个，因为您没有可用的订购信息。

所以搜索空间的大小是这样的(我实际上对索引方法使用了 2 的幂，但它比那稍微好一点):

+-----------+----------------+------------+
| 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 行。您可以直接那里没有进一步的搜索。

因此，以多一点存储空间和一些时间维护索引为代价，您大大提高了搜索速度。这也是索引在数据库中的作用。