前言 相信大家之前都了解过很多种数据结构，我之前总是两两的，也就是从局部上去进行比较，没有从整体上进行这些树的发展脉络进行梳理，因此经常看完没多久就忘了。看来确实是需要从本源出发，不仅要知其然还要知其所以然，了解清楚前因后果，不仅可以方便我们记忆，更有利于增加我们的理解深度。实际上任何事物的出现都是有他出现的必要性，当某个事物达到瓶颈之后，必然会出现新的事务来弥补它的不足。好的，废话不多说了，今

  LSM Tree（log-structured merge-tree）是一种文件组织结构的数据结构，目前在不少数据库中都有使用到，如SQLite、LevelDB、HBase在Mongodb中也有一个LSM引擎；   在传统的关系型数据库中使用的是B-/B+ tree作为索引的数据结构，B tree的查询性能很高，为O(log n)复杂度，但其写性能并达不到O(log n)，而在传统数据库中每

  前篇文章对LSM的基本原理，算法流程做了简单的介绍，这篇文章将实现一个简单的基于LSM算法的迷你Key-Value数据库，结合上篇文章的理论与本篇文章的实践使之对LSM算法有更好的理解，当然此版本还有很大问题只是Demo模型，后面也会指出；   此LSMDB有支持常见的数据库四大功能：CURD（增删查改），从前篇文章可知要实现基于LSM的数据库此程序中需存在这么几种数据结构：memTable

  上篇文章简单的实现了基于LSM数据库的初步版本，在该版本中如数据写入到内存表后但还未持久化到SSTable排序字符串表，此时正好程序崩溃，内存表中暂未持久化的数据将会丢失。 引入WAL   为了解决上述问题，将引入数据库中常用于解决类似问题的方法：WAL（Write Ahead Log）预写式日志——在计算机科学中，WAL（预写式日志）是数据库系统提供原子性和持久性的一系列技术；也就是说WA

  上篇文章简单的填了一个坑基于LSM数据库的实现了WAL，在该版本中如数据写入到内存表的同时将未持久化的数据写入到WAL文件，在未将数据持久化时程序崩溃，可通过WAL文件将数据还原恢复从而避免了数据的丢失。 目前此基于LSM的数据库还有三大坑：    1、索引问题    2、SSTable合并问题    3、单机版本问题；   本篇文章将解决其中的一个坑，索引问题； 索引问题   到目前

作者：京东物流 刘家存随着数据量的增大，传统关系型数据库越来越不能满足对于海量数据存储的需求。对于分布式关系型数据库，我们了解其底层存储结构是非常重要的。本文将介绍下分布式关系型数据库 TiDB 所采用的底层存储结构 LSM 树的原理。[]()1 LSM 树介绍LSM 树（Log-Structured-Merge-Tree) 日志结构合并树由 Patrick O’Neil 等人在论文《The Lo

LSM-Tree全称Log Structured Merge Tree，是一种分层、有序、面向磁盘的数据结构，其核心思想是充分利用磁盘的顺序写性能要远高于随机写性能这一特性，将批量的随机写转换为一次性的顺序写。LSM-Tree的写入操作，类似于普通的日志写入方式，以Append的模式追加；删除操作Append一条删除的日志；修改操作Append一条新key-value。LSM-Tree非就地更新数

LSM-Tree - LevelDb了解和实现引言自从[[《数据密集型型系统设计》LSM-Tree VS BTree]]这篇文章完成之后，对于LSM-Tree这种结构非常感兴趣，于是趁热打铁在之后的几天静下心来研究了一下LevelDB的具体实现，最终阅读了一下源代码。本文涉及了LevelDB的基础功能和相关数据结构的介绍，最后讲述LevelDB中至关重要的读写操作，通过设计数据结构和读写操作的讲解

