Hash ：

时间复杂度O(1)

不满足，范围扫描、顺序扫描

B+树，代表产品：mySql-InnoDB Mongo-B树

特性：

1、每次从磁盘中读取数据将相邻数据一并读出，最大限度减少磁盘IO

2、根节点常驻内存

3、非叶子节点容纳尽量多的元素

4、二分查找迅速，擅长范围查询和顺序扫描

5、随机写问题和节点分裂问题

问题： 出现随机IO 性能下降

LSM树：

google LevelDB

fackbook RocksDB

特性：

随机写转换成顺序写，批量转储

牺牲读的性能

增加后台合并开销

Redis

内存清理：

定期删除

惰性删除

LRU：最近、最少使用

LFU：增加频率

固化方式：

RDB

内存快照

手动/自动触发，

自动方式：

bgsave fork子进程，持久化过程由子进程完成，自动结束

配置项，save m n m秒存在n次写入，就触发bgsave

优点：

对Redis性能影响低

二进制压缩文件体积小

数据恢复快

缺点：

有数据丢失可能

备份文件版本兼容问题

处理方式：

客户端 set key 111 ——

Redis 正常数据写入处理 ——

持久化阀值判断

达到阀值，fork Redis子进程

dump内存数据，写临时文件

覆盖dump.db文件

AOF

预写日志

日志形式记录写入指令

实时持久化

原理：

1、每当有修改数据库的命令被执行时，

2、因为AOF文件里面存储了服务器执行过的所有数据库修改的命令，所以给定一个AOF文件，服务器只要重新执行一遍AOF文件里面包含的所有命令，就可以达到还原数据库的目的

优点：

用户可以根据自己的需要对AOF持久化进行调整，让Redis在遭遇意外停机时不丢失任何数据，或者只丢失一秒钟的数据，这比RDB持久化丢失的数据要少的多

处理方式：

客户端 set key 111 ——

Redis 正常数据写入处理 ——

判断重写阈值

fork子进程，子进程双写

一个模块直接写 aof文件

别一模块 new aof文件，重写，收缩整理

最后同步到 aof文件