忍受我,这需要一段时间:-).
想想一个简单的地址簿,你只需在新朋友或同事到达时添加记录(下一个条目将在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个,但是其中有1000个被关押在我们的另外24个人:-).
为了找到一个特定的朋友,你必须平均扫描512个条目(使用中的一半).这很乏味.最糟糕的情况是扫描所有1,024个,找到你添加的最后一个人.
现在让我们添加该索引.每次添加新朋友/同事(或者如果他们导致你太麻烦就删除它们),你更新这个索引,它只按排序顺序存储名称以及完整条目的行号(地址中的索引页面)书是神奇的,并自动排序你写的所有内容).
以上迷你列表的索引是:
1. Allan Brown, 3
2. Allan Brown, 4
3. Greg Jones, 2
4. Bob Smith, 1
名称和行号比完整条目占用的空间更少,但最重要的方面是这个.
为了找到一个条目,您只需扫描最坏情况下的10个条目(log 2 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行.您可以直接在那里直接进入搜索.
因此,以更多存储空间和维护索引的时间为代价,您大大提高了搜索速度.这就是索引在数据库中的作用.