Hash存储模型、B-Tree存储模型、LSM存储模型介绍[通俗易懂]

小小码 • 2023-01-26 09:30 • 代码基础 • 阅读 115

大家好，我是考100分的小小码，祝大家学习进步，加薪顺利呀。今天说一说Hash存储模型、B-Tree存储模型、LSM存储模型介绍[通俗易懂],希望您对编程的造诣更进一步.

Hash存储模型、B-Tree存储模型、LSM存储模型介绍

每一种数据存储系统，对应有一种存储模型，或者叫存储引擎。我们今天要介绍的是三种比较流行的存储模型，分别是：

Hash存储模型
B-Tree存储模型
LSM存储模型

不同存储模型的应用情况

1、Hash存储模型

redis
memcache

2、B-Tree存储模型

MySQL（以及大多数的关系型数据库）
MongoDB

3、LSM树存储模型

HBase
RocksDB

不同存储模型介绍

1、Hash存储模型

Hash存储模型其实就是HashMap（哈希表）的持久化实现。这种模型的特点是与HashMap有密切关系的。我们知道HashMap可以支持：put（key）增加/修改、delete（key）删除、get（key）随机获取操作，但是HashMap不支持get(1)这样的操作。因为HashMap是无序的，不支持顺序扫描。针对put、get操作，它的时间复杂度是O(1)，也就是说读写速度都很快，所以针对单个Key的操作是非常快速的。如果我们在应用中无需遍历数据，Hash引擎是非常合适的。

首先，通过key，找到对应的文件编号。这个检索的过程，是通过HashMap来实现的。

其次，通过文件编号找到存储中的文件

再者，通过value长度和位置找到对应的行数据

最后，读取出value内容

2、B-Tree存储模型

B-Tree存储模型由于是树状结构存储，所以，它是不支持随机读写的。就像我们学习二叉树时，查找数据得通过遍历树的方式来查找数据。

上图是一种典型的B-Tree存储索引。叶子节点保存了每行的完整数据，非叶子节点保存了索引信息。数据在每个节点都是有序存储的，但查询数据的时候，需要从根节点遍历，然后根据二分查找直到找到叶子节点。如果数据不再内存中，需要从磁盘中读取，并加载到缓存。B+树的根节点是常驻内存的，最多需要h-1次磁盘IO，复杂度为O(h) = O(logdN)。修改操作首先要记录提交日志，然后在修改内存中的B+树。