海量数据里，怎么飞快地找到一个

装信息也有形状，这个形状我们叫它容器。同样的数据，按一条线装、按一张表装、还是按分叉装，形状都不一样。容器不是随便挑的，要照着你想做的事来挑。想按顺序看，线好; 想按名字快速找，表好。而且一个容器不会把所有事都做得一样好。有的动作快，有的动作慢。所以挑对容器，就是快程序的开端。接下来几讲，我们会一个一个认识这些主要容器。

数组是一排带编号、紧挨着的格子的储物柜。报个编号就直接跳到那个格子，取得非常快。链表是散落各处的格子，每个都拿着写有下一个格子地址的纸条。所以要取第五个，得从头照着纸条一格一格走，慢一些。可往中间塞新格子时,只改两张纸条就行，很容易。数组反而要把后面的格子全往后推，挺麻烦。要快速访问就选数组，常往中间插入就选链表，你拿一个换另一个。

栈就是叠盘子。往上放，取的时候从最上面（最后放的那只）出来。所以后放的先出。队列就是排队。在后面站，取的时候从最前面（先来的那个）出来。所以先放的先出。用在哪里? 想把刚做的事倒回去或后退时，栈正合适，因为最后的动作先被取消，依次进行。想按到来顺序公平处理时，队列合适，像打印队列或叫号票一样。叠放是后先，排队是先先，记住这一句就够了。

数据库是一座有条理地存放信息的巨大仓库。通常会整理成表格，横着一行是一条记录，竖着一列是姓名、年龄这样的项目。新信息来了，就整齐地放进对应表格的对应列。它跟单纯写进文件不一样的地方有两点。一，能把许多信息一次性安全地存好。二，就算在几亿条里也能快速找到你要的。所以处理大量信息时，用数据库而不是文件。

数据库找东西最简单的办法是全表扫描：从头开始，一行行看到尾。数据少的时候够快。可一旦条数暴涨到几亿，要看的行也多了那么多，就越来越慢。所以我们提前建好索引。索引就像一份排好序的名牌清单，不用全部扫一遍，点一两下就直接跳到那个位置。同样的条数，索引比全表扫描用少得多的次数就找到答案。索引到底怎么建（索引、哈希、树）下面几讲接着讲。

哈希是看着值用计算定出格子号，然后直接往那个格子放、直接到那个格子找。它一步就到，不用一个个格子扫，所以很快。放进去和查找用的是同一个计算，所以放的格子和找的格子正好对上。也有短处。两个不同的值算出来一样，奔向同一个格子，就是冲突。那就在旁边处理，把它们一起塞进一个格子，或把一个挪到相邻的格子。一句话，哈希用计算定格子来一下找到，冲突就单独处理。

与其把数据排成一长行，不如摆成树的形状: 从一个根分出枝，一路往下。要找的值比当前格大，就走一边的枝; 小，就走另一边。这样每往下一层，要看的候选就少一半。所以哪怕几千个，也几步就找到。层数，也就是树的深度，决定速度。数据翻一倍，深度只多一层，所以再多也慢慢加深。这就跟从中间翻开词典、一半一半缩小一样。

树靠在枝杈间一半一半地缩小范围来查找时很快。可要是只按顺序加入值，枝杈不分叉，只往一边长长地长，就几乎成了一条直线，变慢。平衡树能防住这一点。加入或删除时一边变重了，它会自己重新安排节点的位置，这叫旋转。靠旋转让两边的深度总是差不多，那么数据再多，深度也长得很慢（log）。所以它总能保证在几步之内找到。我们只管加和删，树就自己守住平衡。

数据一多，从头扫就慢。索引就像书后的查找表，是提前建好的地图，让数据库直接跳到对的位置。它有两种。哈希索引一步就精准找到一个准确的值。树索引把值排好序，适合扫一个范围。不过它不是免费的。索引要占额外空间，数据一变，索引也得跟着更新。即便如此，用得好，查找会快得多。

