【大数据】LSM树,专为海量数据读写而生的数据结构

本文涉及的产品
云原生数据库 PolarDB MySQL 版,Serverless 5000PCU 100GB
云原生数据库 PolarDB PostgreSQL 版,企业版 4核16GB
推荐场景:
HTAP混合负载
云原生数据库 PolarDB MySQL 版,通用型 2核4GB 50GB
简介: 【大数据】LSM树,专为海量数据读写而生的数据结构

1.什么是LSM树?

LSM树(Log-Structured Merge Tree)是一种专门针对大量写操作做了优化的数据存储结构,尤其适用于现代大规模数据处理系统,如NoSQL数据库(如Cassandra、HBase、RocksDB等)和键值存储。尽管其名称中包含“树”,但它并不直接对应于传统的树状数据结构,而是指一种数据管理策略或体系架构。


LSM为什么会出现:


当数据量大了之后,读操作采用顺序遍历来进行查找肯能是不行的,性能太低了。所以需要维护一种数据结构用来帮助提升读的效率,在关系型数据库中用B+树(索引)来维护数据的关系,便于查找。


B树和B+树详细内容可移步作者的另一篇文章,作者有个数据结构专栏,专门讲解了所有常用数据结构:


数据结构(8)树形结构——B树、B+树(含完整建树过程)_排序好的数怎么画b+树-CSDN博客

a5eb054b53e2485db3e302fc63b72bbc.png



关系型数据库中对B+树的使用在读的时候性能不错,但是在写的时候存在明显的性能问题。不是说B+树这种数据结构在写的时候存在性能问题,而是关系型数据库中是将树结构存在磁盘上的,并且树的节点在磁盘上的存储是分散的,数据的存储也是分散的,这种落地方式在面对写操作的时候会有性能瓶颈。


原因如下:


首先是写操作。写操作是容易引起B+树的结构的调整的,要调整树的结构当然要去读写树的节点,树的整个结构都存在磁盘上的,所以要走磁盘IO,调整树当然就要去对磁盘上存的树的节点进行读写,B+树在磁盘中的存储是分散的,所以这里的IO是随机IO。写数据的时候,数据也不是顺序存放的,也是分散存放的,也会是随机IO。


其次是读操作,即使B+树尽力优化了树的层高,减少了磁盘IO次数,但是毕竟树的节点和数据不是顺序写入进行存储的,所以在访问的时候还是会进行随机IO,在关系型数据库的场景下倒是没什么问题,在大数据场景下要读的数据量是海量的,海量数据都是进行随机IO的读,性能上来说也是不佳的。


所以在海量数据的写入的时候B+树不是一个优质的选择。对着大数据场景的出现,LSM树出现,用于专门应对海量数据的写入。


总结一下B+树面对海量数据无力是因为:


树存在磁盘上,读写都是磁盘IO


树是分散存放的,读写都是随机IO


数据是分散存放的,读写都是随机IO


LSM树其实就是一套打法,核心目的就是为了规避上面的问题。


LSM树会将树结构放在内存中,从而规避磁盘IO,当然内存是有限的,到了一定条件后会将当前内存中这个版本的树存到磁盘中,存磁盘的时候开辟一块连续空间,将树的节点连续存储在一起,然后刷新内存再重新开始存新进来的内容。读的时候就会先去读内存,内存中没有再去读磁盘。由于磁盘中树的节点是连续写在一起的,会减少随机IO。


当在落磁盘的时候,磁盘上如果有历史版本的话,会和最新的历史版本进行合并。也就是说越新的历史版本,树越”茂盛“:


1dc06eaccf3347038f46a79b38120319.png


2.LSM树的落地实现

LSM树的落地实现通常包含内存中的MemTable(内存表)和磁盘上的SSTable(Sorted String Table,有序字符串表)两部分。


数据首先写入内存中的MemTable,数据在memtable中就会被组织成平衡二叉树:


b9665ae3dca24cf0b50466ca09db343c.png


当MemTable达到一定大小时,会被转换为不可变的SSTable并刷写到磁盘,写入磁盘的时候会开辟一段连续的存储空间,将树的内容连续存储在一起:


4e89c68d0e0d4b5f9b39f5c0d286251c.png


除了上面的内容外,还有一个核心内容——Compaction,合并。


