《数据密集型应用》里面的一页，这里只是再做诠释而已。

两个表格，一个 User Activity Mapper 以及一个 User Database Mapper 表，可以这么定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
CREATE TABLE user_activity (
    u_id INT,
    status VARCHAR(10) DEFAULT "loaded",
    url VARCHAR(100) DEFAULT "/",

    FOREIGN KEY (u_id) REFERENCES user(id)
);

CREATE TABLE user (
    id INT NOT NULL,
    email VARCHAR(50) NOT NULL,
    date_of_birth DATETIME DEFAULT "1970-01-01 00:00:00",

    PRIMARY KEY (id)
);

想要做一个连接操作：

1
2
3
4
5
6
SELECT
    u.date_of_birth AS dob,
    ua.url AS url
FROM user AS u
LEFT JOIN user_activity AS ua
ON u.id = ua.u_id

反正没啥目的，就是为了把 dob 和访问的 url 绑在一起，看看有没有啥关联，这个操作就可以使用 MapReduce 的思想考虑。

这个 SQL 有连接操作，而且是等值连接，那么如何处理等值是一个问题。（当然，等值是肯定比不等要好的。

单机

单个机器的内存和计算能力是有限的，假设 user 表的大小为 M，user_activity 表大小为 N，我关系数据库理论学得不是很好，大概涂一下：

假设我们 user_activity 表的 u_id 是有序的，使用 B+Tree 存储，每个节点的大小为 16KB，由于一个 id 是 32 bits，也就是 4 Bytes，那么差不多有：

假设是三层 B+Tree，那么 $NodeNum_{layer\ 2} = 1638 \times 1638 = 2683044$，此后第三层就会有 $2683044 \times 16\ KB= 42,928,704 KB$ 的空间。
假设 user 表就这么 3 个属性，status 和 url 加上主键平均算下来 50 B（其实根本不可能，我定义的时候就写大了），那也还可以存储 879,179,857 条记录。再假设这三层 B+Tree 是存满了的。$N = 879179857$，至于另外一个表，是和学生个数相关的，肯定两层 B+Tree 就没问题了。

由于是 B+Tree，所以在 u_id 确定之后，在一个小表里面找 id 应该是一件比较快乐的事情，而且 B+Tree 就两层，估计找一次不会很久。

我不清楚在 id & u_id 都明确排序，并且存在外键关系的情况下还会不会每次都傻傻地从根节点开始，我就取个 3 作为每次查找花费的时间吧，我感觉是少了。

MapReduce

假设把整个任务划分成 100 份，交给这么多台机器同时处理，第一层的 100 个机器每个都获得了 user_activity 中顺序存储的（不知道是不是顺序的，哎，真的一点都不懂）8791798 个记录，各自遍历一遍，做了一个类似 GROUP BY id 的操作。

假设 $id \in [1850001, 1856999]$，第二层也是 100 个机器，第 n 个机器负责 $[1850001 + n \times \dfrac{1856999-1850001+1}{100}, 1850001 + (n+1) \times \dfrac{1856999-1850001+1}{100}]$ 这些学号。第一层的机器会根据第二层打算处理的学号，发送特定的记录。第二层收到这些 user_activity 中的记录，会直接从 user 表里面取出来，这个时间还是算做 3 吧，但我觉得算长了，每台机器只需要操作 70 次，接下来只是做一个内存中的 "append" 操作就可以了。

所以差不多是：

emm，怎么说呢，我觉得这件事儿就是把 乘法 降级成了 加法，辣鸡机器越多，处理速度提升地越明显，因为内存和计算资源在一台机器上是有限的，同时还需要 Infinite Bandwidth, Low Latency 等等这些分布式系统友好的假设……