数据库存储引擎;数据库存储引擎有哪几种 收藏 0

MySQL存储引擎及索引简介

作者：京东物流 樊芳渝

在信息技术飞速发展的今天，数据库作为信息系统的核心组件，其性能和稳定性直接关系到整个系统的运行效率和用户体验。而MySQL，作为目前最流行的开源关系型数据库管理系统之一，凭借其强大的功能、灵活的扩展性和广泛的应用场景，早已成为众多开发者和企业的首选。

然而，要想充分发挥MySQL的性能优势，深入了解其存储引擎和索引机制是必不可少的。存储引擎决定了MySQL如何存储、处理和检索数据，不同的存储引擎在事务处理、数据完整性、并发控制等方面有着不同的特点和优势。而索引，则是MySQL高效查询的关键所在，它能够帮助数据库系统快速定位到所需的数据，极大地提高查询效率。





存储引擎就是存储数据、建立索引、更新/查询数据等技术的实现方式。存储引擎是基于表而不是基于库的，所以存储引擎也可以被称为表引擎。 默认存储引擎是InnoDB。

相关操作：

InnoDB 是一种兼顾高可靠性和高性能的通用存储引擎，在 MySQL 5.5 之后，InnoDB 是默认的 MySQL 引擎。

特点：

•DML 操作遵循 ACID 模型，支持事务

•行级锁，提高并发访问性能

•支持外键约束，保证数据的完整性和正确性

知识点：

查看 Mysql 变量：

InnoDB 逻辑存储结构：



索引是帮助 MySQL高效获取数据的数据结构（有序）。在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查询算法，这种数据结构就是索引。

优缺点：

优点：

•提高数据检索效率，降低数据库的IO成本

•通过索引列对数据进行排序，降低数据排序的成本，降低CPU的消耗

缺点：

•索引列也是要占用空间的

•索引大大提高了查询效率，但降低了更新的速度，比如 INSERT、UPDATE、DELETE



二叉树的缺点可以用红黑树来解决：



红黑树也存在大数据量情况下，层级较深，检索速度慢的问题。

为了解决上述问题，可以使用 B-Tree 结构。 B-Tree (多路平衡查找树) 以一棵最大度数（max-degree，指一个节点的子节点个数）为5（5阶）的 b-tree 为例（每个节点最多存储4个key，5个指针） 演示地址：https://www.cs.usfca.edu/~galles/visualization/BTree.html



树的度数是指一个节点的子节点个数。

结构图：



与 B-Tree 的区别：

•所有的数据都会出现在叶子节点

•叶子节点形成一个单向链表

MySQL 索引数据结构对经典的 B+Tree 进行了优化。在原 B+Tree 的基础上，增加一个指向相邻叶子节点的链表指针，就形成了带有顺序指针的 B+Tree，提高区间访问的性能。



在 InnoDB 存储引擎中，根据索引的存储形式，又可以分为以下两种：

聚集索引选取规则：

•如果存在主键，主键索引就是聚集索引

•如果不存在主键，将使用第一个唯一(UNIQUE)索引作为聚集索引

•如果表没有主键或没有合适的唯一索引，则 InnoDB 会自动生成一个 rowid 作为隐藏的聚集索引

创建索引：

查看索引：

删除索引：

查看当前数据库的 INSERT, UPDATE, DELETE, SELECT 访问频次：

慢查询日志记录了所有执行时间超过指定参数（long_query_time，单位：秒，默认10秒）的所有SQL语句的日志。 MySQL的慢查询日志默认没有开启，需要在MySQL的配置文件（/etc/my.cnf）中配置如下信息：

更改后记得重启MySQL服务，日志文件位置：/var/lib/mysql/localhost-slow.log

查看慢查询日志开关状态：

show profile 能在做SQL优化时帮我们了解时间都耗费在哪里。通过 have_profiling 参数，能看到当前 MySQL 是否支持 profile 操作：

profiling 默认关闭，可以通过set语句在session/global级别开启 profiling：

查看所有语句的耗时：

查看指定query_id的SQL语句各个阶段的耗时：

查看指定query_id的SQL语句CPU的使用情况

EXPLAIN 或者 DESC 命令获取 MySQL 如何执行 SELECT 语句的信息，包括在 SELECT 语句执行过程中表如何连接和连接的顺序。 语法：

EXPLAIN 各字段含义：

•id：select 查询的序列号，表示查询中执行 select 子句或者操作表的顺序（id相同，执行顺序从上到下；id不同，值越大越先执行）

•select_type：表示 SELECT 的类型，常见取值有 SIMPLE（简单表，即不适用表连接或者子查询）、PRIMARY（主查询，即外层的查询）、UNION（UNION中的第二个或者后面的查询语句）、SUBQUERY（SELECT/WHERE之后包含了子查询）等

•type：表示连接类型，性能由好到差的连接类型为 NULL、system、const、eq_ref、ref、range、index、all

•possible_key：可能应用在这张表上的索引，一个或多个

•Key：实际使用的索引，如果为 NULL，则没有使用索引

