- 综合排序
- 最热优先
- 最新优先
- 来自专栏机械之心
LSM 树
# LSM 树 # 什么是 LSM 树 LSM 树具有以下 3 个特点： 将索引分为内存和磁盘两部分，并在内存达到阈值时启动树合并（Merge Trees）； 用批量写入代替随机写入，并且用预写日志 WAL LSM 树的这些特点，使得它相对于 B+ 树，在写入性能上有大幅提升。所以，许多 NoSQL 系统都使用 LSM 树作为检索引擎，而且还对 LSM 树进行了优化以提升检索性能。 因此，LSM 树至少需要由两棵树组成，一棵是存储在内存中较小的 C0 树，另一棵是存储在磁盘中较大的 C1 树。 解决方案就是：LSM 树（Log Structured Merge Trees）。 # 参考资料 检索技术核心 20 讲 数据结构 树 LSM 树
78720编辑于 2023-04-07 - 来自专栏用户1337634的专栏
概要介绍LSM树
LSM(Log Structured Merged Tree)树一般用在写多读少的场景，比如日志类型的数据，是HBase、 Cassandra、 LevelDB、 RocksDB 以及 ClickHouse typical LSM backed system ? SSTable (Sorted String Table) LSM-Tree的优点和缺点 与B-tree系列数据结构相比，LSM的写性能提升10作用倍，读性能降低10倍左右（但是使用布隆过滤器Bloom Trees: What Powers Write-Heavy Databases LSM 树详解 平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了 一文了解数据库索引：哈希、B-Tree 与 LSM 深入理解什么是LSM-Tree 日志结构的合并树 The Log-Structured Merge-Tree LSM-tree vs B-tree
84410发布于 2021-06-22 - 来自专栏java达人
LSM树 与B+树比较
这就是B+树的原理，但是写起来就很糟糕，因为会产生大量的随机IO，磁盘寻道速度跟不上。 关于b树 B+树最大的性能问题是会产生大量的随机io。随着新数据的插入，叶子节点会慢慢分裂。 关于lsm树 LSM 树本质上是读写之间的平衡。与B+树相比，它牺牲了部分读取性能来提高写入性能。 读取的时候，因为我们不知道数据在哪棵树上，所以必须遍历所有的树，但是每棵树中的数据都是有序的。 以上就是LSM树最本质的原理，有了原理，再看具体的技术就很简单了： 关于lsm内存结构，可以是B+树，还可以为跳跃表（skip-list）或是一个有序字符串表（SSTables）。 如上所述，LSM 树只是一堆小树。内存中的小树叫做memstore。每次flush时，内存中的 memstore 都会成为磁盘上的storefile。 为什么有一个compact过程？ 这很简单。
1.2K20编辑于 2022-05-16 - 来自专栏Spark学习技巧
从B+树到LSM树，及LSM树在HBase中的应用
本文先由B+树来引出对LSM树的介绍，然后说明HBase中是如何运用LSM树的。 回顾B+树 为什么在RDBMS中我们需要B+树（或者广义地说，索引）？一句话：减少寻道时间。 日志结构合并树（LSM Tree）就是作为B+树的替代方案产生的。 认识LSM树 LSM树由Patrick O'Neil等人在论文《The Log-Structured Merge Tree》中提出，它实际上不是一棵树，而是2个或者多个树或类似树的结构（注意这点）的集合 下图示出最简单的有2个结构的LSM树。 ? 在LSM树中，最低一级也是最小的C0树位于内存里，而更高级的C1、C2...树都位于磁盘里。 HFile就是LSM树中的高层实现。
2.5K30发布于 2020-07-15 - 来自专栏全栈程序员必看
关于LSM树_完全m叉树
关于LSM树 LSM树，即日志结构合并树(Log-Structured Merge-Tree)。其实它并不属于一个具体的数据结构，它更多是一种数据结构的设计思想。 大多NoSQL数据库核心思想都是基于LSM来做的，只是具体的实现不同。所以本来不打算列入该系列，但是有朋友留言了好几次让我讲LSM树，那么就说一下LSM树。 随机读写比顺序读写慢很多，为了提升IO性能，我们需要一种能将随机操作变为顺序操作的机制，于是便有了LSM树。LSM树能让我们进行顺序写磁盘，从而大幅提升写操作，作为代价的是牺牲了一些读性能。 LSM树原理 LSM树由两个或以上的存储结构组成，比如在论文中为了方便说明使用了最简单的两个存储结构。 关于优化措施 本文用图阐述LSM的基本原理，但实际项目中其实有很多优化策略，而且有很多针对LSM树优化的paper。
51710编辑于 2022-11-17 深入理解LSM树
今天我们聊聊 LSM 树。 可能这是你第一次听说 LSM 树，但 LSM 树其实已经是我们的老朋友了，大多数 NoSQL 如 HBase、LevelDB、Cassandra、RocksDB 等底层都有 LSM 树的身影。 LSM 树的架构与优势LSM 树的优点就是写入速度快，写入快的秘密在于 LSM 树利用了磁盘的顺序写，这使得 NoSQL 的性能优于关系型数据库。 下图是 LSM 树的逻辑示意图，LSM 树是一个多层结构，自上而下存储的数据越来越多。 总结今天我们聊了 LSM 树的相关知识，我们首先介绍了 LSM 树的原理，其实 LSM 并不是树，而是一个多层的读写流程，LSM 树本身是为了解决快速写入的问题而设计的，LSM 树利用了磁盘的顺序读写能力
74410编辑于 2024-08-06- 来自专栏我是攻城师
什么是2-3树
2-3树 VS 二叉搜索树 同样的一组数据，在2-3树和二叉搜索树里面的对比如下： ? 可以看到2-3树的节点分布非常均匀，且叶子节点的高度一致，并且如果这里即使是AVL树，那么树的高度也比2-3树高，而高度的降低则可以提升增删改的效率。 2-3树的插入 为了保持平衡性，2-3树的插入如果破坏了平衡性，那么树本身会产生分裂和合并，然后调整结构以维持平衡性，这一点和AVL树为了保持平衡而产生的节点旋转的作用一样，2-3树的插入分裂有几种情况如下 2-3树的删除 2-3树节点的删除也会破坏平衡性，同样树本身也会产生分裂和合并，如下： ? 总结 本篇文章，主要介绍了2-3树相关的知识，2-3树，2-3-4树以及B树都不是二叉树，但与二叉树的大致特点是类似的，它们是一种平衡的多路查找树，节点的孩子个数可以允许多于2个，虽然高度降低了，但编码相对复杂
2.3K20发布于 2019-04-28 - 来自专栏算法无遗策
动画 | 什么是2-3树？
2-3树正是一种绝对平衡的树，任意节点到它所有的叶子节点的深度都是相等的。 2-3树的数字代表一个节点有2到3个子树。它也满足二分搜索树的基本性质，但它不属于二分搜索树。 2-3树查找元素 2-3树的查找类似二分搜索树的查找，根据元素的大小来决定查找的方向。 动画：2-3树插入 2-3树删除元素 2-3树删除元素相对比较复杂，删除元素也和插入元素一样先进行命中查找，查找成功才进行删除操作。 2-3树为满二叉树时，删除叶子节点 2-3树满二叉树的情况下，删除叶子节点是比较简单的。 动画：2-3树删除 -----END---
1K10发布于 2020-01-02 - 来自专栏Android知识点总结
2-3树与红黑树
第一次接触红黑树是在关于hashMap，上来就扔五个特性，说满足这五个特点的二分搜索树就是红黑树。 （1）每个节点或者是黑色，或者是红色。 （2）根节点是黑色。 瞬时懵逼……我扔十个特性，是不是能定义一个红绿灯树呢。所以一直不明白红黑树为什么要这么定义。 直到今天了解了2-3树，才豁然开朗。2-3树是一种神奇的树，它能够保证该树是一个完美树。 2-3树可以演化成红黑树，这便是保证红黑树效率的根本。 先说奇葩的2-3树，首先2-3树满足二分搜索树，但每个节点可能存在1或2个数据，对应的该节点就可能存在2或3个子节点 2-3树 ? 2-3树引入.png 2-3树插入操作： ? 2-3树.png 2-3树演化为红黑树 将三节点拆为两个节点，并将左数据节点设为红色来实现2-3树同等功能 ? 红黑树.png
59030发布于 2018-09-29 - 来自专栏算法无遗策
动画 | 什么是红黑树？（基于2-3树）
学习过2-3树之后就知道应怎样去理解红黑树了，如果直接看「算法导论」里的红黑树的性质，是看不出所以然。 此时我们借着2-3树去理解基本的红黑树，当然我会在后几篇文章介绍2-3-4树以及基于2-3-4树的红黑树。 抛开上面二分搜索树满足红黑的性质，我们知道2-3树不是二叉树，我们把它转换成一颗二叉树，2-节点很好转，3-节点转二叉却有两种，如下图： ? （和2-3树等价的，任意节点到其叶子节点的高度都是相同的）。 因为2-3树不存在永久的4-节点，4-节点终归要分解的（在2-3-4树中，为了更好地插入和删除，4-节点可存在于叶子节点和非叶子节点）2-3树一样不行，所以在2-3树中没有任何一个节点能同时和两条红链接相连
1K20发布于 2020-01-02 - 来自专栏机器学习入门
算法原理系列：2-3查找树
结构缘由 首先，搞清楚2-3查找树为什么会出来，它要解决什么样的问题？假设我们对它的基本已经有所了解了。先给它来个简单的定义： 2-3查找树： 一种保持有序结构的查找树。 而2-3树就是为了规避上述问题而设计发明出来的模型。现在请思考该如何设计它呢？ 这里我们从BST遇到的实际问题出发，提出设计指标，再去思考利用些潜在的性质来构建2-3树。 这部分内容，没有什么理论根据，而是我自己尝试去抓些字典的性质来构建，而2-3树的诞生过程并非真的如此，所以仅供参考。 构建2-3树 字典的两个主要操作为：查找和插入。 我就不卖关子了，直接给出2-3树的其中一个基本定义： 一棵2-3查找树或为一颗空树，或由以下节点组成： 2-节点：含有一个键和两条链接，左链接指向的2-3树中的键都小于该节点，右链接指向的2-3树中的键都大于该节点 3-节点：含有两个键和三条链接，左链接指向的2-3树中的键都小于该节点，中链接指向的2-3树中的键都位于该节点的两个键之间，右链接指向的2-3树中的键都大于该节点。 ！！！
1.1K20发布于 2019-05-26 - 来自专栏肉眼品世界
TiDB 底层存储结构 LSM 树原理介绍
，也就是用的 LSM 树。 2 LSM 树算法大概思路 LSM 树由两个或多个树状的结构组成。 这一节我们以两个树状的结构构成的简单的双层 LSM 树举例，来简单说下 LSM 树大概思路，让大家对 LSM 树实现有个整体的认识。 5 LSM 树的插入、修改、删除 从 LSM 树的名字，Log-Structured-Merge-Tree 日志结构合并树中我们大概就能知道 LSM 树的插入、修改、删除的方法了——顺序追加而非修改(对磁盘操作而言 查找时， LSM 树需要遍历所有层次的树，查找效率上要低于 B+ 树，但 LSM 树写入时节省的磁盘资源占用，可以一定程度上弥补读效率上的差距。
1.2K71编辑于 2023-02-12 - 来自专栏johnhuster
计算机基础之:LSM树
使用过hbase、cassandra之类nosql数据库的小伙伴对LSM树结构应该有所耳闻，那么这种数据结构有哪些优劣势呢，本文做下简单介绍。 LSM（全称：Log-Structured Merge Tree）是一种广泛应用于现代数据库和存储系统的数据结构，尤其适合于写密集型应用场景。 想象一下LSM如同一个高效的图书馆管理系统，我们通过它的优势与劣势来形象生动地描述这一概念。 高效查询：尽管书籍的最终位置可能在多次合并后才确定，但LSM通过维护一个指向书籍最新位置的索引（内存索引），让读者（查询）能迅速找到所需书籍，保证了查询的效率。 空间开销：LSM的后台合并过程会产生一定的空间冗余，就像图书馆在整理书籍时，旧的索引卡可能还在，新的索引卡已生成，这期间会有数据的重复存储。
34510编辑于 2024-06-02 - 来自专栏五分钟学算法
数据结构与算法——2-3树
因此，引入了 2-3 树来提升效率。2-3 树本质也是一种平衡搜索树，但 2-3 树已经不是一棵二叉树了，因为 2-3 树允许存在 3 这种节点，3- 节点中可以存放两个元素，并且可以有三个子节点。 2-3 树定义 2-3 树的定义如下： （1）2-3 树要么为空要么具有以下性质： （2）对于 2- 节点，和普通的 BST 节点一样，有一个数据域和两个子节点指针，两个子节点要么为空，要么也是一个2 （4）所有叶子点都在树的同一层。 2-3树查找 2-3 树的查找类似二叉搜索树的查找过程，根据键值的比较来决定查找的方向。 例如在图 2.1 所示的 2-3 树中查找键为H的节点： ? img 2-3树为满二叉树，删除叶子节点 操作步骤：若2-3树是一颗满二叉树，将2-3树层树减少，并将当前删除节点的兄弟节点合并到父节点中，同时将父节点的所有兄弟节点合并到父节点的父节点中，如果生成了4 img 结语 2-3 树作为一种平衡查找树，查询效率比普通的二叉排序树要稳定许多。
79810发布于 2019-09-03 - 来自专栏算法之名
LSM树（Log-Structured Merge Tree）存储引擎浅析
下图是最简单的二层LSM Tree. ? 图来自lsm论文 lsm tree，理论上，可以是内存中树的一部分和磁盘中第一层树做merge，对于磁盘中的树直接做update操作有可能会破坏物理block的连续性，但是实际应用中，一般lsm有多层， LSM树相比于B+树（大量的叶节点操作，不仅支持单条记录的增、删、读、改操作，还支持顺序扫描（B+树的叶子节点之间的指针）， 对B树的写入过程是一次原位写入的过程，主要分为两个部分，首先是查找到对应的块的位置 LSM树原理把一棵大树拆分成N棵小树，它首先写入内存中，随着小树越来越大，内存中的小树会flush到磁盘中，磁盘中的树定期可以做merge操作，合并成一棵大树，以优化读性能。 总结为，LSM树并不是像B+树单次在磁盘寻址，根据索引来进行写入。而是大量堆集内存，达到一定阈值后，写入磁盘，因为是批量处理，磁盘IO对其性能影响很小，对写操作的性能大大提升。
1.2K20发布于 2019-08-20 - 来自专栏小工匠聊架构
Algorithms_LSM树（Log-Structured Merge Tree）
LSM树的原理 LSM树是一种用于高性能数据存储的数据结构，其核心思想是优化写入操作，特别是在磁盘或闪存存储上。 LSM树的使用场景 现在，让我们探讨LSM树在不同使用场景中的应用： 2.1 分布式数据库系统 分布式数据库系统需要高性能的写入操作，以处理大量的事务和数据更新。 写入性能： LSM树：LSM树在写入性能上非常出色。它采用追加写入的方式，将新数据追加到写入日志中，然后通过合并操作将数据批量写入磁盘。 B+树：B+树不需要类似的合并操作，因为它们的结构不会导致数据碎片。 5. 使用场景的不同： LSM树：LSM树通常适用于写入密集的工作负载，如分布式数据库、日志存储和时间序列数据。 根据工作负载的特点，可以选择LSM树来获得高写入性能，或选择B+树来获得高读取性能。 结论 LSM树是一种高性能的数据存储结构，通过优化写入操作，使其在众多应用场景中得以广泛应用。
1.2K20编辑于 2023-11-09 - 来自专栏全栈程序员必看
LSM树详解_黑龙江野生鱼品种
LSM树(Log-Structured-Merge-Tree)的名字往往会给初识者一个错误的印象，事实上，LSM树并不像B+树、红黑树一样是一颗严格的树状数据结构，它其实是一种存储结构，目前HBase ,LevelDB,RocksDB这些NoSQL存储都是采用的LSM树。 LSM树的核心特点是利用顺序写来提高写性能，但因为分层(此处分层是指的分为内存和文件两部分)的设计会稍微降低读性能，但是通过牺牲小部分读性能换来高性能写，使得LSM树成为非常流行的存储结构。 1、LSM树的核心思想 如上图所示，LSM树有以下三个重要组成部分： 1) MemTable MemTable是在内存中的数据结构，用于保存最近更新的数据，会按照Key有序地组织这些数据，LSM树对于具体如何组织有序地组织数据并没有明确的数据结构定义 3、总结 LSM树是非常值得了解的知识，理解了LSM树可以很自然地理解Hbase，LevelDb等存储组件的架构设计。
50540编辑于 2022-11-16 - 来自专栏一个技术人的金融之路
简讲LSM树（Log-Structured Merge Tree）
前言：最近在了解大数据实时分析技术druid,究其原理时发现用到了类LSM树思想以实现高效的数据插入，于是展开了对LSM的了解，了解之后感觉这东西虽然也并没有很特别，但在大数据、分布式架构中的应用还是非常有价值的 应用实例主要为关系型数据库mysql/mongodb等 LSM树（Log-Structured Merge Tree）存储引擎和B树存储引擎一样，同样支持增、删、读、改、顺序扫描操作。 当然凡事有利有弊，LSM树和B+树相比，LSM树牺牲了部分读性能，用来大幅提高写性能。 前面提到HBase用到了LSM树思想，下面以其为例简单做下图解： hbase.png LSM思想中的两个要点：“拆分小树”、“合并大树”，在HBase中如何体现呢： 数据插入不是直接写到磁盘，而是先写入内存 通过以上的分析，应该知道LSM树的由来了，LSM树的设计思想非常朴素：将对数据的修改增量保持在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘，不过读取的时候稍微麻烦，需要合并各个磁盘中历史数据和内存中最近修改操作
3.1K70发布于 2018-07-26 - 来自专栏yaphetsfang
算法和数据结构: 八 平衡查找树之2-3树
本文首先介绍2-3查找树(2-3 Search Tree)，后面会在此基础上介绍红黑树和B树。 定义 和二叉树不一样，2-3树运行每个节点保存1个或者两个的值。 如果中序遍历2-3查找树，就可以得到排好序的序列。在一个完全平衡的2-3查找树中，根节点到每一个为空节点的距离都相同。 ? 插入完成，变为平衡2-3查找树，树的高度从0变为1。 所以只需要常数次操作即可完成2-3树的平衡。 ? 性质 这些本地操作保持了2-3树的平衡。对于4-node节点变形为2-3节点，变形前后树的高度没有发生变化。 在2-3查找树基础上改进的红黑树不仅具有较高的效率，并且实现起来较2-3查找树简单。 但是2-3查找树作为一种比较重要的概念和思路对于后文要讲到的红黑树和B树非常重要。
1.1K20发布于 2020-07-30 - 来自专栏labuladong的算法专栏
存储系统中的算法：LSM 树设计原理
LevelDB 整个库的代码只有几百 KB，所以我去研究了 LSM 树的代码实现，总结了这篇文章，带你了解 LSM 树的设计原理。 什么是 LSM 树呢？ 综上，B 树的难点在于平衡性维护和并发控制，一般用在读多写少的场景。 LSM 树是数据不可变的代表结构。你只能在尾部追加新数据，不能修改之前已经插入的数据。 后面我会讲讲真正的 LSM 树如何针对读场景进行优化，但再怎么优化，肯定也达不到 B 树的读取效率。 同时，LSM 树还有一个明显弊端就是存在空间放大。 LSM 树不可能向 B 树那样维护所有数据的有序性，但可以维护局部数据的有序性，从而一定程度提升读性能。 LSM 树的设计 就我的理解，LSM 树其实不是一种数据结构，而是一种存储方案。 这样，借助 LSM 树的层级结构和SSTable的有序性，就能利用二分搜索提升查找效率，避免线性查找键值对。
90110编辑于 2022-12-10
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号