之前的 17 讲，我们从小处着眼，介绍了离散数学中最常用的一些知识点。我讲到了很多数据结构、编程语句和基础性算法。这些知识点看似是孤立的，但是内部其实有很多联系。今天这一节，我们就来总结一下前面讲过的内容，把之前讲过的内容串联起来。

数据结构

首先，我们来看一些基本的数据结构，你可别小看这些数据结构，它们其实就是一个个解决问题的“模型”**。**有了这些模型，你就能把一个个具体的问题抽象化，然后再来解决。

我们从最简单的数据结构数组开始说。自从你开始接触计算机编程，数组一定是你经常使用的数据结构。它的特点你应该很清楚。数组可以通过下标，直接定位到所需的数据，因此数组特别适合快速地随机访问。它常常和循环语句相结合，来实现迭代法，例如二分查找、斐波那契数列等等。

另外，我们将要在“线性代数篇”介绍的矩阵，也可以使用多维数组来表示。不过，数组只对稠密的数列更有效。如果数列非常稀疏，那么很多数组的元素就是无效值，浪费了存储空间。此外，数组中元素的插入和删除也比较麻烦，需要进行数据的批量移动。

那么对于稀疏的数列而言，什么样的数据结构更有效呢？答案是链表。链表中的结点存储了数据，而链表结点之间的相连关系，在 C 和 C++ 语言中是通过指针来实现的，而在 Java 语言中是通过对象引用来实现的。

链表的特点是不能通过下标来直接访问数据，而是必须按照存储的结构逐个读取。这样做的优势在于，不必事先规定数据的数量，也不再需要保存无效的值，表示稀疏的数列时可以更有效的利用存储空间，同时也利于数据的动态插入和删除。但是，相对于数组而言，链表无法支持快速地随机访问，进行读写操作时就更耗时。

和数组一样，链表也可以是多维的。对于非常稀疏的矩阵，也可以用多维链表的结构来表达。此外，在链表结构中，点和点之间的连接，分别体现了图论中的顶点和边。因此，我们还可以使用指针、对象引用等来表示图结构中的顶点和边。常见的图模型，例如多叉树、无向图和有向图等，都可以用指针或引用来实现。

在数组和链表这些基础的数据结构之上，我们可以构建更复杂的数据结构，比如哈希表、队列和栈等等。这些数据结构，提供了逻辑更复杂的模型，可以通过数组、链表或两者的结合来实现。

第 2 讲我提到了哈希的概念，而哈希表就可以通过数组和链表来构造。在很多编程语言中，哈希表的实现采用的是链地址哈希表。这种方法的主要思想是，先分配一个很大的数组空间，而数组中的每一个元素都是一个链表的头部。随后，我们就可以根据哈希函数算出的哈希值（也叫哈希的 key），找到数组的某个元素及对应的链表，然后把数据添加到这个链表中。

之所以要这样设计，是因为存在哈希冲突。对于不同的数据，哈希函数可能产生相同的哈希值，这就是哈希冲突。如果数组的每个元素都只能存放一个数据，那就无法解决冲突。如果每个元素对应了一个链表，那么当发生冲突的时候，我们就可以把多个数据添加到同一个链表中。可是，把多个数据存放在一个链表，就代表访问效率不高。所以，我们要尽量找到一个合理的哈希函数，减少冲突发生的机会，提升检索的效率。

在第 2 讲中，我还提到了使用求余相关的操作来实现哈希函数。我这里举个例子。你可以看我画的这幅图。

我们把对 100 求余作为哈希函数。因此数组的长度是 100。对于每一个数字，通过它对 100 求余，确定它在数组中的位置。如果多个数字的求余结果一样，就产生冲突，使用链表来解决。我们可以看到，表中位置 98 的链表没有冲突，而 0、1、2、3 和 99 位置的链表都有冲突。

说完了哈希，我们来看看栈这种数据结构。我在介绍树的深度优先搜索时讲到栈。它是先进后出的。在我们进行函数递归的时候，函数调用和返回的顺序，也是先进后出，所以，栈体现了递归的思想，可以实现基于递归的编程。实际上，计算机系统里的函数递归，在内部也是通过栈来实现的。虽然直接通过栈来实现递归不如函数递归调用那么直观，但是，由于栈可以避免过多的中间变量，它可以节省内存空间的使用。

我在介绍广度优先搜索策略时，谈到了队列。队列和栈最大的不同在于，它是一种先进先出的数据结构，先进入队列的元素会优先得到处理。队列模拟了日常生活中人们排队的现象，其思想已经延伸到很多大型的数据系统中，例如消息队列。

在消息系统中，生产者会源源不断地推送新的数据，而消费者会对这些消息进行处理。可是，有时消费者的处理速度会慢于生产者推送的速度，这会带来很多复杂的后续问题，因此我们可以通过队列实现消息的缓冲。新产生的数据会先进入队列，直到消费者处理它。经过这样的异步处理，消息的队列实现了生产者和消费者的松耦合，对消费者起到了保护作用，使它不容易被数据洪流冲垮。

比哈希表，队列和栈更为复杂的数据结构是基于图论中的各种模型，例如各种二叉树、多叉树、有向图和无向图等等。通常，这些模型表示了顶点和顶点之间的稀疏关系，所以它们常常是基于指针或者对象引用来实现的。我在讲前缀树、社交关系图和交通地图的案例中，都使用了这些模型。另外，树模型中的多叉树、特别是二叉树体现了递归的思想。之前的递归编程的案例中的图示也可以对应到多叉树的表示。

编程语句

在你刚刚开始学习编程的时候，肯定接触过条件语句、循环语句和函数调用这些基本的语句。

条件语句的一个关键元素是布尔表达式。它其实体现了逻辑代数中逻辑和集合的概念。逻辑代数，也被称为布尔代数，主要包括了逻辑表达式及其相关的逻辑运算，可以帮助我们消除自然语言所带来的歧义，并严格、准确地描述事物。在编程语言中，我们把逻辑表达式和控制语言结合起来，比如 Java 语言的 If 语句：

1
2

if(表达式) {函数体 1} else {函数体 2}：若表达式为真，执行函数体 1，否则执行函数体 2。
复制代码

当然，逻辑代数在计算机中的应用，远不止条件语句。例如 SQL 语言中的 Select 语句和布尔检索模型。Select 是 SQL 查询语言中十分常用的语句。这个语句将根据指定的逻辑表达式，在一个数据库中进行查询并返回结果，而返回的结果就是满足条件的记录之集合。类似地，布尔检索模型利用逻辑表达式，确定哪些文档满足检索的条件并把它们作为结果返回。

这里顺便提一下，除了条件语句中的布尔表达式，逻辑代数还体现在编程中的其他地方。例如，SQL 语言中的 Join 操作。Join 有多种类型，每种类型其实都对应了一种集合的操作。

• 内连接（inner join）：假设被连接的两张数据表分别是左表和右表，那么内连接查询能将左表和右表中能关联起来的数据连接后返回，返回的结果就是两个表中所有相匹配的数据。如果认为左表是集合 A，右表是集合 B，那么从集合的角度来说，内连接产生的结果是 A、B 两个集合的交集。
• 外连接（outer join）：外连接可以保留左表，右表或全部表。根据这些行为的不同，可分为左外连接、右外连接和全连接。无论哪一种，都是对应于不同的集合操作。

循环语句可以让我们进行有规律性的重复性操作，直到满足某个条件。这和迭代法中反复修改某个值的操作非常一致。所以循环常用于迭代法的实现，例如二分或者牛顿法求解方程的根。在之前的迭代法讲解中，我经常使用循环来实现编码。另外，循环语句也会经常和布尔表达式相结合。嵌套的多层循环，常常用于比较多个元素的大小，或者计算多个元素之间的相似度等等，这也体现了排列组合的思想。

至于函数的调用，一个函数既可以调用自己，也可以调用其他不同的函数。如果不断地调用自己，这就体现了递归的思想。同时，函数的递归调用也可以体现排列组合的思想。

基础算法

在前面的专栏中，我介绍了一些常见算法及其对应的数学思想。而这些思想，在算法中的体现无处不在。

介绍分治思想的时候，我谈及了 MapReduce 的数据切分。在分布式系统中，除了数据切分，我们还要经常处理的问题是：如何确定服务请求被分配到哪台机器上？这就引出了负载均衡算法。

常见的包括轮询或者源地址哈希算法。轮询算法把请求按顺序轮流地分配到后端服务器上，它并不关心每台服务器当前的负载。如果我们对每个请求标上一个自动增加的 ID，我们可以认为轮询算法是对请求的 ID 进行求余操作（或者是求余的哈希函数），被除数就是可用服务器的数量，余数就是接受请求的服务器 ID。而源地址哈希进一步扩展了这个思想，扩展主要体现在：

• 它可以对请求的 IP 或其他唯一标识进行哈希，而不一定是请求的 ID；
• 哈希函数的变换操作不一定是求余。

不管是对何种数据进行哈希变换，也不管是何种哈希函数，只要能为每个请求确定哈希 key 之后，我们就能为它查找对应的服务器。

另外，在第 9 节中，我谈到了字符串的编辑距离，但是没有涉及字符串匹配的算法。知名的 RK（Rabin-Karp）匹配算法，在暴力匹配（Brute Force）基础之上，充分利用了迭代法和哈希，提升了算法的效率。

首先，RK 算法可以根据两个字符串哈希后的值。来判断它们是不是相同。如果哈希值不同，则两个字符串肯定不同，不用再比较；此外，RK 算法中的哈希设计非常巧妙，让相邻两个子字符串的哈希值产生了固定的联系，让我们可以通过前一个子串的哈希值，推导出后一个子串的哈希值，这样就能使用迭代法来计算每个子串的哈希值，大大减少了用于哈希函数的计算。

除了分治和动态规划，另一个常用的算法思想是回溯。我们可以使用回溯来解决的问题包括八皇后和 0/1 背包等等。回溯实际上体现了递归和排列的思想。不过，它对搜索空间做了一些优化，提前排除了不可能的情况，提升了算法整体的效率。当然，既然回溯体现了递归的思想，也可以把整个搜索状态表示成树，而对结果的搜索就是树的深度优先遍历。

在前两节讲述算法复杂度分析的时候，我已经从数学的角度出发，总结了几个常用的法则，包括四则运算、主次分明、齐头并进、排列组合、一图千言和时空互换。这些法则体现了数学中的运算优先级、数量级、多元变量、图论等思想。这些我们上两节刚刚讲过，我就不多说了，你可以参考之前的内容快速复习一下。

小结

这一讲，我对常用的数据结构、编程语句和算法中所体现的数学思想，做了一个大体的梳理。可以看到，不同的数据结构，都是在编程中运用数学思维的产物。每种数据结构都有自身的特点，有利于我们更方便地实现某种特定的数学模型。

从数据结构的角度来看，最基本的数组遍历体现了迭代的思想，而链表和树的结构可用于刻画图论中的模型。栈的先进后出、以及队列的先进先出，分别适用于图的深度优先和广度优先遍历。哈希表则充分利用了哈希函数的特点，大幅降低了查询的时间复杂度。

当然，仅仅使用数据结构来存储数据还不够，我们还需要操作这些数据。为了实现操作的流程，条件语句使用了布尔代数来控制编程逻辑，循环和函数嵌套使用迭代、递归和排列组合等思想来实现更精细的数学模型。

但是，有时候我们面对的问题太复杂了，除了数据结构和基本的编程语句，我们还需要发明一些算法。为了提升算法的效率，我们需要对其进行复杂度分析。通常，这些算法中的数学思想就更为明显，因为它们都是为了解决特定的问题，根据特定的数学模型而设计的。

有的时候，某个算法会体现多种数学思想，例如 RK 字符串匹配算法，同时使用了迭代法和哈希。此外，多种数学思维可能都是相通的。比如，递归的思想、排列的结果、二进制数的枚举都可以用树的结构来图示化，因此我们可以通过树来理解。

所以，在平时学习编程的时候，你可以多从数学的角度出发，思考其背后的数学模型。这样不仅有利于你对现有知识的融会贯通，还可以帮助你优化数据结构和算法。

上一节，我给你讲了要怎么理解平均负载（ Load Average），并用三个案例展示了不同场景下平均负载升高的分析方法。这其中，多个进程竞争 CPU 就是一个经常被我们忽视的问题。

我想你一定很好奇，进程在竞争 CPU 的时候并没有真正运行，为什么还会导致系统的负载升高呢？看到今天的主题，你应该已经猜到了，CPU 上下文切换就是罪魁祸首。

我们都知道，Linux 是一个多任务操作系统，它支持远大于 CPU 数量的任务同时运行。当然，这些任务实际上并不是真的在同时运行，而是因为系统在很短的时间内，将 CPU 轮流分配给它们，造成多任务同时运行的错觉。

而在每个任务运行前，CPU 都需要知道任务从哪里加载、又从哪里开始运行，也就是说，需要系统事先帮它设置好 CPU 寄存器和程序计数器（Program Counter，PC）。

CPU 寄存器，是 CPU 内置的容量小、但速度极快的内存。而程序计数器，则是用来存储 CPU 正在执行的指令位置、或者即将执行的下一条指令位置。它们都是 CPU 在运行任何任务前，必须的依赖环境，因此也被叫做 CPU 上下文。