由于肯定会落多次磁盘,生成多个版本的sstable,会浪费磁盘空间,所以还会存在合并操作,将多棵小树合成一棵大树。合并的时机一般有两个:


一个时机是在落磁盘生成新的sstable的时候会和之前最新的历史版本对应的sstable进行一次合并,两棵小树合并出一棵大树来。另一个时机是磁盘的存储达到一定阈值之后多个历史版本的sstable会进行合并合并出一棵大树来。


还有最后一个问题就是如何删除LSM树中的元素?


在memtable中删除了,但是sstable中还有,直接删除是没有用的,下次合并的时候还是会把已经删除的元素合并进来。所以LSM的做法是给要删除的元素打上一个墓碑标记,墓碑标记用来标记数据被删除了,下次合并的时候就能通过墓碑标记来判断哪些元素不用合并进来。

相关实践学习
基于Hologres轻松玩转一站式实时仓库
本场景介绍如何利用阿里云MaxCompute、实时计算Flink和交互式分析服务Hologres开发离线、实时数据融合分析的数据大屏应用。
SaaS 模式云数据仓库必修课
本课程由阿里云开发者社区和阿里云大数据团队共同出品,是SaaS模式云原生数据仓库领导者MaxCompute核心课程。本课程由阿里云资深产品和技术专家们从概念到方法,从场景到实践,体系化的将阿里巴巴飞天大数据平台10多年的经过验证的方法与实践深入浅出的讲给开发者们。帮助大数据开发者快速了解并掌握SaaS模式的云原生的数据仓库,助力开发者学习了解先进的技术栈,并能在实际业务中敏捷的进行大数据分析,赋能企业业务。 通过本课程可以了解SaaS模式云原生数据仓库领导者MaxCompute核心功能及典型适用场景,可应用MaxCompute实现数仓搭建,快速进行大数据分析。适合大数据工程师、大数据分析师 大量数据需要处理、存储和管理,需要搭建数据仓库?学它! 没有足够人员和经验来运维大数据平台,不想自建IDC买机器,需要免运维的大数据平台?会SQL就等于会大数据?学它! 想知道大数据用得对不对,想用更少的钱得到持续演进的数仓能力?获得极致弹性的计算资源和更好的性能,以及持续保护数据安全的生产环境?学它! 想要获得灵活的分析能力,快速洞察数据规律特征?想要兼得数据湖的灵活性与数据仓库的成长性?学它! 出品人:阿里云大数据产品及研发团队专家 产品 MaxCompute 官网 https://www.aliyun.com/product/odps 
目录
相关文章
|
19天前
|
存储 算法 Linux
【数据结构和算法】---二叉树(1)--树概念及结构
【数据结构和算法】---二叉树(1)--树概念及结构
14 0
|
27天前
|
存储 算法
【树】数据结构——树和二叉树的概念&笔记
【树】数据结构——树和二叉树的概念&笔记
|
29天前
数据结构 树(第10-14天)
数据结构 树(第10-14天)
|
13天前
|
存储
【数据结构】AVL树——平衡二叉搜索树
【数据结构】AVL树——平衡二叉搜索树
|
1月前
|
存储 算法 测试技术
数据结构学习记录——树习题-Complete Binary Search Tree(题目描述、输入输出示例、数据结构的选择、核心算法、计算左子树的规模)
数据结构学习记录——树习题-Complete Binary Search Tree(题目描述、输入输出示例、数据结构的选择、核心算法、计算左子树的规模)
25 1
|
1月前
|
测试技术 C语言
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
21 1
|
1月前
|
机器学习/深度学习
数据结构学习记录——堆的小习题(对由同样的n个整数构成的二叉搜索树(查找树)和最小堆,下面哪个说法是不正确的)
数据结构学习记录——堆的小习题(对由同样的n个整数构成的二叉搜索树(查找树)和最小堆,下面哪个说法是不正确的)
16 1
|
19天前
|
存储 算法
【C/数据结构与算法】:树和二叉树
【C/数据结构与算法】:树和二叉树
16 0
|
20天前
数据结构篇:旋转操作在AVL树中的实现过程
数据结构篇:旋转操作在AVL树中的实现过程
8 0
|
20天前
|
编译器 数据库 索引
数据结构篇:树形数据结构的基本概念及其遍历方法
数据结构篇:树形数据结构的基本概念及其遍历方法
8 0