什么是big table? —— 分布式数据库

文件系统与数据库

文件系统：

操作：输入——/home/jiayi/test.txt ；输出——文件内容

但如果想改文件里的一点点内容，就比较麻烦了。需要打开文件、for循环扫描内容、找所需要的东西、改动、重新将全部东西都写入文件。所以文件系统只能提供一些简单的读写文件操作。但实际查询中有比较复杂的查询需求，所以我们需要一个更复杂的系统，建立在文件系统之上。也就是数据库系统。

数据库系统：

建立在文件系统之上
负责组织把一些数据存到文件系统
对外的接口比较方便操作数据

设计数据库系统

scenario 场景

需求

查询：key(年龄 + 年级)
返回：value(姓名)

存储

数据库怎么存储？以表的形式？——并不是！

数据最终都会存到文件里面，是类似一种json格式的。

查询

在文件里面，如何更好地支持查询操作呢？

方法1：将全部文件存到内存里面，内存查询——内存根本放不下啊。
方法2：在硬盘的文件的基础上进行二分查找：每次拿出mid读到内存里。这涉及到GFS中的外排序。

修改

如果要修改一个东西，怎么操作呢？可能有三种方法：

直接在文件里修改很难做到。如果原来是4个字节，现在修改成8个字节。那么修改之后还需要改动其它的位置。
读取整个文件，等改好了，重新写入覆盖原文件非常耗费时间。每次都要读出写入。
不修改，直接将这条数据append在文件后面这样写起来很快。如下图所示：

姓名："a", 颜值:"5"，身高："160"，时间："1"
姓名："b", 颜值:"6"，身高："130"，时间："2"
姓名："c", 颜值:"2"，身高："170"，时间："3"
    
修改a的颜值为10
姓名："a", 颜值:"5"，身高："160"，时间："1"
姓名："b", 颜值:"6"，身高："130"，时间："2"
姓名："c", 颜值:"2"，身高："170"，时间："3"
姓名："a", 颜值:"10"，身高："160"，时间："4"

但是读的时候没有顺序哇，就无法进行二分查找了！

解决方案：读的时候先扫旧的，然后再从append里面依次查找是否有修改后的内容。同时进行定期整理，以保证append的内容较少。

有没有一种方法，能即在读的时候二分查找，又能在写的时候append呢？—— 分块有序！

每一块都是内部有序
只有最后一块是无序的

如下所示：

姓名："c", 颜值:"2"，身高："170"，时间："3"
姓名："d", 颜值:"2"，身高："170"，时间："4"        有序块
==========================================
姓名："a", 颜值:"5"，身高："160"，时间："1"
姓名："b", 颜值:"6"，身高："130"，时间："2"        有序块
==========================================
姓名："d", 颜值:"4"，身高："170"，时间："5"        最后一块无序
姓名："b", 颜值:"8"，身高："130"，时间："6"
    
当最后一块满了的时候，把最后一块整理成有序即可

读取的时候，需要在每一块内进行二分查找

这样读和写相对来说就不会很慢了。但是问题来了，当块特别多的时候怎么办？—— 定期对有序块进行K路归并

完整的读写操作

写入：

要将linghuchong的value写成7
给最后一个文件file1写入linghuchong+value=7
当file1满了的时候（例如256M），将file1搞成有序。排序方法有两种：
1. 一开始就写到内存里——内存排序+1次硬盘写入
2. 先写入文件，然后等满了的时候读入内存进行快排——1次硬盘读+内存排序+1次硬盘写
3. 硬盘外部排序——有必要吗？并没有