知道了什么是 CPU 上下文，我想你也很容易理解 CPU 上下文切换。CPU 上下文切换，就是先把前一个任务的 CPU 上下文（也就是 CPU 寄存器和程序计数器）保存起来，然后加载新任务的上下文到这些寄存器和程序计数器，最后再跳转到程序计数器所指的新位置，运行新任务。

而这些保存下来的上下文，会存储在系统内核中，并在任务重新调度执行时再次加载进来。这样就能保证任务原来的状态不受影响，让任务看起来还是连续运行。

我猜肯定会有人说，CPU 上下文切换无非就是更新了 CPU 寄存器的值嘛，但这些寄存器，本身就是为了快速运行任务而设计的，为什么会影响系统的 CPU 性能呢？

在回答这个问题前，不知道你有没有想过，操作系统管理的这些“任务”到底是什么呢？

也许你会说，任务就是进程，或者说任务就是线程。是的，进程和线程正是最常见的任务。但是除此之外，还有没有其他的任务呢？

不要忘了，硬件通过触发信号，会导致中断处理程序的调用，也是一种常见的任务。

所以，根据任务的不同，CPU 的上下文切换就可以分为几个不同的场景，也就是进程上下文切换、线程上下文切换以及中断上下文切换。

这节课我就带你来看看，怎么理解这几个不同的上下文切换，以及它们为什么会引发 CPU 性能相关问题。

进程上下文切换

Linux 按照特权等级，把进程的运行空间分为内核空间和用户空间，分别对应着下图中， CPU 特权等级的 Ring 0 和 Ring 3。

• 内核空间（Ring 0）具有最高权限，可以直接访问所有资源；
• 用户空间（Ring 3）只能访问受限资源，不能直接访问内存等硬件设备，必须通过系统调用陷入到内核中，才能访问这些特权资源。

换个角度看，也就是说，进程既可以在用户空间运行，又可以在内核空间中运行。进程在用户空间运行时，被称为进程的用户态，而陷入内核空间的时候，被称为进程的内核态。

从用户态到内核态的转变，需要通过系统调用来完成。比如，当我们查看文件内容时，就需要多次系统调用来完成：首先调用 open() 打开文件，然后调用 read() 读取文件内容，并调用 write() 将内容写到标准输出，最后再调用 close() 关闭文件。

那么，系统调用的过程有没有发生 CPU 上下文的切换呢？答案自然是肯定的。

CPU 寄存器里原来用户态的指令位置，需要先保存起来。接着，为了执行内核态代码，CPU 寄存器需要更新为内核态指令的新位置。最后才是跳转到内核态运行内核任务。

而系统调用结束后，CPU 寄存器需要恢复原来保存的用户态，然后再切换到用户空间，继续运行进程。所以，一次系统调用的过程，其实是发生了两次 CPU 上下文切换。

不过，需要注意的是，系统调用过程中，并不会涉及到虚拟内存等进程用户态的资源，也不会切换进程。这跟我们通常所说的进程上下文切换是不一样的：

• 进程上下文切换，是指从一个进程切换到另一个进程运行。
• 而系统调用过程中一直是同一个进程在运行。

所以，系统调用过程通常称为特权模式切换，而不是上下文切换。但实际上，系统调用过程中，CPU 的上下文切换还是无法避免的。

那么，进程上下文切换跟系统调用又有什么区别呢？

首先，你需要知道，进程是由内核来管理和调度的，进程的切换只能发生在内核态。所以，进程的上下文不仅包括了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的状态。

因此，进程的上下文切换就比系统调用时多了一步：在保存当前进程的内核状态和 CPU 寄存器之前，需要先把该进程的虚拟内存、栈等保存下来；而加载了下一进程的内核态后，还需要刷新进程的虚拟内存和用户栈。

如下图所示，保存上下文和恢复上下文的过程并不是“免费”的，需要内核在 CPU 上运行才能完成。

根据 Tsuna 的测试报告，每次上下文切换都需要几十纳秒到数微秒的 CPU 时间。这个时间还是相当可观的，特别是在进程上下文切换次数较多的情况下，很容易导致 CPU 将大量时间耗费在寄存器、内核栈以及虚拟内存等资源的保存和恢复上，进而大大缩短了真正运行进程的时间。这也正是上一节中我们所讲的，导致平均负载升高的一个重要因素。

另外，我们知道， Linux 通过 TLB（Translation Lookaside Buffer）来管理虚拟内存到物理内存的映射关系。当虚拟内存更新后，TLB 也需要刷新，内存的访问也会随之变慢。特别是在多处理器系统上，缓存是被多个处理器共享的，刷新缓存不仅会影响当前处理器的进程，还会影响共享缓存的其他处理器的进程。

知道了进程上下文切换潜在的性能问题后，我们再来看，究竟什么时候会切换进程上下文。

显然，进程切换时才需要切换上下文，换句话说，只有在进程调度的时候，才需要切换上下文。Linux 为每个 CPU 都维护了一个就绪队列，将活跃进程（即正在运行和正在等待 CPU 的进程）按照优先级和等待 CPU 的时间排序，然后选择最需要 CPU 的进程，也就是优先级最高和等待 CPU 时间最长的进程来运行。

那么，进程在什么时候才会被调度到 CPU 上运行呢？

最容易想到的一个时机，就是进程执行完终止了，它之前使用的 CPU 会释放出来，这个时候再从就绪队列里，拿一个新的进程过来运行。其实还有很多其他场景，也会触发进程调度，在这里我给你逐个梳理下。

其一，为了保证所有进程可以得到公平调度，CPU 时间被划分为一段段的时间片，这些时间片再被轮流分配给各个进程。这样，当某个进程的时间片耗尽了，就会被系统挂起，切换到其它正在等待 CPU 的进程运行。

其二，进程在系统资源不足（比如内存不足）时，要等到资源满足后才可以运行，这个时候进程也会被挂起，并由系统调度其他进程运行。

其三，当进程通过睡眠函数 sleep 这样的方法将自己主动挂起时，自然也会重新调度。

其四，当有优先级更高的进程运行时，为了保证高优先级进程的运行，当前进程会被挂起，由高优先级进程来运行。

最后一个，发生硬件中断时，CPU 上的进程会被中断挂起，转而执行内核中的中断服务程序。

了解这几个场景是非常有必要的，因为一旦出现上下文切换的性能问题，它们就是幕后凶手。

线程上下文切换

说完了进程的上下文切换，我们再来看看线程相关的问题。

线程与进程最大的区别在于，线程是调度的基本单位，而进程则是资源拥有的基本单位。说白了，所谓内核中的任务调度，实际上的调度对象是线程；而进程只是给线程提供了虚拟内存、全局变量等资源。所以，对于线程和进程，我们可以这么理解：

• 当进程只有一个线程时，可以认为进程就等于线程。
• 当进程拥有多个线程时，这些线程会共享相同的虚拟内存和全局变量等资源。这些资源在上下文切换时是不需要修改的。
• 另外，线程也有自己的私有数据，比如栈和寄存器等，这些在上下文切换时也是需要保存的。

这么一来，线程的上下文切换其实就可以分为两种情况：

第一种， 前后两个线程属于不同进程。此时，因为资源不共享，所以切换过程就跟进程上下文切换是一样。

第二种，前后两个线程属于同一个进程。此时，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据。

到这里你应该也发现了，虽然同为上下文切换，但同进程内的线程切换，要比多进程间的切换消耗更少的资源，而这，也正是多线程代替多进程的一个优势。

中断上下文切换

除了前面两种上下文切换，还有一个场景也会切换 CPU 上下文，那就是中断。

为了快速响应硬件的事件，中断处理会打断进程的正常调度和执行，转而调用中断处理程序，响应设备事件。而在打断其他进程时，就需要将进程当前的状态保存下来，这样在中断结束后，进程仍然可以从原来的状态恢复运行。

跟进程上下文不同，中断上下文切换并不涉及到进程的用户态。所以，即便中断过程打断了一个正处在用户态的进程，也不需要保存和恢复这个进程的虚拟内存、全局变量等用户态资源。中断上下文，其实只包括内核态中断服务程序执行所必需的状态，包括 CPU 寄存器、内核堆栈、硬件中断参数等。

对同一个 CPU 来说，中断处理比进程拥有更高的优先级，所以中断上下文切换并不会与进程上下文切换同时发生。同样道理，由于中断会打断正常进程的调度和执行，所以大部分中断处理程序都短小精悍，以便尽可能快的执行结束。

另外，跟进程上下文切换一样，中断上下文切换也需要消耗 CPU，切换次数过多也会耗费大量的 CPU，甚至严重降低系统的整体性能。所以，当你发现中断次数过多时，就需要注意去排查它是否会给你的系统带来严重的性能问题。

小结

总结一下，不管是哪种场景导致的上下文切换，你都应该知道：

1. CPU 上下文切换，是保证 Linux 系统正常工作的核心功能之一，一般情况下不需要我们特别关注。
2. 但过多的上下文切换，会把 CPU 时间消耗在寄存器、内核栈以及虚拟内存等数据的保存和恢复上，从而缩短进程真正运行的时间，导致系统的整体性能大幅下降。

今天主要为你介绍这几种上下文切换的工作原理，下一节，我将继续案例实战，说说上下文切换问题的分析方法。

在正式落地谈技术之前，我先花一些篇幅给你讲讲大数据技术的发展史，因为这对于你理解技术来说至关重要。

从我的角度而言，不管是学习某门技术，还是讨论某个事情，最好的方式一定不是一头扎到具体细节里，而是应该从时空的角度先了解它的来龙去脉，以及它为什么会演进成为现在的状态。当你深刻理解了这些前因后果之后，再去看现状，就会明朗很多，也能更直接地看到现状背后的本质。说实话，这对于我们理解技术、学习技术而言，同等重要。

今天我们常说的大数据技术，其实起源于 Google 在 2004 年前后发表的三篇论文，也就是我们经常听到的“三驾马车”，分别是分布式文件系统 GFS、大数据分布式计算框架 MapReduce 和 NoSQL 数据库系统 BigTable。

你知道，搜索引擎主要就做两件事情，一个是网页抓取，一个是索引构建，而在这个过程中，有大量的数据需要存储和计算。这“三驾马车”其实就是用来解决这个问题的，你从介绍中也能看出来，一个文件系统、一个计算框架、一个数据库系统。

现在你听到分布式、大数据之类的词，肯定一点儿也不陌生。但你要知道，在 2004 年那会儿，整个互联网还处于懵懂时代，Google 发布的论文实在是让业界为之一振，大家恍然大悟，原来还可以这么玩。

因为那个时间段，大多数公司的关注点其实还是聚焦在单机上，在思考如何提升单机的性能，寻找更贵更好的服务器。而 Google 的思路是部署一个大规模的服务器集群，通过分布式的方式将海量数据存储在这个集群上，然后利用集群上的所有机器进行数据计算。 这样，Google 其实不需要买很多很贵的服务器，它只要把这些普通的机器组织到一起，就非常厉害了。

当时的天才程序员，也是 Lucene 开源项目的创始人 Doug Cutting 正在开发开源搜索引擎 Nutch，阅读了 Google 的论文后，他非常兴奋，紧接着就根据论文原理初步实现了类似 GFS 和 MapReduce 的功能。

两年后的 2006 年，Doug Cutting 将这些大数据相关的功能从 Nutch 中分离了出来，然后启动了一个独立的项目专门开发维护大数据技术，这就是后来赫赫有名的 Hadoop，主要包括 Hadoop 分布式文件系统 HDFS 和大数据计算引擎 MapReduce。

当我们回顾软件开发的历史，包括我们自己开发的软件，你会发现，有的软件在开发出来以后无人问津或者寥寥数人使用，这样的软件其实在所有开发出来的软件中占大多数。而有的软件则可能会开创一个行业，每年创造数百亿美元的价值，创造百万计的就业岗位，这些软件曾经是 Windows、Linux、Java，而现在这个名单要加上 Hadoop 的名字。

如果有时间，你可以简单浏览下 Hadoop 的代码，这个纯用 Java 编写的软件其实并没有什么高深的技术难点，使用的也都是一些最基础的编程技巧，也没有什么出奇之处，但是它却给社会带来巨大的影响，甚至带动一场深刻的科技革命，推动了人工智能的发展与进步。

我觉得，我们在做软件开发的时候，也可以多思考一下，我们所开发软件的价值点在哪里？真正需要使用软件实现价值的地方在哪里？你应该关注业务、理解业务，有价值导向，用自己的技术为公司创造真正的价值，进而实现自己的人生价值。而不是整天埋头在需求说明文档里，做一个没有思考的代码机器人。

Hadoop 发布之后，Yahoo 很快就用了起来。大概又过了一年到了 2007 年，百度和阿里巴巴也开始使用 Hadoop 进行大数据存储与计算。

2008 年，Hadoop 正式成为 Apache 的顶级项目，后来 Doug Cutting 本人也成为了 Apache 基金会的主席。自此，Hadoop 作为软件开发领域的一颗明星冉冉升起。

同年，专门运营 Hadoop 的商业公司 Cloudera 成立，Hadoop 得到进一步的商业支持。

这个时候，Yahoo 的一些人觉得用 MapReduce 进行大数据编程太麻烦了，于是便开发了 Pig。Pig 是一种脚本语言，使用类 SQL 的语法，开发者可以用 Pig 脚本描述要对大数据集上进行的操作，Pig 经过编译后会生成 MapReduce 程序，然后在 Hadoop 上运行。

