茂名网站建设方案外包/友情链接交换系统
一、LSM 树 (Log-Structured Merge Tree)
LSM 树(Log-Structured Merge Tree) 是一种专为 高效写入和批量更新 设计的数据结构,特别适合于 高写入密度 的应用场景,如数据库和文件系统。它广泛用于 NoSQL 数据库(如 Cassandra、LevelDB、RocksDB)等系统中,支持高效的顺序写入和延迟写入的合并操作。
1. 基本原理
LSM 树通过将数据分为多个 分层存储(通常称为 Level),并且将数据按 批次写入 来减少随机写操作,以提升写入性能。其核心思想是将 写入操作转化为顺序写入,从而提高磁盘 I/O 性能。
-
MemTable(内存表):
- 写入首先进入内存中的 MemTable(通常是一个平衡树,如 AVL 树或 SkipList)。
- 当 MemTable 达到一定大小时,会被写入磁盘,形成 SSTable(Sorted String Table) 文件。
-
SSTable(有序字符串表):
- SSTable 是 只读的有序文件,通常是不可变的(Immutable)。
- 数据写入磁盘后,MemTable 会被清空以接受新的写入。
-
合并(Merge)与压缩(Compaction):
- 随着 SSTable 文件的增多,系统会定期执行 合并和压缩操作。
- 合并操作将多个较小的 SSTable 文件合并为一个较大的文件,以减少磁盘空间的浪费,并提升查询效率。
2. 操作流程
-
插入(Insert):
- 新数据首先写入 MemTable。
- MemTable 写满后,将其刷入磁盘生成新的 SSTable 文件。
- 后台合并线程定期将多个 SSTable 文件合并为一个较大的 SSTable 文件。
-
查询(Search):
- 查询操作首先在 MemTable 中查找。
- 如果 MemTable 中未命中,则查找缓存的 Bloom Filter,以决定是否查询 SSTable。
- 若 Bloom Filter 判断 SSTable 可能存在查询数据,则顺序读取 SSTable 文件。
-
删除(Delete):
- 删除操作通过写入 删除标记(Tombstone) 来实现,实际数据不会立即删除,而是等待压缩时清理。
3. 优缺点
优点 | 缺点 |
---|---|
支持高效的批量写入和顺序写入 | 查询效率受限于 SSTable 的合并与压缩策略 |
适合写密集型工作负载 | 删除和更新操作依赖后台合并 |
支持快速恢复(数据持久化在磁盘上) | 高并发查询时,可能导致多次磁盘 I/O |
4. 应用场景
- NoSQL 数据库:如 Cassandra、LevelDB、RocksDB。
- 日志管理系统:存储和检索大规模的日志数据。
- 缓存系统:高效存储和更新缓存数据。
- 分布式存储系统:用于提高数据写入效率和持久化性能。
二、Cuckoo Hashing
Cuckoo Hashing(布谷鸟哈希) 是一种解决哈希表 冲突问题 的高效算法。它通过使用 两个或多个哈希函数 和 重新安置(Kick-Out)策略,在保证 O(1) 时间复杂度的同时,极大地减少了哈希冲突的概率。该算法得名于布谷鸟在其他鸟巢中安放自己的蛋的行为,正如在哈希表中安放键值对时,如果冲突发生,则将现有的键“挤出”并重新安放。
1. 基本原理
- 多哈希函数:使用两个(或更多)不同的哈希函数
h1(x)
和h2(x)
。 - 双表结构:使用两个独立的哈希表,或将其合并为一个逻辑上的双槽位表。
- 挤出策略:当插入一个键时,如果目标槽位已被占用,则将占用的键“挤出”,并重新插入到其另一个哈希位置。
2. 操作流程
-
插入(Insert):
- 计算键的两个哈希值
h1(key)
和h2(key)
。 - 尝试将键插入
h1(key)
所在的槽位。 - 如果槽位已占用,则将原有的键“踢出”(Kick-Out),并尝试将被踢出的键插入其另一哈希位置
h2(key)
。 - 这个过程可能会递归进行,如果达到最大次数(通常是表的大小的常数倍),则触发 重新哈希(Rehashing)。
- 计算键的两个哈希值
-
查询(Search):
- 查询键时,计算其两个哈希值。
- 检查
h1(key)
和h2(key)
两个位置是否存在目标键。
-
删除(Delete):
- 删除时只需检查并清除
h1(key)
和h2(key)
两个位置的键值。
- 删除时只需检查并清除
3. 时间复杂度
操作 | 平均情况复杂度 | 最坏情况复杂度 |
---|---|---|
插入 (Insert) | O(1) | O(1)(可摊销) |
查询 (Search) | O(1) | O(1) |
删除 (Delete) | O(1) | O(1 |
重新哈希 (Rehash) | O(n) | O(n) |
4. 优缺点
优点 | 缺点 |
---|---|
保证 O(1) 的查询和插入性能 | 需要额外空间来存储多个哈希表 |
哈希表装载因子可接近 1,空间利用率高 | 插入时可能需要多次挤出操作 |
可有效避免链式哈希的链表冲突和线性探测 | 当表接近满载时,重新哈希代价较高 |
5. 应用场景
- 缓存系统:适用于需要高性能键值存储的场景,如高速缓存 (Cache)。
- 网络路由:用于存储和查找路由表,提高路由查找效率。
- 数据库系统:索引结构和快速查找数据块。
- 分布式系统:负载均衡、哈希分片等。
三、LSM 树 vs Cuckoo Hashing 对比
特性 | LSM 树 (Log-Structured Merge Tree) | Cuckoo Hashing |
---|---|---|
核心特点 | 高效的批量写入、顺序写入优化 | 使用多个哈希函数与重新安置策略 |
适用数据类型 | 适合有序数据的持久化存储 | 适合高效的键值对存储 |
写入性能 | 批量写入性能优越,适合写密集型场景 | 保证 O(1) 写入性能 |
查询性能 | 查询性能较高,但依赖于合并和压缩操作 | 查询性能为 O(1),但需要额外空间 |
应用场景 | 数据库、日志管理系统、缓存 | 缓存系统、网络路由、快速查找 |
存储结构 | MemTable + SSTable + 压缩机制 | 双哈希表 + 挤出策略 |
总结
- LSM 树 适合 高写入密度 的应用场景,特别是对数据持久化有要求的系统,如 NoSQL 数据库 和 日志系统。
- Cuckoo Hashing 更适合需要 快速插入和查询 的场景,特别是在 内存受限 的环境下,如 高速缓存 和 网络路由表。
相关文章:

LSM树 (Log-Structured Merge Tree)、Cuckoo Hashing详细解读
一、LSM 树 (Log-Structured Merge Tree) LSM 树(Log-Structured Merge Tree) 是一种专为 高效写入和批量更新 设计的数据结构,特别适合于 高写入密度 的应用场景,如数据库和文件系统。它广泛用于 NoSQL 数据库(如 Ca…...

VMware中的重要日志文件 vobd.log 学习总结
最近几天处理完毕存储的故障后,接着就是host方面的问题,Vmware无法访问到存储,其实存储的LUN和POOL 已经online ready了,但是主机还是访问不到存储。 这里介绍下Vmware中的一个重要的日志文件 vobd.log,该文件对于分析…...

MyBatis 返回 Map 或 List<Map>时,时间类型数据,默认为LocalDateTime,响应给前端默认含有‘T‘字符
一、问题 MyBatis 返回 Map 或 List时,时间类型数据,默认为LocalDateTime Springboot 响应给前端的LocalDateTime,默认含有’T’字符,如何统一配置去掉 二、解决方案 1、pom.xml 增加依赖(2024.11.6 补充ÿ…...

ASR TP
ASR翱捷科技 ASR kernel 5.10 android14 ASR EVB平台 jd9365tr(jadard) spi 1.驱动: 跟mtk驱动一样,放进去,不用改 asr_android14.0_alpha\asr\kernel\linux\drivers\input\touchscreen\jadard makefile: asr_android14.0_alpha\asr\kernel\linux\drivers\input\t…...

Tomcat与Nginx之全面比较
概况 Apache Tomcat Apache Tomcat,通常简称为Tomcat,是一个开源的Web应用服务器,它主要用于运行Java Web应用程序。Tomcat实现了Java Servlet和JavaServer Pages(JSP)技术,这些是Java EE规范的一部分。To…...

这是一个bug求助帖子--安装kali 遇坑
第一个报错 介质:kali-linux-2024.1-live-amd64 环境:Dell笔记本 i510代cpu 现象及操作 安装完以后 然后我换了个国内的源进行了以下操作 apt-get update:更新源列表 apt-get upgrade:更新所有可以更新的软件包 然后进行清理。…...

IntelliJ Idea设置自定义快捷键
我IDEA的快捷键是自己修改成了和Eclipse相似,然后想要跳转到某个方法的上层抽象方法没有对应的快捷键,IDEA默认的是Ctrl U (Windows/Linux 系统) 或 Command U (Mac 系统),但是我的不起作用&a…...

AlohaKit:一组.NET MAUI绘制的开源控件
前言 今天大姚给大家分享一组.NET MAUI绘制的开源、免费(MIT License)UI控件库:AlohaKit。 MAUI介绍 .NET MAUI是一个开源、免费(MIT License)的跨平台框架(支持Android、iOS、macOS 和 Windows多平台运…...

Windows 实例磁盘空间管理
操作场景 本文以操作系统为 Windows Server 2012 R2 的腾讯云云服务器为例,介绍如何在 Windows 实例磁盘空间不足的情况下进行空间释放操作,及如何进行磁盘的日常维护。 操作步骤 释放磁盘空间 您可通过 删除容量较大文件 或 删除不需要的文件 &…...

【动手学电机驱动】STM32-FOC(6)基于 IHM03 的无感方波控制
STM32-FOC(1)STM32 电机控制的软件开发环境 STM32-FOC(2)STM32 导入和创建项目 STM32-FOC(3)STM32 三路互补 PWM 输出 STM32-FOC(4)IHM03 电机控制套件介绍 STM32-FOC(5&…...

【数据结构】汇编语言和机器语言的‘数据结构‘
前言 汇编语言没有像高级语言(如 C#、Java 等)那样直接提供数据结构(如数组、链表、树、栈等),但是可以通过对内存地址和寄存器的操作来实现这些数据结构。汇编语言的核心是直接操控计算机的内存,因此所有…...

hadoop+spark中8088,18080,19888,4040端口页面的区别
在hadoop集群中,本身就有 9870端口,8088端口,19888端口 这三个页面,当使用spark作为计算引擎时,会多出8080,4040,18080这三个页面,页面就很多了,现在明确的辨别一下。 单…...

PDS的主要部件
PDS(配电系统)的主要部件包括去耦电容器、电源调节器、PCB几何结构等。以下是这些主要部件的相关介绍: 去耦电容器:去耦电容器是PDS中不可或缺的组成部分,其主要功能是过滤掉电源线上的噪声和干扰,确保供电…...

(十三)JavaWeb后端开发——MySQL2
目录 1.DQL数据查询语言 1.1基本查询 1.2条件查询 where关键字 1.3分组查询 1.4排序查询 1.5分页查询 2.多表设计 3.多表查询——联查 4.多表查询——子查询 5.MySQL 事务 6.事务管理(事务进阶) 7.MySQL 索引 1.DQL数据查询语言 分为五大…...

MFC图形函数学习06——画椭圆弧线函数
绘制椭圆弧线函数是MFC基本绘图函数,这个函数需要的参数比较多,共四对坐标点。前两对坐标点确定椭圆的位置与大小,后两对坐标确定椭圆弧线的起点与终点。 一、绘制椭圆弧线函数 原型:BOOL Arc(int x1,int y1,int x2,int y2…...

缓存、注解、分页
一.缓存 作用:应用查询上,内存中的块区域。 缓存查询结果,减少与数据库的交互,从而提高运行效率。 1.SqlSession 缓存 1. 又称为一级缓存,mybatis自动开启。 2. 作用范围:同一…...

【数据结构与算法】第9课—数据结构之二叉树(链式结构)
文章目录 1. 二叉树的性质2. 链式结构二叉树3. 二叉树链式结构的4种遍历方式4. 二叉树节点个数5. 二叉树的叶子节点个数6. 二叉树第k层节点个数7. 二叉树的高度/深度8. 二叉树查找值为x的节点9. 二叉树的销毁10. 判断是否为完全二叉树11. 二叉树练习题11.1 单值二叉树11.2 相同…...

【CSS】居中样式
对于行内元素,使用 text-align: center。对于已知宽度的块级元素,使用 margin: 0 auto。对于需要灵活布局的元素,使用 Flexbox 或 Grid。 flex .parent {display: flex;justify-content: center; /* 水平居中 */align-items: center; /* 垂…...

Vite环境下uniapp Vue 3项目添加和使用环境变量的完整指南
一、引言 在uniapp项目中,合理配置环境变量对于提高开发效率和保障项目安全至关重要。Vite作为新一代的前端构建工具,为环境变量的管理提供了简洁而强大的支持。下面,我们将一步步学习如何在Vite环境下为uniapp Vue 3项目添加和使用环境变量…...

mysql-springboot netty-flink-kafka-spark(paimon)-minio
1、下载spark源码并编译 mkdir -p /home/bigdata && cd /home/bigdata wget https://archive.apache.org/dist/spark/spark-3.4.3/spark-3.4.3.tgz 解压文件 tar -zxf spark-3.4.3.tgz cd spark-3.4.3 wget https://raw.githubusercontent.com/apache/incubator-celeb…...

讨论一个mysql事务问题
最近在阅读一篇关于隔离级别的文章,文章中提到了一种场景,我们下面来分析一下。 文章目录 1、实验环境2、两个实验的语句执行顺序3、关于start transaction和start transaction with consistent snapshot4、实验结果解释4.1、实验14.2、实验24.3、调整实…...

pytest插件精选:提升测试效率与质量
pytest作为Python生态系统中备受推崇的测试框架,以其简洁、灵活和可扩展性赢得了广泛的认可。通过合理使用pytest的各种插件,可以显著提升测试效率、增强测试的可读性和可维护性。 pytest-sugar:提升测试体验 pytest-sugar是一款增强版的py…...

HTB:Sightless[WriteUP]
目录 连接至HTB服务器并启动靶机 使用nmap对靶机TCP端口进行开放扫描 继续使用nmap对靶机开放的TCP端口进行脚本、服务扫描 首先尝试对靶机FTP服务进行匿名登录 使用curl访问靶机80端口 使用浏览器可以直接访问该域名 使用浏览器直接访问该子域 Getshell 横向移动 查…...

国产化浪潮下,高科技企业如何选择合适的国产ftp软件方案?
高科技企业在数字化转型和创新发展中,数据资产扮演着越来越重要的角色。在研发过程中产生的实验数据、设计文档、测试结果等,专利、商标、版权之类的创新成果等,随着信息量急剧增加和安全威胁的复杂化,传统的FTP软件已经不能满足这…...

自注意力机制
当输入一系列向量,想要考虑其中一个向量与其他向量之间的关系,决定这个向量最后的输出 任意两个向量之间的关系计算 计算其他向量对a1的关联性 多头注意力机制 图像也可以看成一系列的向量,交给自注意力机制处理,CNN是特殊的自注意…...

抽象工厂模式详解
1. 引言 1.1 设计模式概述 设计模式(Design Patterns)是软件开发中解决常见问题的一种最佳实践。它们通过总结经验,提供了一套被验证有效的代码结构和设计原则,帮助开发者提高代码的可维护性、可重用性和可扩展性。 设计模式主…...

【Linux】软硬链接和动静态库
🔥 个人主页:大耳朵土土垚 🔥 所属专栏:Linux系统编程 这里将会不定期更新有关Linux的内容,欢迎大家点赞,收藏,评论🥳🥳🎉🎉🎉 文章目…...

HarmonyOS入门 : 获取网络数据,并渲染到界面上
1. 环境搭建 开发HarmonyOS需要安装DevEco Studio,下载地址 : https://developer.huawei.com/consumer/cn/deveco-studio/ 2. 如何入门 入门HarmonyOS我们可以从一个实际的小例子入手,比如获取网络数据,并将其渲染到界面上。 本文就是基于…...

【贪心】【哈希】个人练习-Leetcode-1296. Divide Array in Sets of K Consecutive Numbers
题目链接:https://leetcode.cn/problems/divide-array-in-sets-of-k-consecutive-numbers/description/ 题目大意:给出一个数组nums[]和一个数k,求nums[]能否被分成若干个k个元素的连续的子列。 思路:比较简单,贪心就…...

【数据库实验一】数据库及数据库中表的建立实验
目录 实验1 学习RDBMS的使用和创建数据库 一、 实验目的 二、实验内容 三、实验环境 四、实验前准备 五、实验步骤 六、实验结果 七、评价分析及心得体会 实验2 定义表和数据库完整性 一、 实验目的 二、实验内容 三、实验环境 四、实验前准备 五、实验步骤 六…...