2023年7月27日发(作者：)

数据库的数据结构（1）——key-value数据库的⽇志系统许多数据库内部使⽤⽇志，⽇志是⼀个只⽀持追加更新的记录序列的集合，通常存储了⼤量的数据。如果每查询⼀条数据要从头到位扫描整个数据⽂件来查找数据所在的位索引是基于原始数据派⽣⽽来的额外数据结构，许多数据库允许单独增加和删除索引，⽽不影响数据库的内容，只影响查询性能。维护额外的数据结构必然带来额外的写⼊开销。适当的索引可以加速读取查询，但每个索引都会减慢写速度。key-value哈希索引key-value类型不是唯⼀可以索引的数据，但是它是其他更复杂索引的基础构造模块。key-value存储和⼤多数编程语⾔所内置的字典结构⼗分相似，通常使⽤hash map/hash tabl1、哈希表索引的局限性与优点局限性：_哈希表必须全部放⼊内存，如果有⼤量的key，可能存在内存不⾜的现象。原则上可以在磁盘上维护hash map，但是当哈希变满的时候，哈希表继续增长需要付出的代价⽐较昂贵，并且哈希冲突时候需要更加复杂的处理逻辑。区间查询效率不⾼。⽐如不能简单⽀持扫⾯abc0000和abc9999区间内所有的键，只能逐个查询。因此为了解决这些局限性，后续会介绍其它索引针对不同缺陷所进⾏的优化⽅式。优点：追加和分段合并主要是顺序写，⽐随机写⼊快。若果段⽂件是追加的或者不可变的，并发和崩溃恢复则简单许多，⽐如不必担⼼在重写值时发⽣崩溃的情况，留下⼀个包含部分旧值和部分新值混杂在⼀起的⽂件。合并旧段课程避免数据⽂件碎⽚化。2、哈希表索引的简单模型使⽤类csv格式的⽂件存储key-value对，将key存⼊内存中对hash map进⾏索引，每次写⼊只能进⾏追加操作。如果只追加到⼀个⽂件，但是磁盘空间是有限到，为了避免耗尽空间，需要将⽇志分解为⼀定⼤⼩的段，当⽂件达到⼀定⼤⼩的时候就关闭它，将后续写⼊到新的⽂件中，然后压由于段在写⼊后不会更改，所以被合并的段需要写⼊另⼀个新的段⽂件。段⽂件段合并和压缩过程中会将旧的段⽂件冻结，当其它线程运⾏时依旧可以使⽤旧的段⽂件进⾏正常读需要解决的⼀些细节问题：删除记录在需要删除的key的位置添加删除符，在合并段的时候抛弃/奔溃修复机器重启后内存中的hash map可能会消失，可以将每个段的hash map的快照存在磁盘上。并发控制单线程写⼊保证严格的先后顺序，多线程读取。部分写⼊数据库随时可能奔溃，包括将记录追加到⽇志的过程中，因此需要有⼀个校验值发现损坏的部分并丢弃。