编写 Pig 脚本虽然比直接 MapReduce 编程容易，但是依然需要学习新的脚本语法。于是 Facebook 又发布了 Hive。Hive 支持使用 SQL 语法来进行大数据计算，比如说你可以写个 Select 语句进行数据查询，然后 Hive 会把 SQL 语句转化成 MapReduce 的计算程序。

这样，熟悉数据库的数据分析师和工程师便可以无门槛地使用大数据进行数据分析和处理了。Hive 出现后极大程度地降低了 Hadoop 的使用难度，迅速得到开发者和企业的追捧。据说，2011 年的时候，Facebook 大数据平台上运行的作业 90% 都来源于 Hive。

随后，众多 Hadoop 周边产品开始出现，大数据生态体系逐渐形成，其中包括：专门将关系数据库中的数据导入导出到 Hadoop 平台的 Sqoop；针对大规模日志进行分布式收集、聚合和传输的 Flume；MapReduce 工作流调度引擎 Oozie 等。

在 Hadoop 早期，MapReduce 既是一个执行引擎，又是一个资源调度框架，服务器集群的资源调度管理由 MapReduce 自己完成。但是这样不利于资源复用，也使得 MapReduce 非常臃肿。于是一个新项目启动了，将 MapReduce 执行引擎和资源调度分离开来，这就是 Yarn。2012 年，Yarn 成为一个独立的项目开始运营，随后被各类大数据产品支持，成为大数据平台上最主流的资源调度系统。

同样是在 2012 年，UC 伯克利 AMP 实验室（Algorithms、Machine 和 People 的缩写）开发的 Spark 开始崭露头角。当时 AMP 实验室的马铁博士发现使用 MapReduce 进行机器学习计算的时候性能非常差，因为机器学习算法通常需要进行很多次的迭代计算，而 MapReduce 每执行一次 Map 和 Reduce 计算都需要重新启动一次作业，带来大量的无谓消耗。还有一点就是 MapReduce 主要使用磁盘作为存储介质，而 2012 年的时候，内存已经突破容量和成本限制，成为数据运行过程中主要的存储介质。Spark 一经推出，立即受到业界的追捧，并逐步替代 MapReduce 在企业应用中的地位。

一般说来，像 MapReduce、Spark 这类计算框架处理的业务场景都被称作批处理计算，因为它们通常针对以“天”为单位产生的数据进行一次计算，然后得到需要的结果，这中间计算需要花费的时间大概是几十分钟甚至更长的时间。因为计算的数据是非在线得到的实时数据，而是历史数据，所以这类计算也被称为大数据离线计算。

而在大数据领域，还有另外一类应用场景，它们需要对实时产生的大量数据进行即时计算，比如对于遍布城市的监控摄像头进行人脸识别和嫌犯追踪。这类计算称为大数据流计算，相应地，有 Storm、Flink、Spark Streaming 等流计算框架来满足此类大数据应用的场景。 流式计算要处理的数据是实时在线产生的数据，所以这类计算也被称为大数据实时计算。

在典型的大数据的业务场景下，数据业务最通用的做法是，采用批处理的技术处理历史全量数据，采用流式计算处理实时新增数据。而像 Flink 这样的计算引擎，可以同时支持流式计算和批处理计算。

除了大数据批处理和流处理，NoSQL 系统处理的主要也是大规模海量数据的存储与访问，所以也被归为大数据技术。 NoSQL 曾经在 2011 年左右非常火爆，涌现出 HBase、Cassandra 等许多优秀的产品，其中 HBase 是从 Hadoop 中分离出来的、基于 HDFS 的 NoSQL 系统。

我们回顾软件发展的历史会发现，差不多类似功能的软件，它们出现的时间都非常接近，比如 Linux 和 Windows 都是在 90 年代初出现，Java 开发中的各类 MVC 框架也基本都是同期出现，Android 和 iOS 也是前脚后脚问世。2011 年前后，各种 NoSQL 数据库也是层出不群，我也是在那个时候参与开发了阿里巴巴自己的 NoSQL 系统。

事物发展有自己的潮流和规律，当你身处潮流之中的时候，要紧紧抓住潮流的机会，想办法脱颖而出，即使没有成功，也会更加洞悉时代的脉搏，收获珍贵的知识和经验。而如果潮流已经退去，这个时候再去往这个方向上努力，只会收获迷茫与压抑，对时代、对自己都没有什么帮助。

但是时代的浪潮犹如海滩上的浪花，总是一浪接着一浪，只要你站在海边，身处这个行业之中，下一个浪潮很快又会到来。你需要敏感而又深刻地去观察，略去那些浮躁的泡沫，抓住真正潮流的机会，奋力一搏，不管成败，都不会遗憾。

正所谓在历史前进的逻辑中前进，在时代发展的潮流中发展。通俗的说，就是要在风口中飞翔。

上面我讲的这些基本上都可以归类为大数据引擎或者大数据框架。而大数据处理的主要应用场景包括数据分析、数据挖掘与机器学习。数据分析主要使用 Hive、Spark SQL 等 SQL 引擎完成；数据挖掘与机器学习则有专门的机器学习框架 TensorFlow、Mahout 以及 MLlib 等，内置了主要的机器学习和数据挖掘算法。

此外，大数据要存入分布式文件系统（HDFS），要有序调度 MapReduce 和 Spark 作业执行，并能把执行结果写入到各个应用系统的数据库中，还需要有一个大数据平台整合所有这些大数据组件和企业应用系统。

图中的所有这些框架、平台以及相关的算法共同构成了大数据的技术体系，我将会在专栏后面逐个分析，帮你能够对大数据技术原理和应用算法构建起完整的知识体系，进可以专职从事大数据开发，退可以在自己的应用开发中更好地和大数据集成，掌控自己的项目。

上一期我们聊了大数据技术的发展历程，事实上，我们对大数据技术的使用同样也经历了一个发展过程。从最开始的 Google 在搜索引擎中开始使用大数据技术，到现在无处不在的各种人工智能应用，伴随着大数据技术的发展，大数据应用也从曲高和寡走到了今天的遍地开花。

Google 从最开始发表大数据划时代论文的时候，也许自己也没有想到，自己开启了一个大数据的新时代。今天大数据和人工智能的种种成就，离不开全球数百万大数据从业者的努力，这其中也包括你和我。历史也许由天才开启，但终究还是由人民创造，作为大数据时代的参与者，我们正在创造历史。

大数据应用的搜索引擎时代

作为全球最大的搜索引擎公司，Google 也是我们公认的大数据鼻祖，它存储着全世界几乎所有可访问的网页，数目可能超过万亿规模，全部存储起来大约需要数万块磁盘。为了将这些文件存储起来，Google 开发了 GFS（Google 文件系统），将数千台服务器上的数万块磁盘统一管理起来，然后当作一个文件系统，统一存储所有这些网页文件。

你可能会觉得，如果只是简单地将所有网页存储起来，好像也没什么太了不起的。没错，但是 Google 得到这些网页文件是要构建搜索引擎，需要对所有文件中的单词进行词频统计，然后根据 PageRank 算法计算网页排名。这中间，Google 需要对这数万块磁盘上的文件进行计算处理，这听上去就很了不起了吧。当然，也正是基于这些需求，Google 又开发了 MapReduce 大数据计算框架。

其实在 Google 之前，世界上最知名的搜索引擎是 Yahoo。但是 Google 凭借自己的大数据技术和 PageRank 算法，使搜索引擎的搜索体验得到了质的飞跃，人们纷纷弃 Yahoo 而转投 Google。所以当 Google 发表了自己的 GFS 和 MapReduce 论文后，Yahoo 应该是最早关注这些论文的公司。

Doug Cutting 率先根据 Google 论文做了 Hadoop，于是 Yahoo 就把 Doug Cutting 挖了过去，专职开发 Hadoop。可是 Yahoo 和 Doug Cutting 的蜜月也没有持续多久，Doug Cutting 不堪 Yahoo 的内部斗争，跳槽到专职做 Hadoop 商业化的公司 Cloudera，而 Yahoo 则投资了 Cloudera 的竞争对手 HortonWorks。

顶尖的公司和顶尖的高手一样，做事有一种优雅的美感。你可以看 Google 一路走来，从搜索引擎、Gmail、地图、Android、无人驾驶，每一步都将人类的技术边界推向更高的高度。而差一点的公司即使也曾经获得过显赫的地位，但是一旦失去做事的美感和节奏感，在这个快速变革的时代，陨落得比流星还快。

大数据应用的数据仓库时代

Google 的论文刚发表的时候，吸引的是 Yahoo 这样的搜索引擎公司和 Doug Cutting 这样的开源搜索引擎开发者，其他公司还只是“吃瓜群众”。但是当 Facebook 推出 Hive 的时候，嗅觉敏感的科技公司都不淡定了，他们开始意识到，大数据的时代真正开启了。

曾经我们在进行数据分析与统计时，仅仅局限于数据库，在数据库的计算环境中对数据库中的数据表进行统计分析。并且受数据量和计算能力的限制，我们只能对最重要的数据进行统计和分析。这里所谓最重要的数据，通常指的都是给老板看的数据和财务相关的数据。

而 Hive 可以在 Hadoop 上进行 SQL 操作，实现数据统计与分析。也就是说，我们可以用更低廉的价格获得比以往多得多的数据存储与计算能力。我们可以把运行日志、应用采集数据、数据库数据放到一起进行计算分析，获得以前无法得到的数据结果，企业的数据仓库也随之呈指数级膨胀。

不仅是老板，公司中每个普通员工比如产品经理、运营人员、工程师，只要有数据访问权限，都可以提出分析需求，从大数据仓库中获得自己想要了解的数据分析结果。

你看，在数据仓库时代，只要有数据，几乎就一定要进行统计分析，如果数据规模比较大，我们就会想到要用 Hadoop 大数据技术，这也是 Hadoop 在这个时期发展特别快的一个原因。技术的发展同时又促进了技术应用，这也为接下来大数据应用走进数据挖掘时代埋下伏笔。

大数据应用的数据挖掘时代

大数据一旦进入更多的企业，我们就会对大数据提出更多期望，除了数据统计，我们还希望发掘出更多数据的价值，大数据随之进入数据挖掘时代。

讲个真实的案例，很早以前商家就通过数据发现，买尿不湿的人通常也会买啤酒，于是精明的商家就把这两样商品放在一起，以促进销售。啤酒和尿不湿的关系，你可以有各种解读，但是如果不是通过数据挖掘，可能打破脑袋也想不出它们之间会有关系。在商业环境中，如何解读这种关系并不重要，重要的是它们之间只要存在关联，就可以进行关联分析，最终目的是让用户尽可能看到想购买的商品。

除了商品和商品有关系，还可以利用人和人之间的关系推荐商品。如果两个人购买的商品有很多都是类似甚至相同的，不管这两个人天南海北相隔多远，他们一定有某种关系，比如可能有差不多的教育背景、经济收入、兴趣爱好。根据这种关系，可以进行关联推荐，让他们看到自己感兴趣的商品。

更进一步，大数据还可以将每个人身上的不同特性挖掘出来，打上各种各样的标签：90 后、生活在一线城市、月收入 1～2 万、宅……这些标签组成了用户画像，并且只要这样的标签足够多，就可以完整描绘出一个人，甚至比你最亲近的人对你的描述还要完整、准确。

除了商品销售，数据挖掘还可以用于人际关系挖掘。你听过“六度分隔理论”吗，它认为世界上两个互不认识的人，只需要很少的中间人就能把他们联系起来。这个理论在美国的实验结果是，通过六步就能联系上两个不认识的美国人。也是基于这个理论，Facebook 研究了十几亿用户的数据，试图找到关联两个陌生人之间的数字，答案是惊人的 3.57。你可以看到，各种各样的社交软件记录着我们的好友关系，通过关系图谱挖掘，几乎可以把世界上所有的人际关系网都描绘出来。

现代生活几乎离不开互联网，各种各样的应用无时不刻不在收集数据，这些数据在后台的大数据集群中一刻不停地在被进行各种分析与挖掘。这些分析和挖掘带给我们的是美好还是恐惧，依赖大数据从业人员的努力。但是可以肯定，不管最后结果如何，这个进程只会加速不会停止，你我只能投入其中。

大数据应用的机器学习时代

我们很早就发现，数据中蕴藏着规律，这个规律是所有数据都遵循的，过去发生的事情遵循这个规律，将来要发生的事情也遵循这个规律。一旦找到了这个规律，对于正在发生的事情，就可以按照这个规律进行预测。

在过去，我们受数据采集、存储、计算能力的限制，只能通过抽样的方式获取小部分数据，无法得到完整的、全局的、细节的规律。而现在有了大数据，可以把全部的历史数据都收集起来，统计其规律，进而预测正在发生的事情。

这就是机器学习。

把历史上人类围棋对弈的棋谱数据都存储起来，针对每一种盘面记录如何落子可以得到更高的赢面。得到这个统计规律以后，就可以利用这个规律用机器和人下棋，每一步都计算落在何处将得到更大的赢面，于是我们就得到了一个会下棋的机器人，这就是前两年轰动一时的 AlphaGo，以压倒性优势下赢了人类的顶尖棋手。

