在当今信息时代，数据的存储和管理变得越来越重要。无论是云存储、数据库还是分布式文件系统，都需要高效的数据存储和检索方法。其中，LSM树（Log-Structured Merge Tree）是一种高性能的数据结构，广泛应用于各种分布式存储系统和数据库引擎中。本文将介绍LSM树的原理，并探讨其在不同使用场景中的应用。
随着数据量的增大，传统关系型数据库越来越不能满足对于海量数据存储的需求。对于分布式关系型数据库，我们了解其底层存储结构是非常重要的。本文将介绍下分布式关系型数据库 TiDB 所采用的底层存储结构 LSM 树的原理。
在有代表性的关系型数据库如MySQL、SQL Server、Oracle中，数据存储与索引的基本结构就是我们耳熟能详的B树和B+树。而在一些主流的NoSQL数据库如HBase、Cassandra、LevelDB、RocksDB中，则是使用日志结构合并树（Log-structured Merge Tree，LSM Tree）来组织数据。本文先由B+树来引出对LSM树的介绍，然后说明HBase中是如何运用LSM树的。
在评估和选型数据库的时候，人们往往将重点放在数据建模的灵活性，一致性保证，线性可伸缩性，容错性，低延迟，高吞吐量和易于管理等方面。但怎么才能评判出这些指标呢？很多人往往会网上一通搜索和看官方文档，再加上自己的“经验”来得出这些指标。
哈希表 哈希表支持增、删、改、查操作，但是支持范围查找较差；因为哈希表特性，如果进行范围查找，一个范围的所有数据都必须经过哈希计算来查找对应的链表节点，这几乎是需要这个范围每一个数据都需要去哈希表中查找一次，性能比较差。 📷 B+树 B+树支持增、删、改、查操作，并且很好支持范围查找，插入和查找性能均衡。 B+树的结构每个非叶子节点是数据索引，叶子节点是数据或者数据的指针。B+树叶子节点之间的连接可以实现高效的范围查询，例如innoDB存储引擎默认就是B+树结构. 传统的B+树读写相对比较均衡，但是当内存容
LSM树(Log-Structured-Merge-Tree)的名字往往会给初识者一个错误的印象，事实上，LSM树并不像B+树、红黑树一样是一颗严格的树状数据结构，它其实是一种存储结构，目前HBase,LevelDB,RocksDB这些NoSQL存储都是采用的LSM树。
RocksDB是一个高性能、可扩展、嵌入式、持久化、可靠、易用和可定制的键值存储库。它采用LSM树数据结构，支持高吞吐量的写入和快速的范围查询，可被嵌入到应用程序中，实现持久化存储，支持水平扩展，可以在多台服务器上部署，实现集群化存储，具有高度的可靠性和稳定性，易于使用并可以根据需求进行定制和优化。RocksDB主要使用到了下面知识：
前言：最近在了解大数据实时分析技术druid,究其原理时发现用到了类LSM树思想以实现高效的数据插入，于是展开了对LSM的了解，了解之后感觉这东西虽然也并没有很特别，但在大数据、分布式架构中的应用还是非常有价值的，下面简单做下分享！
LSM 树的这些特点，使得它相对于 B+ 树，在写入性能上有大幅提升。所以，许多 NoSQL 系统都使用 LSM 树作为检索引擎，而且还对 LSM 树进行了优化以提升检索性能。
我在上篇文章 Apache Pulsar 的架构设计 中介绍了 Pulsar 存算分离的架构，其中 broker 只负责计算，由 BookKeeper 负责底层的存储，我还画了这样一张图说明 BookKeeper 读写分离的设计：
高性能事务系统应用程序通常在提供活动跟踪的历史记录表；同时，事务系统生成$日志记录，用于系统恢复。这两种生成的信息都可以受益于有效的索引。众所周知的设置中的一个例子是TPC-a基准应用程序，该应用程序经过修改以支持对特定账户的账户活动历史记录的有效查询。这需要在快速增长的历史记录表上按帐户id进行索引。不幸的是，基于磁盘的标准索引结构（如B树）将有效地使事务的输入/输出成本翻倍，以实时维护此类索引，从而使系统总成本增加50%。显然，需要一种以低成本维护实时索引的方法。日志结构合并树（LSM树）是一种基于磁盘的数据结构，旨在为长时间内经历高记录插入（和删除）率的文件提供低成本索引。LSM树使用一种延迟和批量索引更改的算法，以一种类似于合并排序的有效方式将基于内存的组件的更改级联到一个或多个磁盘组件。在此过程中，所有索引值都可以通过内存组件或其中一个磁盘组件连续进行检索（除了非常短的锁定期）。与传统访问方法（如B-树）相比，该算法大大减少了磁盘臂的移动，并将在使用传统访问方法进行插入的磁盘臂成本超过存储介质成本的领域提高成本性能。LSM树方法还推广到插入和删除以外的操作。然而，在某些情况下，需要立即响应的索引查找将失去输入/输出效率，因此LSM树在索引插入比检索条目的查找更常见的应用程序中最有用。例如，这似乎是历史表和日志文件的常见属性。第6节的结论将LSM树访问方法中内存和磁盘组件的混合使用与混合方法在内存中缓冲磁盘页面的常见优势进行了比较。
LSM树(Log-Structured-Merge-Tree)（日志结构合并树）是一种能够提升磁盘写入速度的数据结构，它通过将大量的磁盘随机写操作，转换为批量顺序写的方式来得到写入性能的提升。但是同时也牺牲了一部分的读性能
这张经典图片来自 Flink PMC 的 Stefan Richter 在Flink Forward 2018演讲的PPT
我们熟知常用数据库MySQL MongoDB HBase等底层存储都用了各种树结构，如B树LSM树，不过为什么要用这些结构呢？
1. 概述 Log-Structured Merge-trees (LSM树)被广泛应用在现代NoSQL系统存储层中，比如：BigTable、Dynamo、HBase、Cassandra、LevelDB、RocksDB和AsterixDB等等。不同于传统的索引结构（比如B+树）更新时直接在所在位置进行修改，LSM树则先将数据直接写入到内存，然后通过合并线程将内存数据刷新到磁盘。这种设计有很多好处，包括：超高的写性能、不错的空间利用率、可优化性、简单的并发控制和恢复机制等。 2. LSM树的
推出一个新系列，《看图轻松理解数据结构和算法》，主要使用图片来描述常见的数据结构和算法，轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种排序等等几十篇的样子。
随着rocksDB（facebook的）,levelDB（google的），以及我们熟知的hbase，他们都是使用的LSM树结构的数据库。
作为目前数据库引擎的两种主要数据结构，LSM-tree和B+-tree在业界已经有非常广泛的研究。相比B+-tree，LSM-tree牺牲一定的读性能以换取更小的写放大以及更低的存储成本，但这必须建立在已有的HDD和SSD的基础上。 探索前沿研究，聚焦技术创新，本期DB·洞见由腾讯云数据库高级工程师王宏博进行分享，主要介绍一篇2022年FAST的论文，主题为“基于硬件透明压缩的B+树优化”。本次分享的论文针对可计算存储SSD（支持硬件透明压缩）提出了三种有趣的设计方法，从而极大地减少了B+-tree的写放大
LotusDB 是一个基于 LSM Tree 进行设计，并结合 B+ 树优势的单机 KV 存储引擎，读写性能稳定、快速。
2006年，Google 发表了 BigTable 的论文。这篇论文提到 BigTable 单机上所使用的数据结构就是 LSM。
点击上方蓝字，发现更多精彩 导语 LSM作为一种重要的数据存储结构方式，被许多大型开源存储系统应用为底层引擎的存储结构。同时由于influxDB的不断改良，一种基于LSM的改良数据结构TSM也开始被熟知并广泛应用。本文将基于官方文档和相关论文分析该两种数据结构的组成原理和应用特点。 LSM（Log-Structured Merge Tree）日志结构合并树 ° 模型发展 由于b+树具有稳定查询效率、逻辑上有序的数据存储等特点，使得b+树成为了许多RDBMS的底层引擎的数据结构。不过，b+数的有序数据存储仅
虽然大家都是叫它 LSM 树，听着很像是一个树状的数据结构，但严格意义上，它是一种存储结构，全称 Log-Structured-Merge-Tree，即日志结构合并树
最近遇到两个问题,wriedtiger引擎到底支持不支持LSM tree , 2 为什么percona的mongodb Dump 了ROCKSDB 的数据库引擎.
对于目前大多数Druid 的使用场景来说，Druid 本质上是一个分布式的时序数据库，而对于一个数据库的性能来说，其数据的组织方式至关重要。为了更好地阐述Druid 的架构设计思想，我们得先从数据库的文件组织方式聊起。
MySQL + HBase是我们日常应用中常用的两个数据库，分别解决应用的在线事务问题和大数据场景的海量存储问题。
LSM树是HBase里使用的非常有创意的一种数据结构。在有代表性的关系型数据库如MySQL、SQL Server、Oracle中，数据存储与索引的基本结构就是我们耳熟能详的B树和B+树。而在一些主流的NoSQL数据库如HBase、Cassandra、LevelDB、RocksDB中，则是使用日志结构合并树（Log-structured Merge Tree，LSM Tree）来组织数据。
LSM 树广泛用于数据存储，例如 RocksDB、Apache AsterixDB、Bigtable、HBase、LevelDB、Apache Accumulo、SQLite4、Tarantool、WiredTiger、Apache Cassandra、InfluxDB和ScyllaDB等。
来源：blog.csdn.net/weixin_41605937/ article/details/110933984
本文是左耳耗子推荐的Medium上的一篇关于MySQL的文章Some study on database storage internals，本人觉得文章十分好，就取得了作者的许可，自行进行了翻译，原文链接见文末。
【Flink】第十二篇：记kudu-connector写CDC数据的-D数据时，报主键不存在的异常
笔者前段时间在学习数据结构时，恰好听说了 LSM Tree，于是试着通过 LSM Tree 的设计思想，自己实现一个简单的 KV 数据库。
来源：https://blog.csdn.net/weixin_41605937/article/details/110933984
LSM Tree（log-structured merge-tree）是一种文件组织结构的数据结构，目前在不少数据库中都有使用到，如SQLite、LevelDB、HBase在Mongodb中也有一个LSM引擎；
经历了大概 4 个月的打磨，LotusDB 的第一个 release 版本终于发布了，我看了下，有 200 多次 commit（接近 rosedb 一年多的 commit 次数了）。
Apache IoTDB（物联网数据库）是一体化收集、存储、管理与分析物联网时序数据的软件系统。Apache IoTDB 采用轻量式架构，具有高性能和丰富的功能，并与Apache Hadoop、Spark和Flink等进行了深度集成，可以满足工业物联网领域的海量数据存储、高速数据读取和复杂数据分析需求。
现在假设有 1000 个节点的key。对于磁盘，一定是将这1000个节点依次写入磁盘的速度最快。但是这样读很糟糕，因为key在磁盘中完全乱了，每次读都得扫描。
Flink 社区希望能够将 Flink 的 Streaming 实时计算能力和 Lakehouse 新架构优势进一步结合，推出新一代的 Streaming Lakehouse 技术，促进数据在数据湖上真正实时流动起来，并为用户提供实时离线一体化的开发体验。Flink 社区内部孵化了 Flink Table Store （简称 FTS ）子项目，一个真正面向 Streaming 以及 Realtime的数据湖存储项目。2023年3月12日，FTS进入 Apache 软件基金会 (ASF) 的孵化器，改名为 Apache Paimon (incubating)。
简介 随着公司业务量的逐年成长，粘性会话(Sticky Session)越来越成为应用横向扩展(Scale Out)的瓶颈，为消除粘性会话，支持应用无状态(Stateless)，我们SOA团队在今年发起了集中式会话服务器(Centralized SessionServer)项目，该项目的核心是一个我们独立设计和开发的高性能持久化的Key/Value存储引擎，我们称为SessionDB，本文介绍SessionDB存储引擎的特性，架构和设计，我们的性能优化，并做出性能评测和分析。 我们的Key-Value存储引
存储布局，上图显示了x-engine的架构，X-Engine 将每个表分成多个字表，并未每个字表维护一个LSM树，关联快照和索引，x-engine中的每个数据库中包含一个重做日志，每个LSM树由一个位于主存储器中的热数据层和一个位于NVM/SSD/HDD的数据处理层组层，热，温，冷不同的数据的层次在系统中存储在不同访问频率的层次中，热数据包含一个活动的内存表和多个不可变的内存表，他们是跳表，用于存储最近插入的记录，并缓冲热记录的缓存，这里不同访问频度的数据已树桩的结构组织数据，树的每个层级的存储有一个排序的extent序列来组织。extent 包含记录快以及关联的过滤器和索引。我们正在探索机器学习技术与数据访问拼读之间的关系。
第二章讲了上层抽象：数据模型和查询语言。本章下沉一些，聚焦数据库底层如何处理查询和存储。这其中，有个逻辑链条：
不同的数据库存储系统都会设计不同的索引结构来优化查询/写入效率， 在讨论这些结构之前， 我们先从头回顾一下计算机存储的一些设计
LSM Tree（Log-structured merge-tree）广泛应用在HBase，TiDB等诸多数据库和存储引擎上，我们先来看一下它的一些应用：
HBase是一个开源的、分布式的、版本化的NoSQL数据库（即非关系型数据库），依托Hadoop分布式文件系统HDFS提供分布式数据存储，利用MapReduce来处理海量数据，用Zookeeper作为其分布式协同服务，一般用于存储海量数据。HDFS和HBase的区别在于，HDFS是文件系统，而HBase是数据库。HBase只是一个NoSQL数据库，把数据存在HDFS上。可以把HBase当做是MySQL，把HDFS当做是硬盘。
这部分内容主要回答我们在文章开头提到的第二个问题。第二个问题展开其实是一连串的问题。例如：lsm派系难道只有lsm tree这一类存储模型吗？如果答案是否定的，那么除了lsm tree存储模型外，还有哪些lsm 模型？这些模型之间又有哪些相同点和差异点？
十多年前，谷歌发布了大名鼎鼎的"三驾马车"的论文，分别是GFS(2003年)，MapReduce（2004年），BigTable（2006年），为开源界在大数据领域带来了无数的灵感，其中在 “BigTable” 的论文中很多很酷的方面之一就是它所使用的文件组织方式，这个方法更一般的名字叫 Log Structured-Merge Tree。在面对亿级别之上的海量数据的存储和检索的场景下，我们选择的数据库通常都是各种强力的NoSQL，比如Hbase，Cassandra，Leveldb，RocksDB等等，这其中前两者是Apache下面的顶级开源项目数据库，后两者分别是Google和Facebook开源的数据库存储引擎。而这些强大的NoSQL数据库都有一个共性，就是其底层使用的数据结构，都是仿照“BigTable”中的文件组织方式来实现的，也就是我们今天要介绍的LSM-Tree。
LSM-tree是由两个或两个以上存储数据的结构组成的。最简单的LSM-tree有两个部分，如下图所示。常驻内存部分，称为C_0树（或C_0），其可以设计为任何方便键值查找的数据结构，常驻硬盘部分，称为C_1树（或C_1）。C1进一步可延申为C_2，C_3等等。
在计算机领域，有一个有趣的趋势，往系统中写入数据需要做更多的工作。我们需要对数据进行重新组织、合并、重新建立数据库索引等操作，才能使写入的内容更加有用。如果不这样做，必须实现内容搜索或其他工作来支持未来的数据读取。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