图是把对象当作点、把对象之间的关系当作线来装的资料。把人当作点、把朋友关系当作线，连接就一目了然。从一个点顺着线走会出来邻居，再顺着邻居的线走就出来朋友的朋友。像这样沿着线扩散，就能把连成一片的整群都逛一遍。在推荐、找连接这类以关系为核心的事情上，用表得翻来翻去的，用图只要顺着线走就到了。一句话，点是对象，线是关系，再顺着邻居走，这就是图。

SQL 是为了从数据库取得想要的东西而发问的语言。只需说两件事。先挑出要看哪几列。一张表有好多列，你只留下想看的那几列。这叫 SELECT。再给出留下哪些行的条件。不是全部的行，只留下符合条件的行。这叫 WHERE。挑好的列和留下的行相遇，就出来一张正好符合条件的小结果表。拿一张表，用挑列和按条件筛行来问，答案就以表的形式回来，这就是 SQL 的基础。

数据通常分散在好几张表里。订单在订单表，人的信息在客户表，各放各的。只看一张表，答不了跨表的问题。所以我们找两张表都有的公共列，比如客户编号。把这一列值相同的行配成对，两张表就连成一行。这样连起来后，就能当作一张表来用，回答这笔订单是谁下的之类的问题。一句话，用公共列把行配对、连起分开的表，就是连接。

规范化是这样一种整理: 把一张表里反复出现的信息剥出来，分到单独一张表，再用共同的列重新接上。与其每笔订单都写顾客姓名，不如在顾客表里只写一次顾客，订单表里只留顾客编号。这样编号变了，只改顾客表里那一行就完事，不会出现不一致。也不会在一行行修改时漏掉某一散落的行。不过分得太细，每看一样东西就得把好几张表重新接回去，可能变慢。那时也会故意把常一起看的信息合到一张表里，这叫反规范化。归根结底，规范化就是把重复剥出来分开、用关系接上，分得太细时再合回去的一种平衡。

事务是把几次改动当成一个整体来处理，让它们要么全成、要么全不成的办法。像转账那样扣和加是一对时，两件都完成了才真正生效。中途要是断电或哪里对不上，它不会只留一半，而是把整件事退回到之前的状态。这叫回滚。还有，几个人同时想改同一笔余额时，它一个一个轮着处理，让大家不会互相覆盖。一拥而上的乱局变成了排队办理。一句话: 要么全做要么全不做、出岔就回滚、同时也不乱。这三样就是事务。

缓存是把常用数据的副本放在近处的办法。远处的存储慢，因为来回的路长。可副本放近处，往后就走一条短路马上取出。要找的东西在缓存里，就叫命中，快快取出。不在，就叫未命中，跑到远处取回来，再把那份副本留在缓存里。所以下次就成了命中。也有短处。原件变了，缓存里还留着旧副本，可能给出旧值。这叫缓存过时。所以时不时把缓存重新填一遍，或过一段时间就扔掉，挡住旧值。一句话，把副本放近处，命中就快，原件一变就把缓存刷新，这就是缓存。

压缩是把同样的信息装进更小空间的本事。有两手。一是减少重复。像 AAAA 这样同样的连成串，写成 A 四次就短了。二是给常出现的小段一个短代码。把长段换成短符号，整体就小了。而且压缩出来的，一还原就和原件一模一样，因为什么都没扔。这叫无损。压得越狠就越小，但压和解都更费时间。所以要在多小和多快之间权衡着选。一句话，减少重复、给短代码把它装小，而还原回来还是原件，这就是压缩。

数据大到一台扛不住时，就把它切成块分到好几台装。这叫分布(分散)。每台只持有整体的一部分，凑起来就能装下很大的数据。而且为了一台坏了也不出事，把同样的数据复制到好几台。这叫复制。分着装的分布和复制保存的复制，是不同的概念。分布是把货切开分摊，复制是把同样的货放在好几处。为了这种巨大又快速的处理，把严格的表格形式放松的容器，叫做 NoSQL。它就像把哈希那种用键直接放和找值的容器养大，于是成了通向下一个领域人工智能所处理的海量数据的桥。