再举个和我们生活更近的例子。把人聊天的对话数据都收集起来，记录每一次对话的上下文，如果上一句是问今天过得怎么样，那么下一句该如何应对，通过机器学习可以统计出来。将来有人再问今天过得怎么样，就可以自动回复下一句话，于是我们就得到一个会聊天的机器人。Siri、天猫精灵、小爱同学，这样的语音聊天机器人在机器学习时代已经满大街都是了。

将人类活动产生的数据，通过机器学习得到统计规律，进而可以模拟人的行为，使机器表现出人类特有的智能，这就是人工智能 AI。

现在我们对待人工智能还有些不理智的态度，有的人认为人工智能会越来越强大，将来会统治人类。实际上，稍微了解一点人工智能的原理就会发现，这只是大数据计算出来的统计规律而已，表现的再智能，也不可能理解这样做的意义，而有意义才是人类智能的源泉。按目前人工智能的发展思路，永远不可能出现超越人类的智能，更不可能统治人类。

小结

大数据从搜索引擎到机器学习，发展思路其实是一脉相承的，就是想发现数据中的规律并为我们所用。所以很多人把数据称作金矿，大数据应用就是从这座蕴含知识宝藏的金矿中发掘中有商业价值的真金白银出来。

数据中蕴藏着价值已经是众所周知的事情了，那么如何从这些庞大的数据中发掘出我们想要的知识价值，这正是大数据技术目前正在解决的事情，包括大数据存储与计算，也包括大数据分析、挖掘、机器学习等应用。

美国的西部淘金运动带来了美国的大拓荒时代，来自全世界各地的人涌向美国西部，将人口、资源、生产力带到了荒蛮的西部地带，一条条铁路也将美国的东西海岸连接起来，整个美国也随之繁荣起来。大数据这座更加庞大的金矿目前也正发挥着同样的作用，全世界无数的政府、企业、个人正在关注着这座金矿，无数的资源正在向这里涌来。

我们不曾生活在美国西部淘金的繁荣时代，错过了那个光荣与梦想、自由与激情的个人英雄主义时代。但是现在，一个更具划时代意义的大数据淘金时代已经到来，而你我正身处其中。

作为一个软件开发工程师，你对数据库肯定再熟悉不过了。作为主流的数据存储系统，它在我们的业务开发中，有着举足轻重的地位。在工作中，为了加速数据库中数据的查找速度，我们常用的处理思路是，对表中数据创建索引。那你是否思考过，数据库索引是如何实现的呢？底层使用的是什么数据结构和算法呢？

算法解析

思考的过程比结论更重要。跟着我学习了这么多节课，很多同学已经意识到这一点，比如 Jerry 银银同学。我感到很开心。所以，今天的讲解，我会尽量还原这个解决方案的思考过程，让你知其然，并且知其所以然。

1. 解决问题的前提是定义清楚问题

如何定义清楚问题呢？除了对问题进行详细的调研，还有一个办法，那就是，通过对一些模糊的需求进行假设，来限定要解决的问题的范围。

如果你对数据库的操作非常了解，针对我们现在这个问题，你就能把索引的需求定义得非常清楚。但是，对于大部分软件工程师来说，我们可能只了解一小部分常用的 SQL 语句，所以，这里我们假设要解决的问题，只包含这样两个常用的需求：

• 根据某个值查找数据，比如 select * from user where id=1234；
• 根据区间值来查找某些数据，比如 select * from user where id > 1234 and id < 2345。

除了这些功能性需求之外，这种问题往往还会涉及一些非功能性需求，比如安全、性能、用户体验等等。限于专栏要讨论的主要是数据结构和算法，对于非功能性需求，我们着重考虑性能方面的需求。性能方面的需求，我们主要考察时间和空间两方面，也就是执行效率和存储空间。

在执行效率方面，我们希望通过索引，查询数据的效率尽可能的高；在存储空间方面，我们希望索引不要消耗太多的内存空间。

2. 尝试用学过的数据结构解决这个问题

问题的需求大致定义清楚了，我们现在回想一下，能否利用已经学习过的数据结构解决这个问题呢？支持快速查询、插入等操作的动态数据结构，我们已经学习过散列表、平衡二叉查找树、跳表。

我们先来看散列表。散列表的查询性能很好，时间复杂度是 O(1)。但是，散列表不能支持按照区间快速查找数据。所以，散列表不能满足我们的需求。

我们再来看平衡二叉查找树。尽管平衡二叉查找树查询的性能也很高，时间复杂度是 O(logn)。而且，对树进行中序遍历，我们还可以得到一个从小到大有序的数据序列，但这仍然不足以支持按照区间快速查找数据。

我们再来看跳表。跳表是在链表之上加上多层索引构成的。它支持快速地插入、查找、删除数据，对应的时间复杂度是 O(logn)。并且，跳表也支持按照区间快速地查找数据。我们只需要定位到区间起点值对应在链表中的结点，然后从这个结点开始，顺序遍历链表，直到区间终点对应的结点为止，这期间遍历得到的数据就是满足区间值的数据。

这样看来，跳表是可以解决这个问题。实际上，数据库索引所用到的数据结构跟跳表非常相似，叫作 B+ 树。不过，它是通过二叉查找树演化过来的，而非跳表。为了给你还原发明 B+ 树的整个思考过程，所以，接下来，我还再从二叉查找树讲起，看它是如何一步一步被改造成 B+ 树的。

3. 改造二叉查找树来解决这个问题

为了让二叉查找树支持按照区间来查找数据，我们可以对它进行这样的改造：树中的节点并不存储数据本身，而是只是作为索引。除此之外，我们把每个叶子节点串在一条链表上，链表中的数据是从小到大有序的。经过改造之后的二叉树，就像图中这样，看起来是不是很像跳表呢？

改造之后，如果我们要求某个区间的数据。我们只需要拿区间的起始值，在树中进行查找，当查找到某个叶子节点之后，我们再顺着链表往后遍历，直到链表中的结点数据值大于区间的终止值为止。所有遍历到的数据，就是符合区间值的所有数据。

但是，我们要为几千万、上亿的数据构建索引，如果将索引存储在内存中，尽管内存访问的速度非常快，查询的效率非常高，但是，占用的内存会非常多。

比如，我们给一亿个数据构建二叉查找树索引，那索引中会包含大约 1 亿个节点，每个节点假设占用 16 个字节，那就需要大约 1GB 的内存空间。给一张表建立索引，我们需要 1GB 的内存空间。如果我们要给 10 张表建立索引，那对内存的需求是无法满足的。如何解决这个索引占用太多内存的问题呢？

我们可以借助时间换空间的思路，把索引存储在硬盘中，而非内存中。我们都知道，硬盘是一个非常慢速的存储设备。通常内存的访问速度是纳秒级别的，而磁盘访问的速度是毫秒级别的。读取同样大小的数据，从磁盘中读取花费的时间，是从内存中读取所花费时间的上万倍，甚至几十万倍。

这种将索引存储在硬盘中的方案，尽管减少了内存消耗，但是在数据查找的过程中，需要读取磁盘中的索引，因此数据查询效率就相应降低很多。

二叉查找树，经过改造之后，支持区间查找的功能就实现了。不过，为了节省内存，如果把树存储在硬盘中，那么每个节点的读取（或者访问），都对应一次磁盘 IO 操作。树的高度就等于每次查询数据时磁盘 IO 操作的次数。

我们前面讲到，比起内存读写操作，磁盘 IO 操作非常耗时，所以我们优化的重点就是尽量减少磁盘 IO 操作，也就是，尽量降低树的高度。那如何降低树的高度呢？

我们来看下，如果我们把索引构建成 m 叉树，高度是不是比二叉树要小呢？如图所示，给 16 个数据构建二叉树索引，树的高度是 4，查找一个数据，就需要 4 个磁盘 IO 操作（如果根节点存储在内存中，其他结点存储在磁盘中），如果对 16 个数据构建五叉树索引，那高度只有 2，查找一个数据，对应只需要 2 次磁盘操作。如果 m 叉树中的 m 是 100，那对一亿个数据构建索引，树的高度也只是 3，最多只要 3 次磁盘 IO 就能获取到数据。磁盘 IO 变少了，查找数据的效率也就提高了。

如果我们将 m 叉树实现 B+ 树索引，用代码实现出来，就是下面这个样子（假设我们给 int 类型的数据库字段添加索引，所以代码中的 keywords 是 int 类型的）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

/**
 * 这是 B+ 树非叶子节点的定义。
 *
 * 假设 keywords=[3, 5, 8, 10]
 * 4 个键值将数据分为 5 个区间：(-INF,3), [3,5), [5,8), [8,10), [10,INF)
 * 5 个区间分别对应：children[0]...children[4]
 *
 * m 值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小：
 * PAGE_SIZE = (m-1)*4[keywordss 大小]+m*8[children 大小]
 */
public class BPlusTreeNode {
  public static int m = 5; // 5 叉树
  public int[] keywords = new int[m-1]; // 键值，用来划分数据区间
  public BPlusTreeNode[] children = new BPlusTreeNode[m];// 保存子节点指针
}
 
/**
 * 这是 B+ 树中叶子节点的定义。
 *
 * B+ 树中的叶子节点跟内部结点是不一样的,
 * 叶子节点存储的是值，而非区间。
 * 这个定义里，每个叶子节点存储 3 个数据行的键值及地址信息。
 *
 * k 值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小：
 * PAGE_SIZE = k*4[keyw.. 大小]+k*8[dataAd.. 大小]+8[prev 大小]+8[next 大小]
 */
public class BPlusTreeLeafNode {
  public static int k = 3;
  public int[] keywords = new int[k]; // 数据的键值
  public long[] dataAddress = new long[k]; // 数据地址
 
  public BPlusTreeLeafNode prev; // 这个结点在链表中的前驱结点
  public BPlusTreeLeafNode next; // 这个结点在链表中的后继结点
}

我稍微解释一下这段代码。

对于相同个数的数据构建 m 叉树索引，m 叉树中的 m 越大，那树的高度就越小，那 m 叉树中的 m 是不是越大越好呢？到底多大才最合适呢？

不管是内存中的数据，还是磁盘中的数据，操作系统都是按页（一页大小通常是 4KB，这个值可以通过 getconfig PAGE_SIZE 命令查看）来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次 IO 操作。所以，我们在选择 m 大小的时候，要尽量让每个节点的大小等于一个页的大小。读取一个节点，只需要一次磁盘 IO 操作。

尽管索引可以提高数据库的查询效率，但是，作为一名开发工程师，你应该也知道，索引有利也有弊，它也会让写入数据的效率下降。这是为什么呢？

数据的写入过程，会涉及索引的更新，这是索引导致写入变慢的主要原因。

对于一个 B+ 树来说，m 值是根据页的大小事先计算好的，也就是说，每个节点最多只能有 m 个子节点。在往数据库中写入数据的过程中，这样就有可能使索引中某些节点的子节点个数超过 m，这个节点的大小超过了一个页的大小，读取这样一个节点，就会导致多次磁盘 IO 操作。我们该如何解决这个问题呢？

实际上，处理思路并不复杂。我们只需要将这个节点分裂成两个节点。但是，节点分裂之后，其上层父节点的子节点个数就有可能超过 m 个。不过这也没关系，我们可以用同样的方法，将父节点也分裂成两个节点。这种级联反应会从下往上，一直影响到根节点。这个分裂过程，你可以结合着下面这个图一块看，会更容易理解（图中的 B+ 树是一个三叉树。我们限定叶子节点中，数据的个数超过 2 个就分裂节点；非叶子节点中，子节点的个数超过 3 个就分裂节点）。

正是因为要时刻保证 B+ 树索引是一个 m 叉树，所以，索引的存在会导致数据库写入的速度降低。实际上，不光写入数据会变慢，删除数据也会变慢。这是为什么呢？

我们在删除某个数据的时候，也要对应的更新索引节点。这个处理思路有点类似跳表中删除数据的处理思路。频繁的数据删除，就会导致某些结点中，子节点的个数变得非常少，长此以往，如果每个节点的子节点都比较少，势必会影响索引的效率。

我们可以设置一个阈值。在 B+ 树中，这个阈值等于 m/2。如果某个节点的子节点个数小于 m/2，我们就将它跟相邻的兄弟节点合并。不过，合并之后结点的子节点个数有可能会超过 m。针对这种情况，我们可以借助插入数据时候的处理方法，再分裂节点。

文字描述不是很直观，我举了一个删除操作的例子，你可以对比着看下（图中的 B+ 树是一个五叉树。我们限定叶子节点中，数据的个数少于 2 个就合并节点；非叶子节点中，子节点的个数少于 3 个就合并节点。）。

数据库索引以及 B+ 树的由来，到此就讲完了。你有没有发现，B+ 树的结构和操作，跟跳表非常类似。理论上讲，对跳表稍加改造，也可以替代 B+ 树，作为数据库的索引实现的。

B+ 树发明于 1972 年，跳表发明于 1989 年，我们可以大胆猜想下，跳表的作者有可能就是受了 B+ 树的启发，才发明出跳表来的。不过，这个也无从考证了。

总结引申

今天，我们讲解了数据库索引实现，依赖的底层数据结构，B+ 树。它通过存储在磁盘的多叉树结构，做到了时间、空间的平衡，既保证了执行效率，又节省了内存。