•Key_len：表示索引中使用的字节数，该值为索引字段最大可能长度，并非实际使用长度，在不损失精确性的前提下，长度越短越好

•rows：MySQL认为必须要执行的行数，在InnoDB引擎的表中，是一个估计值，可能并不总是准确的

•filtered：表示返回结果的行数占需读取行数的百分比，filtered的值越大越好

•如果索引关联了多列（联合索引），要遵守最左前缀法则，最左前缀法则指的是查询从索引的最左列开始，并且不跳过索引中的列。

•如果跳跃某一列，索引将部分失效（后面的字段索引失效）。

•联合索引中，出现范围查询（<, >），范围查询右侧的列索引失效。可以用>=或者<=来规避索引失效问题。

1.在索引列上进行运算操作，索引将失效。如：

1.字符串类型字段使用时，不加引号，索引将失效。如：

此处phone的值没有加引号

1.模糊查询中，如果仅仅是尾部模糊匹配，索引不会是失效；如果是头部模糊匹配，索引失效。如：

前后都有 % 也会失效。

1.用 or 分割开的条件，如果 or 其中一个条件的列没有索引，那么涉及的索引都不会被用到。

2.如果 MySQL 评估使用索引比全表更慢，则不使用索引。

是优化数据库的一个重要手段，简单来说，就是在SQL语句中加入一些人为的提示来达到优化操作的目的。

例如，使用索引：

不使用哪个索引：

必须使用哪个索引：

use 是建议，实际使用哪个索引 MySQL 还会自己权衡运行速度去更改，force就是无论如何都强制使用该索引。

当字段类型为字符串（varchar, text等）时，有时候需要索引很长的字符串，这会让索引变得很大，查询时，浪费大量的磁盘IO，影响查询效率，此时可以只降字符串的一部分前缀，建立索引，这样可以大大节约索引空间，从而提高索引效率。

语法：

前缀长度：可以根据索引的选择性来决定，而选择性是指不重复的索引值（基数）和数据表的记录总数的比值，索引选择性越高则查询效率越高，唯一索引的选择性是1，这是最好的索引选择性，性能也是最好的。 求选择性公式：

show index 里面的sub_part可以看到接取的长度

单列索引：即一个索引只包含单个列 联合索引：即一个索引包含了多个列 在业务场景中，如果存在多个查询条件，考虑针对于查询字段建立索引时，建议建立联合索引，而非单列索引。

单列索引情况：

这句只会用到phone索引字段

•多条件联合查询时，MySQL优化器会评估哪个字段的索引效率更高，会选择该索引完成本次查询

1.针对于数据量较大，且查询比较频繁的表建立索引

2.针对于常作为查询条件（where）、排序（order by）、分组（group by）操作的字段建立索引

3.尽量选择区分度高的列作为索引，尽量建立唯一索引，区分度越高，使用索引的效率越高

4.如果是字符串类型的字段，字段长度较长，可以针对于字段的特点，建立前缀索引

5.尽量使用联合索引，减少单列索引，查询时，联合索引很多时候可以覆盖索引，节省存储空间，避免回表，提高查询效率

6.要控制索引的数量，索引并不是多多益善，索引越多，维护索引结构的代价就越大，会影响增删改的效率

7.如果索引列不能存储NULL值，请在创建表时使用NOT NULL约束它。当优化器知道每列是否包含NULL值时，它可以更好地确定哪个索引最有效地用于查询

首先，我们了解到MySQL支持多种存储引擎，每种存储引擎都有其独特的特点和适用场景。例如，InnoDB是MySQL的默认存储引擎，它提供了事务支持、行级锁定和外键约束等功能，非常适合需要高可靠性和并发控制的应用场景。而MyISAM则以其快速的读操作和全文索引支持而闻名，但在事务处理和行级锁定方面相对较弱。此外，还有其他存储引擎如Memory、CSV等，它们各自在不同的应用场景中发挥着重要作用。

其次，我们深入了解了索引在MySQL中的重要性。索引是数据库系统高效查询的关键所在，它能够帮助数据库系统快速定位到所需的数据，极大地提高查询效率。我们探讨了MySQL中的几种主要索引类型，包括B树索引、哈希索引、全文索引等，并了解了它们的工作原理和适用场景。同时，我们也强调了索引的创建和维护需要谨慎进行，以避免对数据库性能产生负面影响。

最后，我们强调了在实际应用中需要根据具体需求选择合适的存储引擎和索引策略。不同的应用场景对数据库的性能、可靠性、可扩展性等方面有着不同的要求，因此我们需要根据实际需求进行权衡和选择。同时，我们也提到了MySQL在存储引擎和索引方面的不断发展和创新，如InnoDB的持续优化和新的索引类型的引入等，这些都为我们提供了更多的选择和可能性。

总之，通过今天的分享，我们对MySQL的存储引擎及索引有了更深入的认识和理解。希望这些知识能够帮助我们在实际应用中更加得心应手地处理数据库相关的问题和挑战。同时，我也鼓励大家继续深入学习和探索MySQL的更多高级特性和优化技巧，以不断提升我们的数据库管理和应用能力。

