第三章 数据存储与检索

存储引擎的两大家族:基于日志结构的存储引擎 和 面向页的存储引擎。

哈希索引

如何解决只追加到一个文件,如何避免最终用尽磁盘空间呢?

将日志分成一定大小的段,当文件达到一定大小时久关闭它,并将后续写入到新的段文件中。然后,可以在这些已经关闭的段上执行压缩,压缩也就是把在日志中丢弃重复的键,并且只保留每个键最近的更新(和redis的AOF 重做的原理一样)。
对于查询,因为每个段都有自己的hash表,将键映射到文件的偏移量。为了找到键的值,首先检查最新的段的hash map,如果不存在,检查第二最新的段,以此类推。
存储的方式,可以使用二进制的方式。 ### 如何处理删除动作?
在数据文件中追加一个特殊的删除标记(成为墓碑),当合并日志段时,就会丢弃这个已经删除键的所有值。 ### 崩溃恢复怎么处理?
如果数据库重新启动,则内存中的hash map将丢失。原则上,可以通过从头到尾读取整个段文件,然后记录每个键的最新值的偏移量,来恢复每个段的hash map。但是如果分段文件很大,可能扫描的时间很长,重启过程就会非常缓慢。 可以通过将每个段的hash map的快照存储在磁盘上,可以更快的加载到内存中,加快恢复的速度。 

BTree

the goal of btree is minimize the number of reads.

The height of the BTree determines maximum number of seeks possible in search data. and the height of the structure is : logm(n) [log base m of n]

therefore: the number of seeks is no more than logm(n). so, a BTree is an optimized algorithm to optimize around the idea of doing as minimal disk seeks as possible when all of data cannot fit in main memory.

For a BTree of order “m”:

  1. All keys within a node are in sorted order.
  2. Each node contains no more than m - 1 keys.(m - 1 keys have m children.)
  3. Each internal nodes can have at most m children. so, a BTree of order m is like an m-way tree. - a root node can be a leaf or have [2, m] children. - Each non-root, internal node has [ceil(m/2), m] children.
  4. All leaves are on the same level.