前面的讲解中，为了一步一步详细地给你介绍 B+ 树的由来，内容看起来比较零散。为了方便你掌握和记忆，我这里再总结一下 B+ 树的特点：

• 每个节点中子节点的个数不能超过 m，也不能小于 m/2；
• 根节点的子节点个数可以不超过 m/2，这是一个例外；
• m 叉树只存储索引，并不真正存储数据，这个有点儿类似跳表；
• 通过链表将叶子节点串联在一起，这样可以方便按区间查找；
• 一般情况，根节点会被存储在内存中，其他节点存储在磁盘中。

除了 B+ 树，你可能还听说过 B 树、B- 树，我这里简单提一下。实际上，B- 树就是 B 树，英文翻译都是 B-Tree，这里的“-”并不是相对 B+ 树中的“+”，而只是一个连接符。这个很容易误解，所以我强调下。

而 B 树实际上是低级版的 B+ 树，或者说 B+ 树是 B 树的改进版。B 树跟 B+ 树的不同点主要集中在这几个地方：

• B+ 树中的节点不存储数据，只是索引，而 B 树中的节点存储数据；
• B 树中的叶子节点并不需要链表来串联。

也就是说，B 树只是一个每个节点的子节点个数不能小于 m/2 的 m 叉树。

课后思考

1. B+ 树中，将叶子节点串起来的链表，是单链表还是双向链表？为什么？
2. 我们对平衡二叉查找树进行改造，将叶子节点串在链表中，就支持了按照区间来查找数据。我们在散列表（下）讲到，散列表也经常跟链表一块使用，如果我们把散列表中的结点，也用链表串起来，能否支持按照区间查找数据呢？

极客时间版权所有: https://time.geekbang.org/column/article/77830

上一节课我跟你分享了数据挖掘的最佳学习路径，相信你对接下来的学习已经心中有数了。今天我们继续预习课，我会用三篇文章，分别对 Python 的基础语法、NumPy 和 Pandas 进行讲解，带你快速入门 Python 语言。如果你已经有 Python 基础了，那先恭喜你已经掌握了这门简洁而高效的语言，这几节课你可以跳过，或者也可以当作复习，自己查漏补缺，你还可以在留言区分享自己的 Python 学习和使用心得。

好了，你现在心中是不是有个问题，要学好数据分析，一定要掌握 Python 吗？

我的答案是，想学好数据分析，你最好掌握 Python 语言。为什么这么说呢？

首先，在一份关于开发语言的调查中，使用过 Python 的开发者，80% 都会把 Python 作为自己的主要语言。Python 已经成为发展最快的主流编程语言，从众多开发语言中脱颖而出，深受开发者喜爱。其次，在数据分析领域中，使用 Python 的开发者是最多的，远超其他语言之和。最后，Python 语言简洁，有大量的第三方库，功能强大，能解决数据分析的大部分问题，这一点我下面具体来说。

Python 语言最大的优点是简洁，它虽然是 C 语言写的，但是摒弃了 C 语言的指针，这就让代码非常简洁明了。同样的一行 Python 代码，甚至相当于 5 行 Java 代码。我们读 Python 代码就像是读英文一样直观，这就能让程序员更好地专注在问题解决上，而不是在语言本身。

当然除了 Python 自身的特点，Python 还有强大的开发者工具。在数据科学领域，Python 有许多非常著名的工具库：比如科学计算工具 NumPy 和 Pandas 库，深度学习工具 Keras 和 TensorFlow，以及机器学习工具 Scikit-learn，使用率都非常高。

总之，如果你想在数据分析、机器学习等数据科学领域有所作为，那么掌握一项语言，尤其是 Python 语言的使用是非常有必要的，尤其是我们刚提到的这些工具，熟练掌握它们会让你事半功倍。

安装及 IDE 环境

了解了为什么要学 Python，接下来就带你快速开始你的第一个 Python 程序，所以我们先来了解下如何安装和搭建 IDE 环境。

Python 的版本选择

Python 主要有两个版本： 2.7.x 和 3.x。两个版本之间存在一些差异，但并不大，它们语法不一样的地方不到 10%。

另一个事实就是：大部分 Python 库都同时支持 Python 2.7.x 和 3.x 版本。虽然官方称 Python2.7 只维护到 2020 年，但是我想告诉你的是：千万不要忽视 Python2.7，它的寿命远不止到 2020 年，而且这两年 Python2.7 还是占据着 Python 版本的统治地位。一份调查显示：在 2017 年的商业项目中 2.7 版本依然是主流，占到了 63.7%，即使这两年 Python3.x 版本使用的增速较快，但实际上 Python3.x 在 2008 年就已经有了。

那么你可能会问：这两个版本该如何选择呢？

版本选择的标准就是看你的项目是否会依赖于 Python2.7 的包，如果有依赖的就只能使用 Python2.7，否则你可以用 Python 3.x 开始全新的项目。

Python IDE 推荐

确定了版本问题后，怎么选择 Python IDE 呢？有众多优秀的选择，这里推荐几款。

1. PyCharm

这是一个跨平台的 Python 开发工具，可以帮助用户在使用 Python 时提升效率，比如：调试、语法高亮、代码跳转、自动完成、智能提示等。

2. Sublime Text

SublimeText 是个著名的编辑器，Sublime Text3 基本上可以 1 秒即启动，反应速度很快。同时它对 Python 的支持也很到位，具有代码高亮、语法提示、自动完成等功能。

3. Vim

Vim 是一个简洁、高效的工具，速度很快，可以做任何事，从来不崩溃。不过 Vim 相比于 Sublime Text 上手有一定难度，配置起来有些麻烦。

4. Eclipse+PyDev

习惯使用 Java 的人一定对 Eclipse 这个 IDE 不陌生，那么使用 Eclipse+PyDev 插件会是一个很好的选择，这样熟悉 Eclipse 的开发者可以轻易上手。

如果上面这些 IDE 你之前都没有怎么用过，那么推荐你使用 Sublime Text，上手简单，反应速度快。

Python 基础语法

环境配置好后，我们就来快速学习几个 Python 必会的基础语法。我假设你是 Python 零基础，但已经有一些其他编程语言的基础。下面我们一一来看。

输入与输出

1
2
3
4

name = raw_input("What's your name?")
sum = 100+100
print ('hello,%s' %name)
print ('sum = %d' %sum)

raw_input 是 Python2.7 的输入函数，在 python3.x 里可以直接使用 input，赋值给变量 name，print 是输出函数，%name 代表变量的数值，因为是字符串类型，所以在前面用的 %s 作为代替。

这是运行结果：

1
2
3

What's your name?cy
hello,cy
sum = 200

判断语句：if … else …

1
2
3
4
5
6
7

if score>= 90:
       print 'Excellent'
else:
       if score < 60:
           print 'Fail'
       else:
           print 'Good Job'

if … else … 是经典的判断语句，需要注意的是在 if expression 后面有个冒号，同样在 else 后面也存在冒号。

另外需要注意的是，Python 不像其他语言一样使用{}或者 begin…end 来分隔代码块，而是采用代码缩进和冒号的方式来区分代码之间的层次关系。所以代码缩进在 Python 中是一种语法，如果代码缩进不统一，比如有的是 tab 有的是空格，会怎样呢？会产生错误或者异常。相同层次的代码一定要采用相同层次的缩进。

循环语句：for … in

1
2
3
4

sum = 0
for number in range(11):
    sum = sum + number
print sum

运行结果：

1

55

for 循环是一种迭代循环机制，迭代即重复相同的逻辑操作。如果规定循环的次数，我们可以使用 range 函数，它在 for 循环中比较常用。range(11) 代表从 0 到 10，不包括 11，也相当于 range(0,11)，range 里面还可以增加步长，比如 range(1,11,2) 代表的是 [1,3,5,7,9]。

循环语句: while

1
2
3
4
5
6

sum = 0
number = 1
while number < 11:
       sum = sum + number
       number = number + 1
print sum

运行结果：

1

55

1 到 10 的求和也可以用 while 循环来写，这里 while 控制了循环的次数。while 循环是条件循环，在 while 循环中对于变量的计算方式更加灵活。因此 while 循环适合循环次数不确定的循环，而 for 循环的条件相对确定，适合固定次数的循环。

数据类型：列表、元组、字典、集合

列表：[]

1
2
3
4
5
6
7

lists = ['a','b','c']
lists.append('d')
print lists
print len(lists)
lists.insert(0,'mm')
lists.pop()
print lists

运行结果：

1
2
3

['a', 'b', 'c', 'd']
4
['mm', 'a', 'b', 'c']

列表是 Python 中常用的数据结构，相当于数组，具有增删改查的功能，我们可以使用 len() 函数获得 lists 中元素的个数；使用 append() 在尾部添加元素，使用 insert() 在列表中出入元素，使用 pop() 删除尾部的元素。

元组 (tuple)

1
2

tuples = ('tupleA','tupleB')
print tuples[0]

运行结果：

1

tupleA

元组 tuple 和 list 非常类似，但是 tuple 一旦初始化就不能修改。因为不能修改所以没有 append(), insert() 这样的方法，可以像访问数组一样进行访问，比如 tuples[0]，但不能赋值。

字典 {dictionary}

1
2
3
4
5
6
7
8
9
10
11
12
13

# -*- coding: utf-8 -*
# 定义一个 dictionary
score = {'guanyu':95,'zhangfei':96}
# 添加一个元素
score['zhaoyun'] = 98
print score
# 删除一个元素
score.pop('zhangfei')
# 查看 key 是否存在
print 'guanyu' in score
# 查看一个 key 对应的值
print score.get('guanyu')
print score.get('yase',99)

运行结果：

1
2
3
4

{'guanyu': 95, 'zhaoyun': 98, 'zhangfei': 96}
True
95
99

字典其实就是{key, value}，多次对同一个 key 放入 value，后面的值会把前面的值冲掉，同样字典也有增删改查。增加字典的元素相当于赋值，比如 score[‘zhaoyun’] = 98，删除一个元素使用 pop，查询使用 get，如果查询的值不存在，我们也可以给一个默认值，比如 score.get(‘yase’,99)。

集合：set

1
2
3
4
5

s = set(['a', 'b', 'c'])
s.add('d')
s.remove('b')
print s
print 'c' in s

运行结果：

1
2

set(['a', 'c', 'd'])
True

集合 set 和字典 dictory 类似，不过它只是 key 的集合，不存储 value。同样可以增删查，增加使用 add，删除使用 remove，查询看某个元素是否在这个集合里，使用 in。

注释：#

注释在 python 中使用 #，如果注释中有中文，一般会在代码前添加 # -- coding: utf-8 -。

如果是多行注释，使用三个单引号，或者三个双引号，比如：

1
2
3
4
5
6

# -*- coding: utf-8 -*
'''
这是多行注释，用三个单引号
这是多行注释，用三个单引号 
这是多行注释，用三个单引号
'''

引用模块 / 包：import

1
2
3
4
5
6
7
8

# 导入一个模块
import model_name
# 导入多个模块
import module_name1,module_name2
# 导入包中指定模块 
from package_name import moudule_name
# 导入包中所有模块 
from package_name import *

Python 语言中 import 的使用很简单，直接使用 import module_name 语句导入即可。这里 import 的本质是什么呢？import 的本质是路径搜索。import 引用可以是模块 module，或者包 package。

针对 module，实际上是引用一个.py 文件。而针对 package，可以采用 from … import …的方式，这里实际上是从一个目录中引用模块，这时目录结构中必须带有一个 init.py 文件。

函数：def

1
2
3

def addone(score):
   return score + 1
print addone(99)

运行结果：

1
2

100
复制代码

函数代码块以 def 关键词开头，后接函数标识符名称和圆括号，在圆括号里是传进来的参数，然后通过 return 进行函数结果得反馈。

A+B Problem

上面的讲的这些基础语法，我们可以用 sumlime text 编辑器运行 Python 代码。另外，告诉你一个相当高效的方法，你可以充分利用一个刷题进阶的网址： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1 ，这是浙江大学 ACM 的 OnlineJudge。

什么是 OnlineJudge 呢？它实际上是一个在线答题系统，做题后你可以在后台提交代码，然后 OnlineJudge 会告诉你运行的结果，如果结果正确就反馈：Accepted，如果错误就反馈：Wrong Answer。

不要小看这样的题目，也会存在编译错误、内存溢出、运行超时等等情况。所以题目对编码的质量要求还是挺高的。下面我就给你讲讲这道 A+B 的题目，你可以自己做练习，然后在后台提交答案。

题目：A+B

输入格式：有一系列的整数对 A 和 B，以空格分开。

输出格式：对于每个整数对 A 和 B，需要给出 A 和 B 的和。

输入输出样例：

1
2
3
4

INPUT
1 5
OUTPUT
6

针对这道题，我给出了下面的答案：

1
2
3
4
5
6
7

while True:
       try:
              line = raw_input()
              a = line.split()
              print int(a[0]) + int(a[1])
       except:
              break

当然每个人可以有不同的解法，官方也有 Python 的答案，这里给你介绍这个 OnlineJudge 是因为：

1. 可以在线得到反馈，提交代码后，系统会告诉你对错。而且你能看到每道题的正确率，和大家提交后反馈的状态；
2. 有社区论坛可以进行交流学习；
3. 对算法和数据结构的提升大有好处，当然对数据挖掘算法的灵活运用和整个编程基础的提升都会有很大的帮助。

总结

现在我们知道，Python 毫无疑问是数据分析中最主流的语言。今天我们学习了这么多 Python 的基础语法，你是不是体会到了它的简洁。如果你有其他编程语言基础，相信你会非常容易地转换成 Python 语法的。那到此，Python 我们也就算入门了。有没有什么方法可以在此基础上快速提升 Python 编程水平呢？给你分享下我的想法。

在日常工作中，我们解决的问题都不属于高难度的问题，大部分人做的都是开发工作而非科研项目。所以我们要提升的主要是熟练度，而通往熟练度的唯一路径就是练习、练习、再练习！

如果你是第一次使用 Python，不用担心，最好的方式就是直接做题。把我上面的例子都跑一遍，自己在做题中体会。

如果你想提升自己的编程基础，尤其是算法和数据结构相关的能力，因为这个在后面的开发中都会用到。那么 ACM Online Judge 是非常好的选择，勇敢地打开这扇大门，把它当作你进阶的好工具。

你可以从 Accepted 比率高的题目入手，你做对的题目数越多，你的排名也会越来越往前，这意味着你的编程能力，包括算法和数据结构的能力都有了提升。另外这种在社区中跟大家一起学习，还能排名，就像游戏一样，让学习更有趣味，从此不再孤独。

我在文章中多次强调练习的作用，这样可以增加你对数据分析相关内容的熟练度。所以我给你出了两道练习题，你可以思考下如何来做，欢迎把答案放到评论下面，我也会和你一起在评论区进行讨论。

1. 如果我想在 Python 中引用 scikit-learn 库该如何引用？
2. 求 1+3+5+7+…+99 的求和，用 Python 该如何写？

极客时间版权所有: https://time.geekbang.org/column/article/73574

上一节中，我给你分享了数据分析的全景图，其中最关键的部分就是数据挖掘，那什么是数据挖掘呢？

想象一下，茫茫的大海上，孤零零地屹立着钻井，想要从大海中开采出宝贵的石油。

对于普通人来说，大海是很难感知的，就更不用说找到宝藏了。但对于熟练的石油开采人员来说，大海是有坐标的。他们对地质做勘探，分析地质构造，从而发现哪些地方更可能有石油。然后用开采工具，进行深度挖掘，直到打到石油为止。

大海、地质信息、石油对开采人员来说就是数据源、地理位置、以及分析得到的结果。

而我们要做的数据挖掘工作，就好像这个钻井一样，通过分析这些数据，从庞大的数据中发现规律，找到宝藏。

数据挖掘，从知识清单开始

我们第一天学开车的时候一定不会直接上路，而是要你先学习基本的知识，然后再进行上车模拟。

只有对知识有全面的认知，才能确保在以后的工作中即使遇到了问题，也可以快速定位问题所在，然后找方法去对应和解决。

所以我列了一个数据挖掘的知识清单，分别是数据挖掘的基本流程、十大算法和数学原理，以此来开启我们的学习之旅。

数据挖掘的基本流程

在正式讲数据挖掘知识清单之前，我先和你聊聊数据挖掘的基本流程。

数据挖掘的过程可以分成以下 6 个步骤。

1. 商业理解：数据挖掘不是我们的目的，我们的目的是更好地帮助业务，所以第一步我们要从商业的角度理解项目需求，在这个基础上，再对数据挖掘的目标进行定义。
2. 数据理解：尝试收集部分数据，然后对数据进行探索，包括数据描述、数据质量验证等。这有助于你对收集的数据有个初步的认知。
3. 数据准备：开始收集数据，并对数据进行清洗、数据集成等操作，完成数据挖掘前的准备工作。
4. 模型建立：选择和应用各种数据挖掘模型，并进行优化，以便得到更好的分类结果。
5. 模型评估：对模型进行评价，并检查构建模型的每个步骤，确认模型是否实现了预定的商业目标。
6. 上线发布：模型的作用是从数据中找到金矿，也就是我们所说的“知识”，获得的知识需要转化成用户可以使用的方式，呈现的形式可以是一份报告，也可以是实现一个比较复杂的、可重复的数据挖掘过程。数据挖掘结果如果是日常运营的一部分，那么后续的监控和维护就会变得重要。

数据挖掘的十大算法

为了进行数据挖掘任务，数据科学家们提出了各种模型，在众多的数据挖掘模型中，国际权威的学术组织 ICDM （the IEEE International Conference on Data Mining）评选出了十大经典的算法。

按照不同的目的，我可以将这些算法分成四类，以便你更好的理解。

l 分类算法：C4.5，朴素贝叶斯（Naive Bayes），SVM，KNN，Adaboost，CART

l 聚类算法：K-Means，EM

l 关联分析：Apriori

l 连接分析：PageRank

1. C4.5

C4.5 算法是得票最高的算法，可以说是十大算法之首。C4.5 是决策树的算法，它创造性地在决策树构造过程中就进行了剪枝，并且可以处理连续的属性，也能对不完整的数据进行处理。它可以说是决策树分类中，具有里程碑式意义的算法。

2. 朴素贝叶斯（Naive Bayes）

朴素贝叶斯模型是基于概率论的原理，它的思想是这样的：对于给出的未知物体想要进行分类，就需要求解在这个未知物体出现的条件下各个类别出现的概率，哪个最大，就认为这个未知物体属于哪个分类。

3. SVM

SVM 的中文叫支持向量机，英文是 Support Vector Machine，简称 SVM。SVM 在训练中建立了一个超平面的分类模型。如果你对超平面不理解，没有关系，我在后面的算法篇会给你进行介绍。

4. KNN

KNN 也叫 K 最近邻算法，英文是 K-Nearest Neighbor。所谓 K 近邻，就是每个样本都可以用它最接近的 K 个邻居来代表。如果一个样本，它的 K 个最接近的邻居都属于分类 A，那么这个样本也属于分类 A。

5. AdaBoost

Adaboost 在训练中建立了一个联合的分类模型。boost 在英文中代表提升的意思，所以 Adaboost 是个构建分类器的提升算法。它可以让我们多个弱的分类器组成一个强的分类器，所以 Adaboost 也是一个常用的分类算法。

6. CART

CART 代表分类和回归树，英文是 Classification and Regression Trees。像英文一样，它构建了两棵树：一颗是分类树，另一个是回归树。和 C4.5 一样，它是一个决策树学习方法。

7. Apriori

Apriori 是一种挖掘关联规则（association rules）的算法，它通过挖掘频繁项集（frequent item sets）来揭示物品之间的关联关系，被广泛应用到商业挖掘和网络安全等领域中。频繁项集是指经常出现在一起的物品的集合，关联规则暗示着两种物品之间可能存在很强的关系。

8. K-Means

K-Means 算法是一个聚类算法。你可以这么理解，最终我想把物体划分成 K 类。假设每个类别里面，都有个“中心点”，即意见领袖，它是这个类别的核心。现在我有一个新点要归类，这时候就只要计算这个新点与 K 个中心点的距离，距离哪个中心点近，就变成了哪个类别。

9. EM

EM 算法也叫最大期望算法，是求参数的最大似然估计的一种方法。原理是这样的：假设我们想要评估参数 A 和参数 B，在开始状态下二者都是未知的，并且知道了 A 的信息就可以得到 B 的信息，反过来知道了 B 也就得到了 A。可以考虑首先赋予 A 某个初值，以此得到 B 的估值，然后从 B 的估值出发，重新估计 A 的取值，这个过程一直持续到收敛为止。

EM 算法经常用于聚类和机器学习领域中。

10. PageRank

PageRank 起源于论文影响力的计算方式，如果一篇文论被引入的次数越多，就代表这篇论文的影响力越强。同样 PageRank 被 Google 创造性地应用到了网页权重的计算中：当一个页面链出的页面越多，说明这个页面的“参考文献”越多，当这个页面被链入的频率越高，说明这个页面被引用的次数越高。基于这个原理，我们可以得到网站的权重划分。

算法可以说是数据挖掘的灵魂，也是最精华的部分。这 10 个经典算法在整个数据挖掘领域中的得票最高的，后面的一些其他算法也基本上都是在这个基础上进行改进和创新。今天你先对十大算法有一个初步的了解，你只需要做到心中有数就可以了，具体内容不理解没有关系，后面我会详细给你进行讲解。

数据挖掘的数学原理

我说了这么多数据挖掘中的经典算法，但是如果你不了解概率论和数理统计，还是很难掌握算法的本质；如果你不懂线性代数，就很难理解矩阵和向量运作在数据挖掘中的价值；如果你没有最优化方法的概念，就对迭代收敛理解不深。所以说，想要更深刻地理解数据挖掘的方法，就非常有必要了解它后背的数学原理。

1. 概率论与数理统计

概率论在我们上大学的时候，基本上都学过，不过大学里老师教的内容，偏概率的多一些，统计部分讲得比较少。在数据挖掘里使用到概率论的地方就比较多了。比如条件概率、独立性的概念，以及随机变量、多维随机变量的概念。

很多算法的本质都与概率论相关，所以说概率论与数理统计是数据挖掘的重要数学基础。

2. 线性代数

向量和矩阵是线性代数中的重要知识点，它被广泛应用到数据挖掘中，比如我们经常会把对象抽象为矩阵的表示，一幅图像就可以抽象出来是一个矩阵，我们也经常计算特征值和特征向量，用特征向量来近似代表物体的特征。这个是大数据降维的基本思路。

基于矩阵的各种运算，以及基于矩阵的理论成熟，可以帮我们解决很多实际问题，比如 PCA 方法、SVD 方法，以及 MF、NMF 方法等在数据挖掘中都有广泛的应用。

3. 图论

社交网络的兴起，让图论的应用也越来越广。人与人的关系，可以用图论上的两个节点来进行连接，节点的度可以理解为一个人的朋友数。我们都听说过人脉的六度理论，在 Facebook 上被证明平均一个人与另一个人的连接，只需要 3.57 个人。当然图论对于网络结构的分析非常有效，同时图论也在关系挖掘和图像分割中有重要的作用。

4. 最优化方法

最优化方法相当于机器学习中自我学习的过程，当机器知道了目标，训练后与结果存在偏差就需要迭代调整，那么最优化就是这个调整的过程。一般来说，这个学习和迭代的过程是漫长、随机的。最优化方法的提出就是用更短的时间得到收敛，取得更好的效果。

总结

今天我列了下学习数据挖掘你要掌握的知识清单，只有你对数据挖掘的流程、算法、原理有更深的理解，你才能在实际工作中更好地运用，我将在后面的章节中对它们进行一一介绍。

最后给你留道思考题吧。

今天我给你讲了如何学习数据挖掘，你从中有什么样的体会呢？如果某电商网站想挖掘商品之间的关联关系，从而提升销售额，你觉得可以采用上面的哪个算法？为什么？

极客时间版权所有: https://time.geekbang.org/column/article/73397

今天我们的学习正式开始，我想先给你一张数据分析的全景图，让你对后面的学习做到心中有数。

现在，你已经知道了数据分析在现代社会中的重要地位。掌握数据，就是掌握规律。当你了解了市场数据，对它进行分析，就可以得到市场规律。当你掌握了产品自身的数据，对它进行分析，就可以了解产品的用户来源、用户画像等等。所以说数据是个全新的视角。数据分析如此重要，它不仅是新时代的“数据结构 + 算法”，也更是企业争夺人才的高地。

当我们谈论数据分析的时候，都在讲些什么呢？

这里我可以把数据分析分成三个重要的组成部分。

1. 数据采集。它是我们的原材料，也是最“接地气”的部分，因为任何分析都要有数据源。
2. 数据挖掘。它可以说是最“高大上”的部分，也是整个商业价值所在。之所以要进行数据分析，就是要找到其中的规律，来指导我们的业务。因此数据挖掘的核心是挖掘数据的商业价值，也就是我们所谈的商业智能 BI。
3. 数据可视化。它可以说是数据领域中万金油的技能，可以让我们直观地了解到数据分析的结果。

下面我来一一为你讲解一下这三个重要的部分。

数据采集

在数据采集部分中，你通常会和数据源打交道，然后使用工具进行采集。

在专栏里，我会告诉你都有哪些常用的数据源，以及如何获取它们。另外在工具使用中，你也将掌握“八爪鱼”这个自动抓取的神器，它可以帮你抓取 99% 的页面源。当然我也会教你如何编写 Python 爬虫。掌握 Python 爬虫的乐趣是无穷的。它不仅能让你获取微博上的热点评论，自动下载例如“王祖贤”的海报，还能自动给微博加粉丝，让你掌握自动化的快感。

数据挖掘

第二个部分是数据挖掘，它可以说是知识型的工程，相当于整个专栏中的“算法”部分。首先你要知道它的基本流程、十大算法、以及背后的数学基础。

这一部分我们会接触到一些概念，比如关联分析，Adaboost 算法等等，你可能对这些概念还是一知半解，没有关系，我会详细为你介绍这些“朋友”。

每讲完一个算法原理，我都会带你做一个项目的实战，我精选了一些典型的、有趣的项目，比如对泰坦尼克号乘客进行生存预测、对文档进行自动分类、以及导演是如何选择演员的等等。

掌握了数据挖掘，就好比手握水晶球一样，它会通过历史数据，告诉你未来会发生什么。当然它也会告诉你这件事发生的置信度是怎样的，置信度这个词你先记住就可以了，后面我们来学习它具体代表什么。