分布式数据库设计——存储引擎原理(全)

数据库的一个首要目标是可靠并高效地管理数据，以供人们使用。进而不同的应用可以使用相同的数据库来共享它们的数据。数据库的出现使人们放弃了为每个独立的应用开发数据存储的想法，同时，随着数据库广泛的使用，其处理能力飞速发展，演进出如现代的分布式数据库这般惊人的能力。为了支撑抽象的多种场景。一般的数据库都会采用多模块或多子系统的架构来构建数据库，从而方便数据库项目团队依据现实的场景来组合不同的子模块，进而构造出一众丰富的数据库产品。而存储引擎就是这一众模块中极为重要的一环。

这个世界上，没有针对数据库设计的一定之规。每个数据库都是根据它所要解决的问题，并结合其他因素慢慢发展成如今的模样的。所以数据库子模块的分化也没有一个广泛接受的标准，且有些模块之间的边界也是很模糊的。特别是需要优化数据库性能时，原有被设计为独立存在的模块很可能会融合以提高数据库整体性能。

比较典型的分布式数据库的架构和模块组合标准，因为这是大部分分布式数据库的架构模式。

1. 传输层：它是接受客户端请求的一层。用来处理网络协议。同时，在分布式数据库中，它还承担着节点间互相通信的职责。
2. 查询层：请求从传输层被发送到查询层。在查询层，协议被进行解析，如 SQL 解析；后进行验证与分析；最后结合访问控制来决定该请求是否要被执行。解析完成后，请求被发送到查询优化器，在这里根据预制的规则，数据分布并结合数据库内部的统计，会生成该请求的执行计划。执行计划一般是树状的，包含一系列相关的操作，用于从数据库中查询到请求希望获取的数据。
3. 执行层（存储引擎层）：执行计划被发送到执行层去运行。执行层一般包含本地运行单元与远程运行单元。根据执行计划，调用不同的单元，而后将结果合并返回到传输层。

细心的你可能会注意到，这里只有查询层，那么数据是怎么写入的？这对于不同的数据库，答案会非常不同。有的数据库会放在传输层，由于协议简单，就不需要额外处理，直接发送到执行层；而有些写入很复杂，会交给查询层进行处理。

以上就是数据库领域中比较常见的模块划分方式。你可能有这样的疑问：那么存储引擎在哪里呢？

执行层本地运行单元其实就是存储引擎。它一般包含如下一些功能：

1. 事务管理器：用来调度事务并保证数据库的内部一致性（这与模块一中讨论的分布式一致性是不同的）；
2. 锁管理：保证操作共享对象时候的一致性，包括事务、修改数据库参数都会使用到它；
3. 存储结构：包含各种物理存储层，描述了数据与索引是如何组织在磁盘上的；
4. 内存结构：主要包含缓存与缓冲管理，数据一般是批量输入磁盘的，写入之前会使用内存去缓存数据；
5. 提交日志：当数据库崩溃后，可以使用提交日志恢复系统的一致性状态。

以上就是存储引擎比较重要的几个功能，其核心就是提供数据读写功能，故一般设计存储引擎时，会提供对其写入路径与读取路径的描述。

存储引擎中最重要的部分就是磁盘与内存两个结构。而根据数据在它们之中挑选一种作为主要的存储，数据库可以被分为内存型数据库与磁盘型数据库。由此可见存储引擎的一个功能，就是可以被作为数据库类型划分的依据，可见引擎的重要性。

内存型存储是把数据主要存储在内存里，其目的很明显，就是加快数据读写性能。分布式数据库一个重要的门类就是内存型数据库，包括 Redis、NuoDB 和 MySQL Cluster 等。当然其缺点也很明显，那就是内存的成本较高，且容量有限。而分布式的架构能有效地扩充该类数据库的容量，这也是内存数据库主要是分布式数据库的原因。

磁盘存储相对传统，它存储主要数据，而内存主要作为缓冲来使写入批量化。磁盘存储的好处是，存储性价比较高，这主要得益于磁盘甚至是磁带的单位存储价格相比内存非常低廉。但是与内存型数据库相比，磁盘型数据库的性能比较低。不过，随着近年 SSD 磁盘的普及，这种趋势得到了有效的改善。

这两种存储引擎的差别还体现在功能实现的难度上。内存型数据库相对简单，因为写入和释放随机的内存空间是相对比较容易的；而磁盘型数据库需要处理诸如数据引用、文件序列化、碎片整理等复杂的操作，实现难度很高。

数据一般是以表格的形式存储在数据库中的，所以所有数据都有行与列的概念。但这只是一个逻辑概念，我们将要介绍的所谓“行式”和“列式”体现的其实是物理概念。

行式存储会把每行的所有列存储在一起，从而形成数据文件。当需要把整行数据读取出来时，这种数据组织形式是比较合理且高效的。但是如果要读取多行中的某个列，这种模式的代价就很昂贵了，因为一些不需要的数据也会被读取出来。

