第三章主要介绍可持久化的数据索引——主流的可持久化数据索引有下面几种:
Hash Index 是一种相对简单的索引结构。几乎每一种程序设计语言都有提供内存数据结构 hash map/table 的标准库,比如 C++ 中的 std::unordered_map
、Python 中的 dictionary
、Golang 中的 map
。
简单的 Hash Index 可以在 hash map 的基础上实现将数据持久化:在内存中维护一个 hash map,保存 key -> <offset, size>
,在磁盘上维护一个 append only 的文件用于持久化保存数据。
hash-index.png
简单粗糙的 C++ 代码实现如下:
#include <assert.h>
#include <fcntl.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>
#include <string>
#include <unordered_map>
#include <vector>
class HashIndex {
public:
HashIndex(const std::string& data_fname)
: data_fname_(data_fname), data_fd_(-1) {}
int Init() {
data_fd_ = open(data_fname_.c_str(), O_CREAT | O_RDWR | O_APPEND, 0666);
if (data_fd_ < 0) {
fprintf(stderr, "open %s error %s\n", data_fname_.c_str(),
strerror(errno));
return -1;
}
return 0;
}
int Get(const std::string& key, std::string* value) {
auto itr = hash_.find(key);
if (itr == hash_.end()) {
return 1;
}
std::vector<char> buf(itr->second.size);
ssize_t rsize =
pread(data_fd_, &buf[0], itr->second.size, itr->second.offset);
if (rsize != itr->second.size) {
fprintf(stderr, "pread fd %d offset %lu size %u rsize %ld error %s\n",
data_fd_, itr->second.offset, itr->second.size, rsize,
strerror(errno));
return -1;
}
std::string tmp_key;
DecodeData(buf.data(), tmp_key, *value);
if (tmp_key != key) {
return -2;
}
return 0;
}
int Set(const std::string& key, const std::string& value) {
std::string buf = EncodeData(key, value);
off_t offset = lseek(data_fd_, 0, SEEK_CUR);
if (offset < 0) {
fprintf(stderr, "lseek fd %d error %s\n", data_fd_, strerror(errno));
return -1;
}
auto wsize = write(data_fd_, buf.data(), buf.size());
if (wsize != buf.size()) {
fprintf(stderr, "write fd %d buf size %zu wsize %ld error %s\n", data_fd_,
buf.size(), wsize, strerror(errno));
return -1;
}
auto& value_info = hash_[key];
value_info.offset = offset;
value_info.size = buf.size();
return 0;
}
private:
uint32_t EncodeDataSize(uint32_t ksize, uint32_t vsize) {
return sizeof(uint32_t) * 2 + ksize + vsize;
}
std::string EncodeData(const std::string& key, const std::string& value) {
std::string result;
uint32_t ksize = key.size();
uint32_t vsize = value.size();
result.reserve(EncodeDataSize(ksize, vsize));
result.append((char*)&ksize, sizeof(ksize));
result.append(key);
result.append((char*)&vsize, sizeof(vsize));
result.append(value);
return result;
}
void DecodeData(const char* buf, std::string& key, std::string& value) {
uint32_t ksize = *(const uint32_t*)buf;
buf += sizeof(uint32_t);
key = std::string(buf, ksize);
buf += ksize;
uint32_t vsize = *(const uint32_t*)buf;
buf += sizeof(uint32_t);
value = std::string(buf, vsize);
}
struct ValueInfo {
uint64_t offset;
uint32_t size;
};
std::unordered_map<std::string, ValueInfo> hash_;
std::string data_fname_;
int data_fd_;
};
int main() {
HashIndex hash("/tmp/hash_index_test");
int ret = hash.Init();
assert(ret == 0);
std::string v0;
ret = hash.Get("hello", &v0);
assert(ret == 1);
ret = hash.Set("hello", "world");
assert(ret == 0);
ret = hash.Get("hello", &v0);
assert(ret == 0);
assert(v0 == "world");
ret = hash.Set("hash", "HashTable");
assert(ret == 0);
ret = hash.Set("lsm", "LSMTree");
assert(ret == 0);
ret = hash.Set("b-", "B-Tree");
assert(ret == 0);
ret = hash.Set("b+", "B+Tree");
assert(ret == 0);
ret = hash.Get("hash", &v0);
assert(ret == 0);
assert(v0 == "HashTable");
ret = hash.Get("lsm", &v0);
assert(ret == 0);
assert(v0 == "LSMTree");
ret = hash.Get("b-", &v0);
assert(ret == 0);
assert(v0 == "B-Tree");
ret = hash.Get("b+", &v0);
assert(ret == 0);
assert(v0 == "B+Tree");
ret = hash.Set("hello", "WORLD");
assert(ret == 0);
ret = hash.Get("hello", &v0);
assert(ret == 0);
assert(v0 == "WORLD");
return 0;
}
这个实现没有考虑太多方面的问题,比如:
想要知道这些问题如何解决,可以参考论文:Bitcask: A Log-Structured Hash Table for Fast Key/Value Data。
此外,Hash Index 还存在一些限制:
下面介绍的 LSM-Tree、B-Tree、B+Tree 的大小不会受到内存大小的限制,也能实现效率比较高的 range query,相对 Hash Indexe 会更加通用。
LSM-Tree 最早应该是出自论文 The Log-Structured Merge-Tree (LSM-Tree) ,其设计目标是提升写性能。
LSM-Tree 通过将随机写转化为顺序写来提高写性能(无论 HDD 还是 SSD,其顺序读写都要明显优于随机读写),而付出的代价就是读放大(每次查询可能需要 I/O)和写放大(compaction)。
lsm_arch.png
如上图所示:
LSM-Tree 最近几年非常热门,比较知名的开源实现有:
1970 年的论文 Organization and maintenance of large ordered indices 提出了一种按页管理外存,便于随机访问的数据结构——B-Tree。
B-Tree 是众多平衡树中的一种,其设计思想是尽可能减少每次读写需要访问外存的次数。大部分 B-Tree 的操作(search、insert、delete)都只需要访问磁盘 O(h) 次。h 是 B-Tree 的高度。B-Tree 是一棵高扇出的扁平树。h 的值一般都比较小。
B-Tree 将数据划分成一个个固定大小的 page,一般是 4/8/16 KB,每次读写一个 page。一个 page 上保存的数据是有序的,方便快速查找。
B-Tree.png
一棵 m 阶的 B-Tree 的定义如下:
m/2 - 1 <= j <= m - 1
。m/2 <= k <= m
。1、2、3 主要是规定了 B-Tree 的结点分裂(split)与合并(merge)的基本规则。
4 保证了树结构是平衡的。
一个 page 中能存放的关键字 key 越多,B-Tree 的扇出(m 的值)就越大,这棵树就会越扁平。
二叉树扇出固定为 2,5 层最多可以存储 31 个 key-value。
B-Tree 假设 page 为 8KB,key 16 B, value 64 B,扇出可以接近 100。假设扇出为 100,5 层的 B-Tree 最多可以存储超过 100 亿个 key-value。
使用 B-Tree 作为索引数据结构的开源实现主要有:
B+Tree.png
B+Tree 是 B-Tree 的变种。B+Tree 与 B-Tree 的最大区别在于:B-Tree 可以在非叶结点中存储数据,而 B+Tree 的所有数据都存储在叶子节点中,非叶子结点只存储 key 不存储 value。
这一点的区别让 B+Tree 的扇出大大高于 B-Tree。理论上,同等情况下 B+Tree 的高度要比 B-Tree 矮。
另外,B+Tree 通过在叶子结点增加相互连接的指针,可以很方便地执行范围查询和遍历,提高区间访问的性能。
一般情况下,在范围查询(range query)的场景下,B+Tree 的性能要优于 B-Tree;在点查询(point query)的场景下,B+Tree 每次查询都需要固定从根节点访问到叶子结点,而 B-Tree 可能在树中间就能查到结果。
使用 B+Tree 作为索引数据结构的数据库/存储引擎的有: