数据库怎么在里面找到东西

一开始它一行行扫着找

前面我们学过，数据库
按表格的样子一行行整理。
在里面找东西，
最简单的办法是这个。
从最上面一行往下，
一行一行地看对不对。
碰到对得上的那行就停。
这样从头看到尾，
叫做全表扫描。

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

靠上面的值，
看几次很快就找到了。
可靠下面的值，
要把上面全过一遍才到。
要找的值在最末尾，
那等于把每一行都看了。
行数少的时候，这样
也够快，没什么问题。
那要是行变得很多呢?

数据暴涨，扫描就变慢

真正的数据库，
行数大得惊人。
几百万、几亿行都很常见。
要找最末尾的值，全表扫描
必须把那些行每一个都看一遍。
所以行数翻一倍，
要看的次数也翻一倍。
行多了多少，
找的代价就跟着多多少。
这就是全表扫描的极限。

点击把条数变大。用全表扫描找最末尾值所需的次数，会以柱状陡然增长。

条数越大，
柱子蹭蹭往上长。
小表里不算事的，
到大表里就成了重负担。
只要每次从头扫到尾，
这个代价就躲不掉。
那有没有不扫描、
直接到那个位置的办法呢?
好在有个聪明的办法。

建个索引，直接跳过去

想想书后面的索引。
词条按顺序排好，
旁边写着第几页。
不用从头翻整本书，
在索引里指着词条，
直接翻到那一页。
数据库也能把这样的清单
提前建好。
它就叫索引。

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

一指索引，
没扫表就直接到了。
哪怕是最末尾的值，
点一两下也就够了。
秘诀在于索引提前
整整齐齐排好序。
排好序，就能很快缩小
范围、指到大概在哪。
看全部的必要没有了。

比比全表扫描和索引

把两种办法摆一块儿，
在同样的条数下比一比。
全表扫描要看的次数，
跟行数一样多。
索引借助排序，
用很少的次数就完事。
条数一样，结果
却是天壤之别。
所以常找的数据，
建好索引才划算。

选个条数，把两边的查找都点一下。把全表扫描和索引找同一个值所用的次数并排比一比。

条数越大，
全表扫描的柱子蹭蹭往上长，
索引的柱子却几乎不动。
正是这个差距，
让数据越大、索引越出彩。
当然索引也不是白来的。
提前建好、保持排序
是要花功夫的。
但要是常找，那就值这个价。

来理一理

归成一句话，是这样。
最简单的查找是全表扫描，
也就是从头一行行全看一遍。
数据少，这就够了。
可一旦暴涨到几亿条，
扫描的代价就陡然增长。
所以提前建好索引，
点一两下就直接跳过去。
同样的条数，索引看得少得多。

依次点要点回顾一下。(一行行扫 → 数据暴涨 → 用索引跳 → 全表扫描 vs 索引)

现在你知道数据库
为什么从全表扫描
转向索引了。
可那个索引
实际上是怎么建的呢?
除了排好序的清单，
还有哈希和树这样的办法。
那些聪明的索引结构，
下面几讲一个个跟着看。