【云计算与大数据技术】Bloom Filter、LSM树、Merkle哈希树、Cuckoo哈希等数据结构的讲解（图文解释超详细）

落日映苍穹つ 2023-09-30 17:47 16阅读 0赞

## 一、重要数据结构与算法 ##

分布式存储系统中存储大量的数据,同时需要支持大量的上层读/写操作，为了实现高吞吐量，设计和实现一个良好的数据结构能起到相当大的作用

这是以下三个数据库使用的数据结构，一个良好的数据结构对于分布式系统来说有着很大的作用。

NoSQL – LSM Tree

MemC3 – Cuckoo Hash

HBase – BloomFilter

## 二、Bloom Filter ##

Bloom Filter用于在海量数据中快速查找给定的数据是否在某个集合内

Bloom Filter的原理是当一个元素被加入集合时，通过k 个散列函数将这个元素映射成一个位数组中的k 个点，把它们置为1

检索时，用户只要看看这些点是不是都是1 就(大约)知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是 1，则被检元素很可能在

Bloom Filter的高效是有一定代价的，在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合，因此Bloom Filter不适合那些零错误的应用场合，在能容忍低错误的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省

![3be76b1514684a08bf0cd0a65987214f.png][]

## 三、LSM树 ##

LSM 树和 B+树相比，LSM 树牺牲了部分读性能，用来大幅度提高写性能

把一棵大树拆分成n棵小树，它首先写入内存中，随着小树越来越大，内存中的小树会flush到磁盘中，磁盘中的树定期可以做 merge操作

插入操作首先会作用于内存，由于内存中的树不会很大，因此速度快

合并操作会顺序写入一个或多个磁盘页,比随机写入快得多

![bf59a1dea1404cd7bd3fa6cab84f88f0.png][]

## 四、Merkle哈希树 ##

数据分成小的数据块,有相应的哈希和它对应

往上走，把相邻的两个哈希合并成一个字符串，然后运算这个字符串的哈希,这样每两个哈希组合得到了一个“子哈希”

Merkle Tree明显的一个好处是可以单独拿出一个分支来对部分数据进行校验

![4c0f8acb42f54a5290159bf7c5bcb8e2.png][]

## 五、Cuckoo哈希 ##

Cuckoo 哈希是一种解决 hash 冲突的方法，其目的是使用简易 的 hash 函数来提高 Hash Table 的利用率

使用两个 hash 函数来处理碰撞，从而每个 key 都对应到两个位置

对 key 值哈希，生成两个 hash key值 ，hash k1 和 hash k2 ,如果对应的两个位置上有一个为空，直接把 key 插入即可

否则，任选一个位置，把 key 值插入，把已经在那个位置的 key 值踢出

其查找思路与一般哈希一致，Cuckoo Hash在读多写少的负载情况下能够快速实现数据的查找

**创作不易 觉得有帮助请点赞关注收藏~~~**

[3be76b1514684a08bf0cd0a65987214f.png]: https://img-blog.csdnimg.cn/3be76b1514684a08bf0cd0a65987214f.png
[bf59a1dea1404cd7bd3fa6cab84f88f0.png]: https://img-blog.csdnimg.cn/bf59a1dea1404cd7bd3fa6cab84f88f0.png
[4c0f8acb42f54a5290159bf7c5bcb8e2.png]: https://img-blog.csdnimg.cn/4c0f8acb42f54a5290159bf7c5bcb8e2.png

发表评论取消回复

表情：

评论列表（有 0 条评论，16人围观）

还没有评论，来说两句吧...

相关阅读

相关【云计算与大数据技术】Bloom Filter、LSM树、Merkle哈希树、Cuckoo哈希等数据结构的讲解（图文解释超详细）

一、重要数据结构与算法分布式存储系统中存储大量的数据,同时需要支持大量的上层读/写操作，为了实现高吞吐量，设计和实现一个良好的数据结构能起到相当大的作用这是以下三个

落日映苍穹つ/ 2023年09月30日 17:47/ 0 赞/ 17 阅读

相关【云计算与大数据技术】大数据概念和发展背景讲解（图文解释超详细）

一、什么是大数据大数据是一个不断发展的概念，可以指任何体量或负载下那个超出常规数据处理方法和处理能力的数据，数据本身可以是结构化，半结构化甚至是非结构化的，随着物联网技

╰半橙微兮°/ 2023年09月30日 17:45/ 0 赞/ 12 阅读

相关数据结构：哈希表

目录第一章哈希表介绍第二章哈希冲突第三章哈希函数第四章哈希表实现 -------------------- > 项目地址：ht

心已赠人/ 2023年01月17日 08:27/ 0 赞/ 244 阅读

相关【数据结构】哈希表、哈希值计算分析

哈希表、哈希值计算分析哈希表完整代码引出哈希表哈希表（Hash Table）哈希冲突（Hash Collision） JDK1.8的

清疚/ 2022年11月06日 05:44/ 0 赞/ 215 阅读

相关重温数据结构：哈希哈希函数哈希表

[点击查看 Java 集合框架深入理解系列][Java _]， - ( ゜- ゜)つロ乾杯~ > 在学习 HashMap 前，我们先来温习下 Hash(哈希) 的概念

￡神魔★判官ぃ/ 2022年07月15日 00:30/ 0 赞/ 330 阅读

相关【数据结构】哈希桶

　　在[上一篇博客][Link 1]中，我们简单地介绍了哈希表，以及解决哈希冲突的办法；今天我们介绍解决哈希冲突的另一种方法——开散列法。开散列法又叫链地址法，首先对关键码集合

心已赠人/ 2022年05月28日 12:09/ 0 赞/ 318 阅读

相关【数据结构】哈希

　　我们经常会在一堆数据中搜索我们需要的数据元素，用于搜索的数据集合称为搜索结构。常见的查找方法有：从前往后依次遍历，二分查找，平衡二叉树，B树等。今天，我们看一种更高效的查找

「爱情、让人受尽委屈。」/ 2022年05月28日 10:57/ 0 赞/ 270 阅读

相关数据结构------哈希

哈希的提出之前我们已经接触过很多的数据结构了，比如线性表，二叉搜索树、AVL树、红黑树、B树等。当我们在这些数据结构中要查找一个元素时，会发现我们需要进行一系列的关键码

青旅半醒/ 2022年05月27日 22:19/ 0 赞/ 268 阅读

相关数据结构——哈希表

一、从一道Leetcode题目认识哈希表 [387. 字符串中的第一个唯一字符][387.] ![watermark_type_ZmFuZ3poZW5naGVpdGk_

淩亂°似流年/ 2022年04月22日 01:12/ 0 赞/ 332 阅读

相关数据结构——哈希表

1、基础知识 1.1 引子在实现编程中，常常面临着两个问题：存储和查询。存储和查询的效率往往决定了整个程序的效率。而我们常见存储数据的数据结构比如线性表，树等。数

心已赠人/ 2022年01月31日 13:39/ 0 赞/ 790 阅读