数据可视化

第三个就是数据可视化，这是一个非常重要的步骤，也是我们特别感兴趣的一个步骤。数据往往是隐性的，尤其是当数据量大的时候很难感知，可视化可以帮我们很好地理解这些数据的结构，以及分析结果的呈现。

如何进行数据可视化呢？有两种方法。

第一种就是使用 Python。在 Python 对数据进行清洗、挖掘的过程中，我们可以使用 Matplotlib、Seaborn 等第三方库进行呈现。

第二种就是使用第三方工具。如果你已经生成了 csv 格式文件，想要采用所见即所得的方式进行呈现，可以采用微图、DataV、Data GIF Maker 等第三方工具，它们可以很方便地对数据进行处理，还可以帮你制作呈现的效果。

数据采集和数据可视化的原理简单，容易理解。这两个部分注重的是工具的掌握，所以我会把重点放在讲解工具以及应用实战上。

虽然这些理论我会给你一一讲解，但纸上得来终觉浅，绝知此事要躬行。手拿地图，我们知道要去哪里，但是怎么去呢？我认为学习数据分析最好的方法是：在工具中灵活运用，在项目中加深理解。

修炼指南

刚才我们讲了数据分析全景图，包括数据采集、数据挖掘、数据可视化这三个部分。你可能觉得东西很多，无从下手，或者感觉数据挖掘涉及好多算法，有点“高深莫测”，掌握起来是不是会吃力。其实这些都是不必要的烦恼。

开篇词里我给你介绍了 MAS 学习法，有了这个方法，学习数据分析就是从“思维”到“工具”再到“实践”的一个过程。今天我会从更多的角度来和你分享我的学习经验，我们可以把今天的内容叫作“修炼指南”。

借用傅盛的话来说，人与人最大的差别在于“认知”，所谓成长就是认知的升级。

很多人存在对“认知“的误解，认为认知不就是概念么？那么你有没有想过，针对同一个概念，为什么不同的人掌握的程度是不一样的呢？

我们只有把知识转化为自己的语言，它才真正变成了我们自己的东西。这个转换的过程，就是认知的过程。

那么如何提升自己的学习吸收能力呢？简单地说，就是要“知行合一”。

如果说认知是大脑，那么工具就好比我们的双手，数据工程师和算法科学家每天打交道最多的就是工具。

如果你开始做数据分析的项目，你脑海中已经思考好了数据挖掘的算法模型，请牢记下面这两点原则。

1. 不重复造轮子

举个数据采集的例子，我见过很多公司，都有数据采集的需求，他们认为某些工具不能满足他们个性化的需求，因此决定招人专门做这项工作。而结果怎样呢？做了 1 年多的实践，工资投入几十万，结果发现 Bug 一大堆，最后还是选择了第三方工具。耗时耗力，还没什么成效。

一个模型是否有相关的类库可以使用——这几乎是每个程序员入行被告知的第一条准则。我也会对新人反复灌输这个概念。大部分情况下你都能找到类库来完成你的想法。

2. 工具决定效率

“不要重复造轮子”意味着首先需要找到一个可以用的轮子，也就是工具。我们该如何选择呢？

这取决于你要做的工作，工具没有好坏之分，只有适合与否。除去研究型的工作，大部分情况下，工程师会选择使用者最多的工具。因为：Bug 少、文档全、案例多。

比如 Python 在处理数据挖掘上就有很多第三方库，这些库都有大量的用户和帮助文档可以帮助你来上手。

在后面的课程里，我会给你介绍最常用的工具，这些工具会让你的数据挖掘事半功倍。

选择好工具之后，你要做的就是积累 “资产”了。我们很难记住大段的知识点，也背不下来工具的指令，但是我们通常能记住故事、做过的项目、做过的题目。这些题目和项目是你最先行的“资产”。

如何快速积累这些“资产”呢？这里我送你三个字：熟练度。

把题目完成只是第一步，关键在于训练我们工具使用的“熟练度”。

高中的时候，有一次我做“八皇后”的问题，第一次解答花了一个小时的时间。当时老师明确告诉我必须在 20 分钟内完成，我不敢相信，从解题、思考、动手，最后完成，1 个小时不算慢。但是后来我调整了思考的结构。最后我 6 分钟就可以完成那道题。

当熟练度增加的时候，你的思考认知模型也在逐渐提升。所以专栏中，我给你做了一个 “专属题库”，在专属题库中你可以进行自我评测，当然我也会对这些练习题进行讲解。在工作篇中，我也会和你一起分享面试技巧、探讨职场上的晋升之路。

总结

认知三步曲，从认知到工具，再到实战，是我最想给你分享的学习建议。我看到过很多同学上课的模式，以及很多人工作中的思考模式，我特别认同“人与人最大的区别是在认知”这个观点。

他们很听老师的理论，但是这些理论最后又都还给了老师。所以我希望你在后面的 15 周学习里可以做到以下几点。

• 记录下你每天的认知。尤其是每次课程后，对知识点的自我理解。
• 这些认知对应工具的哪些操作。用工具来表达你对知识点的掌握，并用自己的语言记录下这些操作笔记。
• 做更多练习来巩固你的认知。我们学习的内容对于大部分外人来说，就像“开车”一样，很酷。我们学习的内容，对于要掌握的人来说，也像“开车”一样，其实并不难，而且很多人已经上路了。你需要的就是更多的练习。

极客时间版权所有: https://time.geekbang.org/column/article/73270

你好，我是黄申。

今天我们来说一个和编程结合得非常紧密的数学概念。在解释这个重要的概念之前，我们先来看个有趣的小故事。

古印度国王舍罕酷爱下棋，他打算重赏国际象棋的发明人宰相西萨·班·达依尔。这位聪明的大臣指着象棋盘对国王说：“陛下，我不要别的赏赐，请您在这张棋盘的第一个小格内放入一粒麦子，在第二个小格内放入两粒，第三小格内放入给四粒，以此类推，每一小格内都比前一小格加一倍的麦子，直至放满 64 个格子，然后将棋盘上所有的麦粒都赏给您的仆人我吧！”

国王自以为小事一桩，痛快地答应了。可是，当开始放麦粒之后，国王发现，还没放到第二十格，一袋麦子已经空了。随着，一袋又一袋的麦子被放入棋盘的格子里，国王很快看出来，即便拿来全印度的粮食，也兑现不了对达依尔的诺言。

放满这 64 格到底需要多少粒麦子呢？这是个相当相当大的数字，想要手动算出结果并不容易。如果你觉得自己厉害，可以试着拿笔算算。其实，这整个算麦粒的过程，在数学上，是有对应方法的，这也正是我们今天要讲的概念：迭代法（Iterative Method）。

到底什么是迭代法？

迭代法，简单来说，其实就是不断地用旧的变量值，递推计算新的变量值。

我这么说可能还是比较抽象，不容易理解。我们还回到刚才的故事。大臣要求每一格的麦子都是前一格的两倍，那么前一格里麦子的数量就是旧的变量值，我们可以先记作 Xn−1Xn−1；而当前格子里麦子的数量就是新的变量值，我们记作 XnXn。这两个变量的递推关系就是这样的：

如果你稍微有点编程经验，应该能发现，迭代法的思想，很容易通过计算机语言中的循环语言来实现。你知道，计算机本身就适合做重复性的工作，我们可以通过循环语句，让计算机重复执行迭代中的递推步骤，然后推导出变量的最终值。

那接下来，我们就用循环语句来算算，填满格子到底需要多少粒麦子。我简单用 Java 语言写了个程序，你可以看看。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class Lesson3_1 {
    /**
    * @Description: 算算舍罕王给了多少粒麦子
    * @param grid- 放到第几格
    * @return long- 麦粒的总数
    */
 
    public static long getNumberOfWheat(int grid) {
     
     long sum = 0;      // 麦粒总数
     long numberOfWheatInGrid = 0;  // 当前格子里麦粒的数量
     
     numberOfWheatInGrid = 1;  // 第一个格子里麦粒的数量
     sum += numberOfWheatInGrid;  
     
     for (int i = 2; i <= grid; i ++) {
      numberOfWheatInGrid *= 2;   // 当前格子里麦粒的数量是前一格的 2 倍
      sum += numberOfWheatInGrid;   // 累计麦粒总数
     }
     
     return sum;
 
    }
}

下面是一段测试代码，它计算了到第 63 格时，总共需要多少麦粒。

1
2
3

public static void main(String[] args) {
System.out.println(String.format(" 舍罕王给了这么多粒：%d",   Lesson3_1.getNumberOfWheat(63)));
}

计算的结果是 9223372036854775807，多到数不清了。我大致估算了一下，一袋 50 斤的麦子估计有 130 万粒麦子，那么 9223372036854775807 相当于 70949 亿袋 50 斤的麦子！

这段代码有两个地方需要注意。首先，用于计算每格麦粒数的变量以及总麦粒数的变量都是 Java 中的 long 型，这是因为计算的结果实在是太大了，超出了 Java int 型的范围；第二，我们只计算到了第 63 格，这是因为计算到第 64 格之后，总数已经超过 Java 中 long 型的范围。

迭代法有什么具体应用？

看到这里，你可能大概已经理解迭代法的核心理念了。迭代法在无论是在数学，还是计算机领域都有很广泛的应用。大体上，迭代法可以运用在以下几个方面：

• 求数值的精确或者近似解。典型的方法包括二分法（Bisection method）和牛顿迭代法（Newton’s method）。
• 在一定范围内查找目标值。典型的方法包括二分查找。
• 机器学习算法中的迭代。相关的算法或者模型有很多，比如 K- 均值算法（K-means clustering）、PageRank 的马尔科夫链（Markov chain）、梯度下降法（Gradient descent）等等。迭代法之所以在机器学习中有广泛的应用，是因为很多时候机器学习的过程，就是根据已知的数据和一定的假设，求一个局部最优解。而迭代法可以帮助学习算法逐步搜索，直至发现这种解。

这里，我详细讲解一下求数值的解和查找匹配记录这两个应用。

1. 求方程的精确或者近似解

迭代法在数学和编程的应用有很多，如果只能用来计算庞大的数字，那就太“暴殄天物”了。迭代还可以帮助我们进行无穷次地逼近，求得方程的精确或者近似解。

比如说，我们想计算某个给定正整数 n（n>1）的平方根，如果不使用编程语言自带的函数，你会如何来实现呢？

假设有正整数 n，这个平方根一定小于 n 本身，并且大于 1。那么这个问题就转换成，在 1 到 n 之间，找一个数字等于 n 的平方根。

我这里采用迭代中常见的二分法。每次查看区间内的中间值，检验它是否符合标准。

举个例子，假如我们要找到 10 的平方根。我们需要先看 1 到 10 的中间数值，也就是 11/2=5.5。5.5 的平方是大于 10 的，所以我们要一个更小的数值，就看 5.5 和 1 之间的 3.25。由于 3.25 的平方也是大于 10 的，继续查看 3.25 和 1 之间的数值，也就是 2.125。这时，2.125 的平方小于 10 了，所以看 2.125 和 3.25 之间的值，一直继续下去，直到发现某个数的平方正好是 10。

我把具体的步骤画成了一张图，你可以看看。

我这里用 Java 代码演示一下效果，你可以结合上面的讲解，来理解迭代的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public class Lesson3_2 {
 
 /**
    * @Description: 计算大于 1 的正整数之平方根
    * @param n- 待求的数, deltaThreshold- 误差的阈值, maxTry- 二分查找的最大次数
    * @return double- 平方根的解
    */
    public static double getSqureRoot(int n, double deltaThreshold, int maxTry) {
     
     if (n <= 1) {
      return -1.0;
     }
     
     double min = 1.0, max = (double)n;
     for (int i = 0; i < maxTry; i++) {
      double middle = (min + max) / 2;
      double square = middle * middle;
      double delta = Math.abs((square / n) - 1);
      if (delta <= deltaThreshold) {
       return middle;
      } else {
       if (square > n) {
        max = middle;
       } else {
        min = middle;
       }
      }
     }
     
     return -2.0;
 
    }
}

这是一段测试代码，我们用它来找正整数 10 的平方根。如果找不到精确解，我们就返回一个近似解。

1
2
3
4
5
6
7
8
9
10
11
12
13

public static void main(String[] args) {
  
  int number = 10;
  double squareRoot = Lesson3_2.getSqureRoot(number, 0.000001, 10000);
  if (squareRoot == -1.0) {
   System.out.println(" 请输入大于 1 的整数 ");
  } else if (squareRoot == -2.0) {
   System.out.println(" 未能找到解 ");
  } else {
   System.out.println(String.format("%d 的平方根是 %f", number, squareRoot));
  }
  
 }

这段代码的实现思想就是我前面讲的迭代过程，这里面有两个小细节我解释下。

第一，我使用了 deltaThreshold 来控制解的精度。虽然理论上来说，可以通过二分的无限次迭代求得精确解，但是考虑到实际应用中耗费的大量时间和计算资源，绝大部分情况下，我们并不需要完全精确的数据。

第二，我使用了 maxTry 来控制循环的次数。之所以没有使用 while(true) 循环，是为了避免死循环。虽然，在这里使用 deltaThreshold，理论上是不会陷入死循环的，但是出于良好的编程习惯，我们还是尽量避免产生的可能性。

