最简单的 Key-Value 数据库

一个数据库最基本的功能只有两件事，就是读和写。当把数据交给数据库时，它应当把数据存储起来，而后当你向数据库要数据时，它需要把数据返回给你。

最简单的内存键值对数据库只需要短短三行代码就可以实现：

const db = new Map();
const get = (key: string) => db.get(key);
const set = (key: string, value: any) => db.set(key, value);

const db = new Map();
const get = (key: string) => db.get(key);
const set = (key: string, value: any) => db.set(key, value);

你可以使用 get 和 set 来作为对外的接口，利用 Map 作为存储实现。当然这种实现并没有什么大的用处。我们还需要将数据写入到硬盘上，否则进程一旦退出以后数据就全部丢失了，在 Node 中当然也提供了文件系统相关的接口，我们可以使用 fs 模块来实现这样的功能。

这里我们直接把数据序列化以后作为文本塞到文件的最后，同时把键和值用逗号分割。每当读取数据时，扫描这个文件来一行一行遍历查询键名。

import fs from 'fs';
import readline from 'readline';

const dbFile = './data.db';

const get = (key: string) => {
  const readable = fs.createReadStream(dbFile);
  const reader = readline.createInterface({ input: readable });
  return new Promise<string>(resolve => {
    let value: any;
    reader.on('line', line => {
      const [k, v] = line.split(',');
      if (k === key) {
        value = v;
      }
    });
    readable.on('end', () => {
      reader.close();
      resolve(value);
    });
  });
};

const set = (key: string, value: any) => {
  fs.appendFileSync(dbFile, `${key},${value}\n`);
};

import fs from 'fs';
import readline from 'readline';

const dbFile = './data.db';

const get = (key: string) => {
  const readable = fs.createReadStream(dbFile);
  const reader = readline.createInterface({ input: readable });
  return new Promise<string>(resolve => {
    let value: any;
    reader.on('line', line => {
      const [k, v] = line.split(',');
      if (k === key) {
        value = v;
      }
    });
    readable.on('end', () => {
      reader.close();
      resolve(value);
    });
  });
};

const set = (key: string, value: any) => {
  fs.appendFileSync(dbFile, `${key},${value}\n`);
};

然后我们简单的修改一下 eval 参数以接入 set 和 get 接口，这里我们先不管解析 SQL 语句之类的事情，而是使用了一个我们自定的简单的语法，

• set [key] [value]
• get [key]

语法的解析也是暂时假定所有的输入都是正确的格式，这样可以用非常简单的方式来实现：

const replServer = repl.start({
  // ...
  eval: async (evalCmd, _, __, callback) => {
    const cmd = evalCmd.trim();
    if (cmd.startsWith('set')) {
      const [, key, value] = cmd.split(' ');
      set(key, value);
      return callback(null, value);
    }
    if (cmd.startsWith('get')) {
      const [, key] = cmd.split(' ');
      const value = await get(key);
      return callback(null, value);
    }
    return callback(null, `Unrecognized command.`);
  },
});

const replServer = repl.start({
  // ...
  eval: async (evalCmd, _, __, callback) => {
    const cmd = evalCmd.trim();
    if (cmd.startsWith('set')) {
      const [, key, value] = cmd.split(' ');
      set(key, value);
      return callback(null, value);
    }
    if (cmd.startsWith('get')) {
      const [, key] = cmd.split(' ');
      const value = await get(key);
      return callback(null, value);
    }
    return callback(null, `Unrecognized command.`);
  },
});

再启动以后测试一下，可以看到已经成功了：

db.js >> set a aaa
'aaa'
db.js >> set b bbb
'bbb'
db.js >> get a
'aaa'
db.js >> set a ccc
'ccc'
db.js >> get a
'ccc'

db.js >> set a aaa
'aaa'
db.js >> set b bbb
'bbb'
db.js >> get a
'aaa'
db.js >> set a ccc
'ccc'
db.js >> get a
'ccc'

set 函数在简单的场景性能其实非常好，因为在文件尾部追加写入其实是很高效的，像很多日志的实现，都是一个 append-only 的文件，虽然还有像并发，容错等很多额外的事情要处理，但核心原理是一样的。

但对于读取数据的 get 操作，它的性能则非常糟糕，因为每次必须从头到尾扫描整个文件来进行查找。从算法的角度来说，它的复杂度是 O(N) 。也就是说随着数据量的增大，查找的时间也会线性增长。

当然你可能会想，那我们可以把 append 操作改为 prepend， 这样每次都把新的记录写在前面，查找时不需要遍历到结束了，只要找到了就可以停止并返回结果，但很可惜这样并没有改变它的线性复杂度。要解决这个问题，我们需要引入一个叫 索引 的额外结构，比如我们查汉语字典时，可以根据偏旁部首或者拼音，在目录中找到他们的大概位置，直接翻到那一页再仔细一条条查找，索引的概念和目录就是一样的。

同时还有一个问题，在存储时我们将所有的值序列化为字符串再作为文本直接写入到文件中，同时使用逗号分隔键和值，这个叫 CSV (comma-separated values) 格式，写入时会默认使用 UTF-8 的编码格式，每一个 UTF-8 字符会使用 1-4 个字节来存储，但对某些值来说，将其转化成字符串有可能会增大它的体积，例如布尔值完全可以用一个 bit 位来代替，而转变成了字符串 "true" 在 UTF-8 中则变成了 4 个字节。

使用文本格式的最大优点，是提供给了人类一个很好的可读性，事实上 MySQL 确实就有一个CSV 存储引擎。但在绝大多数情况下，文本格式并不是一个最佳选择，毕竟提供给人类可读性并不是一个很高优的目标，而使用二进制格式能有更好的性能表现。虽然我们用 Node.js 来实现肯定不会有太好的性能，但这个学习过程中我们会像设计一个真正的数据库一样去思考。在 Node 中我们也可以利用 Buffer 来实现对二进制数据进行操作，因此后续我们会将文本格式改为二进制格式。

哈希索引

索引是从主数据衍生出来的额外结构，添加和删除索引完全不会影响数据，只会影响查询的性能。维护这个结构会产生一些开销，因为我们需要在写入的时候多做一点操作，去更新索引，这样才能在读取的时候利用索引来加快一点速度。任何类型的索引通常都会减慢写入速度，因此数据库默认并不会索引所有的内容，而是需要用户来根据自己的情况做出取舍来手动选择索引，尽量选择那些带来较大收益而且又不会引入超出必要开销的索引。

前面我们实现了一个键值对数据库，提到键值对，马上就想到了 Map，在不同的语言里，它可能叫 HashMap，Dict 之类的， 可以通过对 key 进行 hash 操作来映射为固定的数字，然后利用数组下标进行访问，那么我们是不是完全可以使用它来索引硬盘上的数据呢？

当然是可以的，假设依然是追加写入的文件，就像前面的例子一样，可以设计一个最简单的索引策略：保留一个内存中的散列映射，其中每个键都映射到数据文件中的一个字节偏移量，指明了可以找到对应值的位置。

接下来我们就为数据库加上索引功能，同时存储格式改为二进制。