LSM-Tree - LevelDb 源码解析引言在上一篇文章[[LSM-Tree - LevelDb了解和实现]]中介绍了LevelDb相关的数据结构和核心组件，LevelDB的核心读写部分，以及为什么在这个数据库中写入的速度要比读取的速度快上好几倍。 LevelDB的源代码还是比较好懂的，好懂到我只学过学JAVA只有定点基础C语言入门知识的人也能看懂，另一方面作者在关键的地方都给了注释，甚至告

LSM-Tree - LevelDb Skiplist跳表跳表介绍跳表（SkipList）是由William Pugh提出的。他在论文《Skip lists: a probabilistic alternative to balanced trees》中详细地介绍了有关跳表结构、插入删除操作的细节。文档：Skiplist跳表原始论文 - pugh-skiplists-cacm1990.pdf链接：

LSM-Tree - LevelDb布隆过滤器引言布隆过滤器有点类似哈希表，但是比哈希表的效率要更高，因为使用了位来判断Key是否存在，布隆过滤器在完成高效搜索key是否存在的同时带来一定的副作用-- 不保证Key一定存在，所以它只适用于允许一定容错率的系统。一句话概括：Bloom Filter 是一个基于概率的数据结构，它只能告诉我们一个元素绝对不在集合内或可能在集合内。布隆过滤器比较悬浮的东西

LSM-Tree - LevelDb之LRU缓存引言LRU缓存在各种开源组件中都有使用的场景，常常用于做冷热数据和淘汰策略，使用LRU主要有三点。第一点是实现非常简单。第二点是代码量本身也不错。最后涉及数据结构非常经典。LevelDB对于LRU缓存实现算是比较经典的案例，这一节来介绍它是如何使用LRU实现缓存的。LeetCode 中有一道相应LRU缓存算法的题目，感兴趣可以做一做：lru-cach

本文系北京大学智能学院在读博士生胡琳所著，目前于 OceanBase 存储组实习，本篇也是 OceanBase 学术系列稿件第二篇。「胡琳：北京大学智能学院在读博士生，博士期间在北京大学数据管理组从事GPU加速图算法的研究，在图算法加速领域取得了一定的成果，发表在SIGMOD等知名会议上，将继续在图计算领域努力探索。」OceanBase 等以 LSM tree 为存储架构的数据库的 compact

内容参考对分布式对定义参考这篇文章：微服务都想用，先把分布式和微服务之间的关系说清楚对分布式架构中心或无中心对比参考这篇文章：分布式存储单主、多主和无中心架构的特征与趋势对HDFS对内部机制参考这篇文章：Hadoop分布式文件系统I/O原理机制的深度解读分布式文件系统HDFS无索引就无K/V首先分布式数据并不是绝对的喜欢使用kv存储模式，例如分布式数据库里面mongodb和elasticsearc

Lethe【SIGMOD'20】论文阅读笔记Lethe: A Tunable Delete-Aware LSM Enginehttps://dl.acm.org/doi/10.114...简介FADE + KiWi。使用非常小的额外元数据、新的delete-aware压缩策略、新的存储布局。背景LSM-tree逻辑删除的问题：（逻辑删除：插入tombstone，使目标键的旧条目失效）空间放大：保留

简介： LSM-Tree 是很多 NoSQL 数据库引擎的底层实现，例如 LevelDB，Hbase 等。本文基于《数据密集型应用系统设计》中对 LSM-Tree 数据库的设计思路，结合代码实现完整地阐述了一个迷你数据库，核心代码 500 行左右，通过理论结合实践来更好地理解数据库的原理。作者 | 萧恺来源 | 阿里技术公众号前言LSM-Tree 是很多 NoSQL 数据库引擎的底层实现，例如 L

LSM简介 Log Structured Merge Tree，下面简称 LSM。2006年，Google 发表了 BigTable 的论文。这篇论文提到 BigTable 单机上所使用的数据结构就是 LSM。目前，LSM 被很多存储产品作为存储结构，比如 Apache HBase, Apache Cassandra, MongoDB 的 Wired Tiger 存储引擎, LevelDB 存