说完了二分迭代法，我这里再简单提一下牛顿迭代法。这是牛顿在 17 世纪提出的一种方法，用于求方程的近似解。这种方法以微分为基础，每次迭代的时候，它都会去找到比上一个值 x0x0 更接近的方程的根，最终找到近似解。该方法及其延伸也被应用在机器学习的算法中，在之后机器学习中的应用中，我会具体介绍这个算法。

2. 查找匹配记录

二分法中的迭代式逼近，不仅可以帮我们求得近似解，还可以帮助我们查找匹配的记录。我这里用一个查字典的案例来说明。

在自然语言处理中，我们经常要处理同义词或者近义词的扩展。这时，你手头上会有一个同义词 / 近义词的词典。对于一个待查找的单词，我们需要在字典中找出这个单词，以及它所对应的同义词和近义词，然后进行扩展。比如说，这个字典里有一个关于“西红柿”的词条，其同义词包括了“番茄”和“tomato”。

那么，在处理文章的时候，当我们看到了“西红柿”这个词，就去字典里查一把，拿出“番茄”“tomato”等等，并添加到文章中作为同义词 / 近义词的扩展。这样的话，用户在搜索“西红柿”这个词的时候，我们就能确保出现“番茄”或者“tomato”的文章会被返回给用户。

乍一看到这个任务的时候，你也许想到了哈希表。没错，哈希表是个好方法。不过，如果不使用哈希表，你还有什么其他方法呢？这里，我来介绍一下，用二分查找法进行字典查询的思路。

第一步，将整个字典先进行排序（假设从小到大）。二分法中很关键的前提条件是，所查找的区间是有序的。这样才能在每次折半的时候，确定被查找的对象属于左半边还是右半边。

第二步，使用二分法逐步定位到被查找的单词。每次迭代的时候，都找到被搜索区间的中间点，看看这个点上的单词，是否和待查单词一致。如果一致就返回；如果不一致，要看被查单词比中间点上的单词是小还是大。如果小，那说明被查的单词如果存在字典中，那一定在左半边；否则就在右半边。

第三步，根据第二步的判断，选择左半边或者后半边，继续迭代式地查找，直到范围缩小到单个的词。如果到最终仍然无法找到，则返回不存在。

当然，你也可以对单词进行从大到小的排序，如果是那样，在第二步的判断就需要相应地修改一下。

我把在 a 到 g 的 7 个字符中查找 f 的过程，画成了一张图，你可以看看。

这个方法的整体思路和二分法求解平方根是一致的，主要区别有两个方面：第一，每次判断是否终结迭代的条件不同。求平方根的时候，我们需要判断某个数的平方是否和输入的数据一致。而这里，我们需要判断字典中某个单词是否和待查的单词相同。第二，二分查找需要确保被搜索的空间是有序的。

我把具体的代码写出来了，你可以看一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

import java.util.Arrays;
 
public class Lesson3_3 {
 
 /**
    * @Description: 查找某个单词是否在字典里出现
    * @param dictionary- 排序后的字典, wordToFind- 待查的单词
    * @return boolean- 是否发现待查的单词
    */
    public static boolean search(String[] dictionary, String wordToFind) {
     
     if (dictionary == null) {
      return false;
     }
     
     if (dictionary.length == 0) {
      return false;
     }
     
     int left = 0, right = dictionary.length - 1;
     while (left <= right) {
      int middle = (left + right) / 2;
      if (dictionary[middle].equals(wordToFind)) {
       return true;
      } else {
       if (dictionary[middle].compareTo(wordToFind) > 0) {
        right = middle - 1;
       } else {
        left = middle + 1;
       }
      }
     }
     
     return false;
 
    }
 
}

我测试代码首先建立了一个非常简单的字典，然后使用二分查找法在这个字典中查找单词“i”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public static void main(String[] args) {
  
  
  String[] dictionary = {"i", "am", "one", "of", "the", "authors", "in", "geekbang"};
  
  Arrays.sort(dictionary);
 
  String wordToFind = "i";
  
  boolean found = Lesson3_3.search(dictionary, wordToFind);
  if (found) {
   System.out.println(String.format(" 找到了单词 %s", wordToFind));
  } else {
   System.out.println(String.format(" 未能找到单词 %s", wordToFind));
  }
  
 }

说的这两个例子，都属于迭代法中的二分法，我在第一节的时候说过，二分法其实也体现了二进制的思想。

小结

到这里，我想你对迭代的核心思路有了比较深入的理解。

实际上，人类并不擅长重复性的劳动，而计算机却很适合做这种事。这也是为什么，以重复为特点的迭代法在编程中有着广泛的应用。不过，日常的实际项目可能并没有体现出明显的重复性，以至于让我们很容易就忽视了迭代法的使用。所以，你要多观察问题的现象，思考其本质，看看不断更新变量值或者缩小搜索的区间范围，是否可以获得最终的解（或近似解、局部最优解），如果是，那么你就可以尝试迭代法。

思考题

在你曾经做过的项目中，是否使用过迭代法？如果有，你觉得迭代法最大的特点是什么？如果还没用过，你想想看现在的项目中是否有可以使用的地方？

极客时间版权所有: https://time.geekbang.org/column/article/72243

你好，我是黄申。今天我们来聊聊“余数”。

提起来余数，我想你肯定不陌生，因为我们生活中就有很多很多与余数相关的例子。

比如说，今天是星期三，你想知道 50 天之后是星期几，那你可以这样算，拿 50 除以 7（因为一个星期有 7 天），然后余 1，最后在今天的基础上加一天，这样你就能知道 50 天之后是星期四了。

再比如，我们做 Web 编程的时候，经常要用到分页的概念。如果你要展示 1123 条数据，每页 10 条，那该怎么计算总共的页数呢？我想你肯定是拿 1123 除以 10，最后得到商是 112，余数是 3，所以你的总页数就是 112+1=113，而最后的余数就是多出来，凑不够一页的数据。

看完这几个例子，不知道你有没有发现，余数总是在一个固定的范围内。

比如你拿任何一个整数除以 7，那得到的余数肯定是在 0～6 之间的某一个数。所以当我们知道 1900 年的 1 月 1 日是星期一，那便可以知道这一天之后的第 1 万天、10 万天是星期几，是不是很神奇？

你知道，整数是没有边界的，它可能是正无穷，也可能是负无穷。但是余数却可以通过某一种关系，让整数处于一个确定的边界内。我想这也是人类发明星期或者礼拜的初衷吧，任你时光变迁，我都是以 7 天为一个周期，“周”而复始地过着确定的生活。因为从星期的角度看，不管你是哪一天，都会落到星期一到星期日的某一天里。

我们再拿上面星期的例子来看。假如今天是星期一，从今天开始的 100 天里，都有多少个星期呢？你拿 100 除以 7，得到商 14 余 2，也就是说这 100 天里有 14 周多 2 天。换个角度看，我们可以说，这 100 天里，你的第 1 天、第 8 天、第 15 天等等，在余数的世界里都被认为是同一天，因为它们的余数都是 1，都是星期一，你要上班的日子。同理，第 2 天、第 9 天、第 16 天余数都是 2，它们都是星期二。

这些数的余数都是一样的，所以被归类到了一起，有意思吧？是的，我们的前人早已注意到了这一规律或者特点，所以他们把这一结论称为同余定理。简单来说，就是两个整数 a 和 b，如果它们除以正整数 m 得到的余数相等，我们就可以说 a 和 b 对于模 m 同余。

也就是说，上面我们说的 100 天里，所有星期一的这些天都是同余的，所有星期二的这些天就是同余的，同理，星期三、星期四等等这些天也都是同余的。

还有，我们经常提到的奇数和偶数，其实也是同余定理的一个应用。当然，这个应用里，它的模就是 2 了，2 除以 2 余 0，所以它是偶数；3 除以 2 余 1，所以它是奇数。2 和 4 除以 2 的余数都是 0，所以它们都是一类，都是偶数。3 和 5 除以 2 的余数都是 1，所以它们都是一类，都是奇数。

你肯定会说，同余定理就这么简单吗，这个定理到底有什么实际的用途啊？其实，我上面已经告诉你答案了，你不妨先自己思考下，同余定理的意义到底是什么。

简单来说，同余定理其实就是用来分类的。你知道，我们有无穷多个整数，那怎么能够全面、多维度地管理这些整数？同余定理就提供了一个思路。

因为不管你的模是几，最终得到的余数肯定都在一个范围内。比如我们上面除以 7，就得到了星期几；我们除以 2，就得到了奇偶数。所以按照这种方式, 我们就可以把无穷多个整数分成有限多个类。

这一点，在我们的计算机中，可是有大用途。

哈希（Hash）你应该不陌生，在每个编程语言中，都会有对应的哈希函数。哈希有的时候也会被翻译为散列，简单来说，它就是将任意长度的输入，通过哈希算法，压缩为某一固定长度的输出。这话听着是不是有点耳熟？我们上面的求余过程不就是在做这事儿吗？

举个例子，假如你想要快速读写 100 万条数据记录，要达到高速地存取，最理想的情况当然是开辟一个连续的空间存放这些数据，这样就可以减少寻址的时间。但是由于条件的限制，我们并没有能够容纳 100 万条记录的连续地址空间，这个时候该怎么办呢？

我们可以考察一下，看看系统是否可以提供若干个较小的连续空间，而每个空间又能存放一定数量的记录。比如我们找到了 100 个较小的连续空间，也就是说，这些空间彼此之间是被分隔开来的，但是内部是连续的，并足以容纳 1 万条记录连续存放，那么我们就可以使用余数和同余定理来设计一个散列函数，并实现哈希表的结构。

那这个函数应该怎么设计呢？你可以先停下来思考思考，提醒你下，你可以再想想星期几的那个例子，因为这里面用的就是余数的思想。

下面是我想到的一种方法：

在这个公式中，x 表示等待被转换的数值，而 size 表示有限存储空间的大小，mod 表示取余操作。通过余数，你就能将任何数值，转换为有限范围内的一个数值，然后根据这个新的数值，来确定将数据存放在何处。

具体来说，我们可以通过记录标号模 100 的余数，指定某条记录存放在哪个空间。这个时候，我们的公式就变成了这样：

假设有两条记录，它们的记录标号分别是 1 和 101。我们把这些模 100 之后余数都是 1 的，存放到第 1 个可用空间里。以此类推，将余数为 2 的 2、102、202 等，存放到第 2 个可用空间，将 100、200、300 等存放到第 100 个可用空间里。

这样，我们就可以根据求余的快速数字变化，对数据进行分组，并把它们存放到不同的地址空间里。而求余操作本身非常简单，因此几乎不会增加寻址时间。

除此之外，为了增加数据散列的随机程度，我们还可以在公式中加入一个较大的随机数 MAX，于是，上面的公式就可以写成这样：

我们假设随机数 MAX 是 590199，那么我们针对标号为 1 的记录进行重新计算，最后的计算结果就是 0，而针对标号 101 的记录，如果随机数 MAX 取 627901，对应的结果应该是 2。这样先前被分配到空间 1 的两条记录，在新的计算公式作用下，就会被分配到不同的可用空间中。

你可以尝试记录 2 和 102，或者记录 100 和 200，最后应该也是同样的情况。你会发现，使用了 MAX 这个随机数之后，被分配到同一个空间中的记录就更加“随机”，更适合需要将数据重新洗牌的应用场景，比如加密算法、MapReduce 中的数据分发、记录的高速查询和定位等等。

让我以加密算法为例，在这里面引入 MAX 随机数就可以增强加密算法的保密程度，是不是很厉害？举个例子，比如说我们要加密一组三位数，那我们设定一个这样的加密规则：

1. 先对每个三位数的个、十和百位数，都加上一个较大的随机数。
2. 然后将每位上的数都除以 7，用所得的余数代替原有的个、十、百位数；
3. 最后将第一位和第三位交换。

这就是一个基本的加密变换过程。

假如说，我们要加密数字 625，根据刚才的规则，我们来试试。假设随机数我选择 590127。那百、十和个位分别加上这个随机数，就变成了 590133，590129，590132。然后，三位分别除以 7 求余后得到 5，1，4。最终，我们可以得到加密后的数字就是 415。因为加密的人知道加密的规则、求余所用的除数 7、除法的商、以及所引入的随机数 590127，所以当拿到 415 的时候，加密者就可以算出原始的数据是 625。是不是很有意思？

小结

到这里，余数的所有知识点我们都讲完了。我想在此之前，你肯定是知道余数，也明白怎么求余。但对于余数的应用不知道你之前是否有思考过呢？我们经常说，数学是计算机的基础，在余数这个小知识点里，我们就能找到很多的应用场景，比如我前面介绍的散列函数、加密算法，当然，也还有我们没有介绍到的，比如循环冗余校验等等。

余数只是数学知识中的沧海一粟。你在中学或者大学的时候，肯定接触过很多的数学知识和定理，编程的时候也会经常和数字、公式以及数据打交道，但是真正学懂数学的人却没几个。希望我们可以从余数这个小概念开始，让你认识到数学思想其实非常实用，用好这些知识，对你的编程，甚至生活都有意想不到的作用。

思考题

你可以想想，在生活和编程中，还有哪些地方用到了余数的思想呢？

极客时间版权所有: https://time.geekbang.org/column/article/72163