而列式存储与之相反，不同行的同一列数据会被就近存储在一个数据文件中。同时除了存储数据本身外，还需要存储该数据属于哪行。而行式存储由于列的顺序是固定的，不需要存储额外的信息来关联列与值之间的关系。

列式存储非常适合处理分析聚合类型的任务，如计算数据趋势、平均值，等等。因为这些数据一般需要加载一列的所有行，而不关心的列数据不会被读取，从而获得了更高的性能。

我们会发现 OLTP 数据库倾向于使用行式存储，而 OLAP 数据库更倾向于列式存储，正是这两种存储的物理特性导致了这种倾向性。而 HATP 数据库也是融合了两种存储模式的一种产物。

当然这里我们要区分 HBase 和 BigTable 所说的宽列存储与列存储在本质上是不同的。宽列存储放在其中的数据的列首先被聚合到了列簇上，列簇被放在不同的文件中；而列簇中的数据其实是按行进行组织的。

当然，选择这两种存储模式最重要的因素还是访问模式。如果数据主要是按照行进行读取，比如交易场景、资料管理场景等，那么行式存储应是首选。如果需要经常查询所有数据做聚合，或者进行范围扫描，那么列式存储就很值得一试。

上文介绍了内存与磁盘之间的取舍，从中可看到磁盘其实更为重要的，因为数据库是提供数据持久化存储的服务。故我们开始介绍磁盘上最为重要的两类文件：数据文件和索引文件。

数据文件和索引文件如名字所示，分别保存原始数据与检索数据用的索引数据。但是随着时间的推移，两者的区分也不是那么泾渭分明了。其中以 IOT（索引组织表）模式为代表的数据文件在数据库，特别是分布式数据库中占据越来越重的位置。一种将两者进行融合的趋势已经变得势不可挡。

数据文件最传统的形式为堆组织表（Heap-Organized Table），数据的放置没有一个特别的顺序，一般是按照写入的先后顺序排布。这种数据文件需要一定额外的索引帮助来查找数据。

另外有两种数据表形式自带了一定的索引数据能力，即哈希组织表（Hash-Organized Table）和索引组织表（Index-Organized Table）。前者是将数据通过哈希函数分散到一组数据桶内，桶内的数据一般是按照一定规则进行排序，以提高查询效率；而后者一般采用索引文件的形式来存储数据，以 B+树为例，数据被存储在叶子节点上，这样做的目的是减少检索数据时读取磁盘的次数，同时对范围扫描支持友好。

索引文件的分类模式一般为主键索引与二级索引两类。前者是建立在主键上的，它可能是一个字段或多个字段组成。而其他类型的索引都被称为二级索引。主键索引与数据是一对一关系，而二级索引很有可能是一对多的关系，即多个索引条目指向一条数据。

这里按照索引与数据之间结合的程度，我们又可以把索引分为聚簇索引和非聚簇索引。前者如哈希组织表和索引组织表那样，数据的分布与索引分布是有关联的，它们被“聚”在一起，这样的查询效率很好。而后者最常见的例子就是针对这两种数据文件的二级索引，因为二级索引要索引的列不是主键，故索引与数据是分割的，查询时需要进行多次磁盘读取。但是对于写入，聚簇索引可能需要进行唯一判断，性能会比简单构建的非聚簇索引低效。

最后一点需要说明的是，二级索引需要保存指向最终数据的“引用”。从实现层面上，这个引用可以是数据的实际位置，也可以是数据的主键。前者的好处是查询效率高，而写入需要更新所有索引，故性能相对较低。而后者就恰好相反，查询需要通过主键索引进行映射，效率稍低，但写入性能很稳定，如 MySQL 就是选用后者作为其索引模式。

原因也是显而易见的，由于单机内存容量相比磁盘来说是很小的，故需要构建分布式数据库来满足业务所需要的容量。

你可以去研究一下，很多列式相关的开源项目都与 Hadoop 等平台有关系的。原因是针对 OLAP 的分析数据库，一个非常大的应用场景就是要分析所有数据。

而列式存储可以被认为是这种模式的一种优化，实现该模式的必要条件是要有分布式系统，因为一台机器的处理能力是有瓶颈的。如果希望处理超大规模数据，那么将数据分散到多个节点就成为必要的方式。所以说，列模式是由分析性分布式的优化需求所流行起来的。

至于宽列存储更是分布式数据库场景下才会采用的模式。数据文件的组织形式，分布式数据库几乎不会使用堆组织表。因为该形式过于随意，无法有效地分散数据。不知道学习过数据分片那一讲的时候你有没有注意到，另外两种组织表的名字与两种分片算法是有着天然联系的。哈希组织表数据经过哈希函数散列到不同的桶，这些桶可以被分散到不同节点。而索引组织表一般叶子节点是按一定顺序排列的，这与范围分片又有着某种契合的关系。所以分布式数据库一般都会采用这两种模式作为其存储引擎，甚至一些分布式数据库直接将数据文件当作索引使用。

