怎么工作 数据库 怎么查找数据

一开始一行行地扫

上一课说过，数据库把信息按表的样子一行行整理好。在里面找东西，最简单的方法就是从最上面一行开始，一行行看是否对得上，往下走。
碰到对得上的一行就停下。像这样从头到尾依次扫一遍，叫作全表扫描。

点一下想找的值。它会从最上面一格格往下扫，并数一数到达之前看了几次。

靠上的值，看几次就找到了。靠下的值，得把上面的全都走过才到。要找的值在最后面的话，结果就是每一行都看了一遍。
行数少的时候，这样也够快，没什么问题。那么，行数变得非常多时会怎样？

数据一多，扫起来就慢

真正的数据库，行数多得惊人，几百万行、几亿行都很常见。用全表扫描找最后一个值，得把所有行都看一遍。
所以行数翻一倍，要看的次数也翻一倍。行数增加多少，查找的成本就跟着增加多少，这就是全表扫描的极限。

点一下增加记录数。用全表扫描找最后一个值所需的次数，会在柱子上急剧增长。

记录数越多，柱子就越长。在小表里不值一提的事，到了大表里就成了沉重的负担。
只要每次都从头扫到尾，这个成本就避免不了。那么，有没有不用扫、直接到那个位置的办法？幸好，有个聪明的办法。

建好索引，直接跳过去

想想书后面附的索引。词语按顺序排好，旁边写着在第几页。不用从头翻整本书，在索引里找到那个词，就能直接翻到那一页。
数据库也能事先建好这样的目录，这叫作索引。

在排好序的索引里点一个名牌。不用扫表，一两步就直接跳到那一行。

用了索引，不扫表也直接到了。就算是最后面的值，一两步也就够了。
秘诀在于索引事先排得整整齐齐。在排好序的目录里，可以先看中间，判断要找的值在前一半还是后一半，把另一半扔掉，再重复这一步。这样一来，就算在一百万个里，二十来步也能找到。

比较全表扫描和索引

把两种方法并排放着，在相同的记录数下比一比。全表扫描要看的次数和行数一样多。索引利用排好的顺序，用很少的次数就完事了。
记录数一样，结果却天差地别。所以，对经常要查的项目，建好索引很划算。

选好记录数，再点两边的查找。并排比较全表扫描和索引找同一个值各用了几次。

记录数越多，全表扫描的柱子就越长，索引的柱子却几乎不变。正是这个差距，让数据越大，索引就越显身手。
当然，索引也不是免费的。它需要额外的空间，而且每进来一行新数据，索引也得跟着改，保持排好的顺序。不过，对经常要查的项目来说，还是很值得。

小结

用一句话概括：最简单的查找是全表扫描，也就是从头一行行全部扫一遍。数据少时，这样就够了。
可数据多到几亿条时，扫描的成本就会急剧上升。所以要事先建好索引，一两步就直接跳过去。记录数一样，索引要看的次数少得多。

依次点要点回顾一下。（一行行扫 → 数据暴增 → 用索引跳过去 → 全表扫描 vs 索引）

现在你知道数据库为什么要从全表扫描转向索引了。那么，索引实际上是怎么建的呢？
除了排好序的目录，还有哈希和树这样的方法。下一课先看看哈希：凭一个名牌就能直接算出位置。