典型的面向分布式数据库所使用的存储引擎。从其特点可以看到，它高速写入的特性对分布式数据库而言是有非常大吸引力的，同时其KV 结构更是分片所喜欢的一种数据格式，非常适合基于此构建分布式数据库。所以诸如 Apache Cassandra、ClickHouse 和 TiDB 等分布式数据库都选用 LSM 树或类似结构的存储引擎来构建分布式数据库。

LSM 树存储引擎的结构暗含在它的名字内。LS 代表日志结构，说明它是以日志形式来存储数据的，那么日志有什么特点呢？如果你对财务记账有些了解的话，会知道会计在删除一笔记录时，是不会直接拿着橡皮擦去擦掉这个记录的，而是会写一笔与原金额相等的冲抵操作。这就是典型的日志型存储的模式。

日志型存储的特点是对写入非常友好，不像 B 树等结构需要进行随机写，日志存储可以进行顺序性写。因为我们常用的 HDD 磁盘是有旋转机构的，写入延迟主要发生在磁盘旋转与读写臂的移动上。如果数据可以顺序写入，可以大大加快这种磁盘机构的写入速度。

而 M 则暗含这个结构会存在合并操作，形成最终的可读取结构。这样读取操作就不用去查找对于该记录的所有更改了，从而加快了读取速度。同时将多个记录合并为一个最终结果，也节省了存储空间。虽然合并操作有诸多优点，但是它也不是没有代价的，那就是会消耗一定的计算量和存储空间。

LSM 树包含内存驻留单元和磁盘驻留单元。首先数据会写入内存的一个缓冲中，而后再写到磁盘上的不可变文件中。

内存驻留单元一般被称为 MemTable（内存表），是一个可变结构。它被作为一个数据暂存的缓冲使用，同时对外提供读取服务。当其中的数据量到达一个阈值后，数据会被批量写入磁盘中的不可变文件内。

磁盘驻留单元，也就是数据文件，是在内存缓冲刷盘时生成的。且这些数据文件是不可变的，只能提供读取服务。而相对的，内存表同时提供读写两个服务。

关于 LSM 树的结构，一般有双树结构和多树结构两种。前者一般是一个理论说明，目前没有一个实际的存储引擎是使用这种结构的。所以我简单说一下双树概念，它有助于你去理解多树结构。

双树中的两棵树分别指：内存驻留单元和磁盘驻留单元中分别有一棵树，你可以想象它们都是 B 树结构的。刷盘的时候，内存数据与磁盘上部分数据进行合并，而后写到磁盘这棵大树中的某个节点下面。成功后，合并前的内存数据与磁盘数据会被移除。

可以看到双树操作是比较简单明了的，而且可以作为一种 B 树类的索引结构而存在。但实际上几乎没有存储引擎去使用它，主要原因是它的合并操作是同步的，也就是刷盘的时候要同步进行合并。而刷盘本身是个相对频繁的操作，这样会造成写放大，也就是会影响写入效率且会占用非常大的磁盘空间。

多树结构是在双树的基础上提出的，内存数据刷盘时不进行合并操作，而是完全把内存数据写入到单独的文件中。那这个时候另外的问题就出现了：随着刷盘的持续进行，磁盘上的文件会快速增加。这时，读取操作就需要在很多文件中去寻找记录，这样读取数据的效率会直线下降。

为了解决这个问题，此种结构会引入合并操作（Compaction）。该操作是异步执行的，它从这众多文件中选择一部分出来，读取里面的内容而后进行合并，最后写入一个新文件中，而后老文件就被删除掉了。如下图所示，这就是典型的多树结构合并操作。而这种结构也是本讲介绍的主要结构。

数据首先写入当前内存表，当数据量到达阈值后，当前数据表把自身状态转换为刷盘中，并停止接受写入请求。此时会新建另一个内存表来接受写请求。刷盘完成后，由于数据在磁盘上，除了废弃内存表的数据外，还对提交日志进行截取操作。而后将新数据表设置为可以读取状态。

在合并操作开始时，将被合并的表设置为合并中状态，此时它们还可以接受读取操作。完成合并后，原表作废，新表开始启用提供读取服务。

查询操作本身并没有 LSM 树的特色操作。由于目标数据可能在内存表或多个数据表中，故需要对多个数据源的结果数据进行归并操作。其中使用了排序归并操作，原因也非常简单，因为不论是内存表还是数据表，其中的数据都已经完成了排序。排序归并算法广泛应用在多种数据库中，如 Oracle、MySQL，等等。另外数据库中间 Apache ShardingShpere 在处理多数据源 order by 时，也使用了这个方法。

而查询另外一个问题是处理同一份数据不同版本的情况，虽然合并操作可以解决部分问题，但合并前的数据还需要通过查询机制来解决。我刚介绍过 LSM 树中对数据的修改和删除本质上都是增加一条记录，因此数据表和内存表中，一份数据会有多条记录，这个时候查询就需要进行冲突处理。一般一份数据的概念是它们具有相同的 key，而往往不同的版本会有时间戳，根据这个时间戳可以建立写入顺序，这类似于向量时钟的概念。故查询中我们很容易判断哪条数据是最新数据。

更新和删除操作本质上是插入数据，然后根据上面提到的冲突处理机制和合并操作来获取最终数据。更新操作是比较简明的，插入新数据就好了。但是删除操作时插入的是什么呢？

一般插入的是特殊的值，被称作墓碑（Tombstone）。它是一个特殊的值，用来表示记录被删除。如果要产出一个范围内数据呢？Apache Cassandra 的处理方法是引入范围墓碑（Range Tombstone）。

比如有从 k0 到 k9 的 9 条数据，在 k3 处设置开始删除点（包含 k3），在 k7 处设置结束删除点（不包含 k7），那么 k3 到 k6 这四条数据就被删除了。此时查询就会查不到 k4 到 k6，即使它们上面没有设置墓碑。

合并操作是用来维护 LSM 树的结构的，以保证其可以正常运行。需要强调的一点是，我们这里说的合并操作针对的是 LSM 树的结构里面提到的多树结构。在多树结构中，磁盘中表的数量随着刷盘动作的持续进行，而变得越来越多。合并操作正是让它们减少的一种手段。

合并操作会根据一定规则，从磁盘的数据文件中选择若干文件进行合并，而后将新文件写入磁盘，成功后会删除老数据。在整个操作的过程中，对内存的消耗是完全可控的。这是由于每个数据文件都是经过排序的，如上一讲提到的查询规则一样，我们依然可以通过排序归并来合并多个文件中的数据。这种合并每次只会加载部分数据，也就是每个文件头部的数据，进入内存进行合并操作。从而很好地控制了合并操作对内存资源的消耗。

在整个合并的过程中，老的数据表依然可以对外提供读取服务，这说明老数据依然在磁盘中。这就要求磁盘要留有一定的额外空间来容纳生成中的新数据表。同时合并操作可以并行执行，但是一般情况下它们操作的数据不会重合，以免引发竞争问题。合并操作既可以将多个数据文件合并成一个，也可以将一个数据文件拆分成多个。

常见的合并策略有 Size-Tiered Compaction 和 Leveled Compaction。

其中，数据表按照大小进行合并，较小的数据表逐步合并为较大的数据表。第一层保存的是系统内最小的数据表，它们是刚刚从内存表中刷新出来的。合并过程就是将低层较小的数据表合并为高层较大的数据表的过程。Apache Cassandra 使用过这种合并策略。

该策略的优点是比较简单，容易实现。但是它的空间放大性很差，合并时层级越高该问题越严重。比如有两个 5GB 的文件需要合并，那么磁盘至少要保留 10GB 的空间来完成这次操作，可想而知此种容量压力是巨大的，必然会造成系统不稳定。

如名称所示，该策略是将数据表进行分层，按照编号排成 L0 到 Ln 这样的多层结构。L0 层是从内存表刷盘产生的数据表，该层数据表中间的 key 是可以相交的；L1 层及以上的数据，将 Size-Tiered Compaction 中原本的大数据表拆开，成为多个 key 互不相交的小数据表，每层都有一个最大数据量阈值，当到达该值时，就出发合并操作。每层的阈值是按照指数排布的，例如 RocksDB 文档中介绍了一种排布：L1 是 300MB、L2 是 3GB、L3 是 30GB、L4 为 300GB。

上图概要性地展示了从 L1 层开始，每个小数据表的容量都是相同的，且数据量阈值是按 10 倍增长。即 L1 最多可以有 10 个数据表，L2 最多可以有 100 个，以此类推。

随着数据表不断写入，L1 的数据量会超过阈值。这时就会选择 L1 中的至少一个数据表，将其数据合并到 L2 层与其 key 有交集的那些文件中，并从 L1 中删除这些数据。

仍然以上图为例，一个 L1 层数据表的 key 区间大致能够对应到 10 个 L2 层的数据表，所以一次合并会影响 11 个文件。该次合并完成后，L2 的数据量又有可能超过阈值，进而触发 L2 到 L3 的合并，如此往复。

可见，Leveled Compaction 与 Size-Tiered Compaction 相比，每次合并时不必再选取一层内所有的数据，并且每层中数据表的 key 区间都是不相交的，重复 key 减少了，所以很大程度上缓解了空间放大的问题。

当然在实际应用中会组合两种策略，比如经典的 RocksDB 会在 L0 合并到 L1 时，使用 Size-Tiered Compaction；而从 L1 开始，则是采用经典的 Leveled Compaction。这其中原因是 L0 的数据表之间肯定会存在相同的 key。

开始介绍这个假说之前，你要先明确几个“放大”概念。

1. 读放大。它来源于在读取时需要在多个文件中获取数据并解决数据冲突问题，如查询操作中所示的，读取的目标越多，对读取操作的影响越大，而合并操作可以有效缓解读放大问题。
2. 写放大。对于 LSM 树来说，写放大来源于持续的合并操作，特别是 Leveled Compaction，可以造成多层连续进行合并操作，这样会让写放大问题呈几何倍增长。
3. 空间放大。这是我在说合并的时候提到过的概念，是指相同 key 的数据被放置了多份，这是在合并操作中所产生的。尤其是 Size-Tiered Compaction 会有严重的空间放大问题。

那么我们可以同时解决以上三种问题吗？根据 RUM 的假说，答案是不能。

该假说总结了数据库系统优化的三个关键参数：读取开销（Read）、更新开销（Update）和内存开销（Memory），也就是 RUM。对应到上面三种放大，可以理解为 R 对应读放大、U 对应写放大，而 M 对应空间放大（Memory 可以理解为广义的存储，而不仅仅指代内存）。

该假说表明，为了优化上述两项的开销必然带来第三项开销的上涨，可谓鱼与熊掌不可兼得。而 LSM 树是用牺牲读取性能来尽可能换取写入性能和空间利用率。

而有的同学会发现，合并操作会带来空间放大的问题，理论上应该会浪费空间。但是 LSM 树由于其不可变性，可以引入块压缩，来优化空间占用使用，且内存不需要做预留（B 树需要额外预留内存来进行树更新操作），从而使其可以很好地优化空间。

你应该知道，RUM 所描述的内容过于简单，一些重要指标如延迟、维护性等没有涵盖其中，但是它可以作为我们工具箱里面的一个短小精干的扳手，来快速分析和掌握一个存储引擎的特点。

互联网规模数据库存储引擎的演变

异地更新相较于原地更新，具有极佳的写入性能，但同时也牺牲了读取性能。

译自 How Database Storage Engines Have Evolved for Internet Scale，作者 Srinivasan Seshadri。

数据库存储引擎的设计对其性能至关重要。几十年来，SQL 和 NoSQL 数据库已经开发出各种技术来优化数据的存储和检索。

数据库存储引擎已经从早期的关系型系统发展到现代的分布式SQL和NoSQL 数据库。早期的关系型系统依赖于对记录的原地更新，而现代系统——无论是分布式关系数据库还是 NoSQL 数据库——主要使用非原地更新。“记录”一词用于指关系数据库中的元组以及 NoSQL 存储中的键值对。

随着互联网规模的用户事件以及来自传感器的自动化事件（例如，物联网）涌入数据库，现代数据库遇到了极其繁重的写入工作负载，非原地更新因此变得流行。

这两种对比鲜明的方法——原地更新和非原地更新——表明，相对于原地更新，非原地更新可以带来极佳的写入性能，但代价是牺牲读取性能。

让我们从存储引擎的分层架构概述开始。数据库存储引擎通常由三层组成：

1. 块存储: 基础层，通过原始设备、文件系统或云存储提供块级访问。数据库组织这些块以实现可扩展的数据存储。
2. 记录存储: 建立在块存储之上，此层将记录组织成块，从而实现表或命名空间扫描。早期的关系型系统通常原地更新记录，而较新的存储引擎则使用非原地更新。
3. 访问方法: 最顶层包括主索引和辅助索引，从而实现高效的数据检索。访问方法的更新也可以是原地更新或非原地更新，我们很快就会看到。许多当前的系统对记录存储和访问方法都采用相同的方法，即原地更新或非原地更新。因此，我们将一起讨论这两层如何在更新方面进行处理。

让我们更深入地研究每一层。

核心是，块存储层将数据组织成称为块（下图 1 中的 B1 和 B2）的可管理单元。这些块充当基本存储单元，更高层将它们组织起来以满足数据库的要求。图 1 说明了一个基本的块存储系统。记录存储和访问方法建立在块存储之上。记录存储和访问方法有两大类，分别对应于更新是否原地进行。接下来我们将描述这两类下的记录存储和访问方法。

图 1：显示块 B1 和 B2 的块存储。

原地更新记录和访问方法是早期关系数据库的标准方法。下图 2 说明了此类系统中的块是如何组织和管理以提供记录存储 API 的。此类记录存储层的显著特征包括：

• 变长记录: 记录的长度经常变化，并且大小在更新期间可能会改变。为了最大限度地减少更新期间的额外IO操作，记录存储层主动管理块空间以适应块内的更新。
• 一级间接寻址: 块中的每个记录都由一个槽号标识，使记录ID (RID) 成为块ID和槽号的组合。这种间接寻址允许记录在块内自由移动而无需更改其RID。
• 槽图: 槽图跟踪块内每个记录的物理位置。它从块的开头开始增长，而记录从结尾开始增长，在两者之间留下空闲空间。这种设计允许块根据记录的大小容纳可变数量的记录，并支持在可用空间内动态调整记录的大小。
• 记录迁移: 当记录增长到超过其原始块的大小限制时，它将被移动到一个新的块，导致其RID发生变化。

图2：就地更新的记录存储，显示块的内部组织方式。

访问方法构建在记录存储之上，以有效地检索记录。它们包括：

• 主键索引: 这些索引将主键字段映射到其对应的RID。
• 二级索引: 这些索引将其他字段值（可能由多个记录共享）映射到其RID。

如果索引完全在内存中，则使用自平衡树，例如红黑树；如果索引主要在磁盘上（部分可能缓存在内存中），则使用B+树。图3显示了记录存储之上的B+树。主键索引和二级索引的条目格式（字段值和RID）相同。

图3：记录存储之上的B+树。

访问方法和记录存储的组合

在某些系统中，访问方法和记录存储层通过将数据直接嵌入B+树的叶节点中来集成。然后，叶级本质上成为一个记录存储，但现在也按索引键排序。由于这种组合，与未排序的记录存储层相比，范围查询的效率更高。但是，要使用其他键访问记录，我们仍然需要在此组合存储层之上使用访问方法（其他键上的索引）。

大多数现代存储引擎，包括分布式NoSQL和分布式SQL引擎，都使用非就地更新。在这种方法中，所有更新都附加到内存中维护的当前写入块，然后在块填满时一次性刷新到磁盘。请注意，如果此节点发生故障，则在写入到达磁盘之前数据的持久性将通过分布式数据库中的复制来缓解。块是不可变的，记录只打包和写入一次，消除了空间管理开销。如果需要，旧版本的记录将由清理过程进行垃圾回收。这有两个优点：

1. 摊销IO成本: 写入块中的所有记录一起只需要一个IO，而就地更新至少需要每个记录一个IO。
2. 利用顺序IO: 这些技术是在磁性硬盘驱动器 (HDD) 时代发明的，顺序IO在HDD中远优于随机IO。但即使在SSD时代，顺序IO仍然相关。这些系统的追加式特性使其适合顺序IO。

最著名和最常用的非就地更新存储引擎形式使用称为日志结构合并树 (LSM-树)的数据结构。事实上，几乎所有现代数据库存储引擎，如BigTable、Dynamo、Cassandra、LevelDB和RocksDB，都使用LSM树。CockroachDB和YugabyteDB等系统采用RocksDB的变体。

LSM树

现代LSM树实现的基础概念源于关于该概念的原始论文，以及同时开发的分步合并方法。

分级合并算法源于一个真实的、关键的需求：1996年管理AT&T网络的全部呼叫量，并记录从美国各地流入的所有呼叫详单（CDR）。那是一个复杂的电话计费计划时代——基于使用量、基于一天中的时间、基于朋友和家人等等。准确记录每个呼叫详单对于未来的计费至关重要。

然而，大量的呼叫量使当时的机器不堪重负，因此产生了将CDR立即追加到记录存储末尾的想法，然后定期“整理”以优化查找以计算账单。账单计算（读取）是批处理作业，没有实时要求，与写入操作不同。

解决上述问题的核心思想是尽可能多地在内存中累积写入，并在内存填满后将其作为级别0的有序运行写入。当有T个级别0的运行可用时，它们全部合并到级别1的更长的有序运行中。在合并过程中，如果需要，可以消除重复项。

这个将级别i的T个有序运行合并以构建级别i+1的更长运行的过程会持续尽可能多的级别，其灵感来自外部排序合并算法。这个想法与最初的LSM树提案非常相似，并且构成了所有现代基于LSM的实现的基础，包括每个级别T个组件的概念。合并过程非常适合顺序IO，写入记录的成本在多个顺序IO操作中为多个记录分摊。

然而，在最坏的情况下，读取必须检查每个级别的每个有序运行，从而导致无法就地更新的惩罚。然而，通过特定于该有序运行的索引（例如B+树）可以有效地查找有序运行中的键。这些B+树直接指向物理位置（而不是RID），因为位置保持不变。图4显示了一个具有三个级别和每个级别T=3个组件的LSM树示例。

有序运行显示为B+树以优化读取操作。请注意，叶级别表示有序运行，而上层级别是从叶级别自下而上构建的（批量加载B+树的标准方法）。在这方面，LSM树可以被认为是访问方法和面向记录的存储结构的组合。虽然排序通常发生在一个键（或多个键的组合）上，但也可能需要通过其他键进行访问的情况，这需要在LSM树之上建立辅助索引。

图4：磁盘上具有三个级别和每个级别三个组件的LSM树示例。

下表比较了早期关系型系统存储引擎与为现代存储引擎开发的存储引擎的关键特性。假设正在写入一条记录，并且正在读取一个主键值。对于早期关系型系统，我们假设在主键上存在B+树索引（叶级别是否包含实际数据或记录标识符（RID）的细节不会显著影响此讨论）。对于LSM树（最常见的现代存储引擎），假设有序运行（和B+树）基于主键。

存储引擎已经发展到可以处理许多数据库系统在互联网规模发展中遇到的繁重写入工作负载。LSM 树已成为解决这一繁重写入工作负载挑战的流行方法。然而，相对于早期关系系统中使用的基于 B+ 树的存储引擎，LSM 树确实牺牲了实时读取性能。在某些情况下，找到一个融合这两种理念优点的系统可能是明智的：使用就地更新以外的方式进行记录存储，以便能够继续处理繁重的写入工作负载，但对访问方法使用就地更新以最大限度地减少读取开销。

访问我们的网站，了解更多关于Aerospike 数据库的信息。

本文作者及来源:Renderbus瑞云渲染农场https://www.renderbus.com