OceanBase 数据库的存储引擎基于 LSM-Tree 架构，将数据分为静态基线数据（放在 SSTable 中）和动态增量数据（放在 MemTable 中）两部分，其中 SSTable 是只读的，一旦生成就不再被修改，存储于磁盘；MemTable 支持读写，存储于内存。数据库 DML 操作插入、更新、删除等首先写入 MemTable，等到 MemTable 达到一定大小时转储到磁盘成为 SSTable。在进行查询时，需要分别对 SSTable 和 MemTable 进行查询，并将查询结果进行归并，返回给 SQL 层归并后的查询结果。同时在内存实现了 Block Cache 和 Row cache，来避免对基线数据的随机读。

当内存的增量数据达到一定规模的时候，会触发增量数据和基线数据的合并，把增量数据落盘。同时每天晚上的空闲时刻，系统也会自动每日合并。

OceanBase 数据库本质上是一个基线加增量的存储引擎，在保持 LSM-Tree 架构优点的同时也借鉴了部分传统关系数据库存储引擎的优点。

传统数据库把数据分成很多页面，OceanBase 数据库也借鉴了传统数据库的思想，把数据文件按照 2MB 为基本粒度切分为一个个宏块, 每个宏块内部继续拆分出多个变长的微块; 而在合并时数据会基于宏块的粒度进行重用, 没有更新的数据宏块不会被重新打开读取, 这样能够尽可能减少合并期间的写放大, 相较于传统的 LSM-Tree 架构数据库显著降低合并代价。

由于 OceanBase 数据库采用基线加增量的设计，一部分数据在基线，一部分在增量，原理上每次查询都是既要读基线，也要读增量。为此，OceanBase 数据库做了很多的优化，尤其是针对单行的优化。OceanBase 数据库内部除了对数据块进行缓存之外，也会对行进行缓存，行缓存会极大加速对单行的查询性能。对于不存在行的"空查"，我们会构建布隆过滤器，并对布隆过滤器进行缓存。OLTP 业务大部分操作为小查询，通过小查询优化，OceanBase 数据库避免了传统数据库解析整个数据块的开销，达到了接近内存数据库的性能。另外，由于基线是只读数据，而且内部采用连续存储的方式，OceanBase 数据库可以采用比较激进的压缩算法，既能做到高压缩比，又不影响查询性能，大大降低了成本。

结合借鉴经典数据库的部分优点，OceanBase 数据库提供了一个更为通用的 LSM-Tree 架构的关系型数据库存储引擎, 具备以下特性:

• 低成本，利用 LSM-Tree 写入数据不再更新的特点, 通过自研行列混合编码叠加通用压缩算法, OceanBase 数据库的数据存储压缩率能够相较传统数据库提升 10+ 倍。

• 易使用，不同于其他 LSM-Tree 数据库，OceanBase 数据库通过支持活跃事务的落盘保证用户的大事务/长事务的正常运行或回滚，多级合并和转储机制来帮助用户在性能和空间上找到更佳的平衡。

• 高性能，对于常见的点查，OceanBase 数据库提供了多级 cache 加速来保证极低的响应延时，而对于范围扫描，存储引擎能够利用数据编码特征支持查询过滤条件的计算下压，并提供原生的向量化支持。

• 高可靠，除了全链路的数据检验之外，利用原生分布式的优势，OceanBase 数据库还会在全局合并时通过多副本比对以及主表和索引表比对的校验来保证用户数据正确性，同时提供后台线程定期扫描规避静默错误。

存储引擎的功能

从功能模块划分上，OceanBase 数据库存储引擎可以大致分为以下几个部分。

数据存储

• 数据组织

  和其他 LSM-Tree 数据库一样，OceanBase 数据库也将数据分为内存增量数据（MemTable）和存储静态数据（SSTable）两个层次，其中 SSTable 是只读的，一旦生成就不再被修改，存储于磁盘；MemTable 支持读写，存储于内存。数据库 DML 操作插入、更新、删除等首先写入 MemTable，等到 MemTable 达到一定大小时转储到磁盘成为 SSTable。

  另外在 OceanBase 数据库内，SSTable 会继续细分为 Mini SSTable、Minor SSTable、Major SSTable 三类，MemTable 转储后形成的我们称为 Mini SSTable，多个 Mini SSTable 会定期 compact 成为 Minor SSTable，而当 OceanBase 数据库特有的每日合并开始后，每个分区所有的 Mini SSTable 和 Minor SSTable 会整体合并为 Major SSTable。

• 存储结构

  在 OceanBase 数据库中, 每个分区的基本存储单元是一个个的 SSTable，而所有存储的基本粒度是宏块，数据库启动时，会将整个数据文件按照 2MB 定长大小切分为一个个宏块，每个 SSTable 实质就是多个宏块的集合。

  每个宏块内部又会继续切分为多个微块，微块的概念和传统数据库的 page/block 概念比较类似, 但是借助 LSM-Tree 的特性，OceanBase 数据库的微块是做过压缩变长的，微块的压缩前大小可以通过建表的时候指定 block_size来确定。

  而微块根据用户指定存储格式可以分别以 encoding 格式或者 flat 格式存储，encoding 格式的微块, 内部数据会以行列混合模式存储；对于 flat 格式的微块，所有数据行则是平铺存储。

• 压缩编码

  OceanBase 数据库对于微块内的数据会根据用户表指定的模式分别进行编码和压缩。当用户表打开 encoding 时, 每个微块内的数据会按照列维度分别进行列内的编码，编码规则包括字典/游程/常量/差值等，每一列压缩结束后，还会进一步对多列进行列间等值/子串等规则编码。编码不仅能帮助用户对数据进行大幅压缩，同时提炼的列内特征信息还能进一步加速后续的查询速度。

  在编码压缩之后，OceanBase 数据库还支持进一步对微块数据使用用户指定的通用压缩算法进行无损压缩，进一步提升数据压缩率。

转储合并

• 转储

  OceanBase 数据库中的转储即 Minor Compaction 概念可以理解和其他 LSM-Tree 架构数据库的 Compaction 概念类似，主要负责 MemTable 刷盘转成 SSTable 以及多个 SSTable 之间的 Compaction 策略选择以及动作。OceanBase 数据库中采用的是 leveled 结合 size tiered 的 Compaction 策略，大致可以分为三层，其中 L1 和 L2 就是固定的 leveled 层次，L0 层是 size tiered，L0 内部还会继续根据写放大系数以及 SSTable 个数进行内部 Compaction 动作。

• 合并

  合并也就是 Major Compaction，在 OceanBase 数据库中也叫每日合并，概念和其他 LSM-Tree 数据库稍有不同。顾名思义，这个概念诞生之初是希望这个动作放到每天凌晨 2 点左右整个集群做一次整体的 Compaction 动作。合并一般是由每个租户的 RS 根据写入状态或者用户设置发起调度，每个租户的每次合并都会选取一个全局的快照点，租户内所有的分区都会用这个快照点的数据做一次 Major Compaction，这样每次合并租户所有的数据都基于这个统一的快照点生成相应的 SSTable，通过这个机制不仅能帮助用户定期整合增量数据，提升读取性能，同时还提供了一个天然的数据校验点，通过全局的一致位点，OceanBase 数据库能够在内部对多副本以及主表索引表进行多维度的物理数据校验。

查询读写

• 插入

  在 OceanBase 数据库中，所有的数据表都可以看成索引聚簇表，即使是无主键堆表，在内部也会为其维护一个隐藏主键。因此当用户插入数据时，在向 MemTable 中写入新的用户数据前，需要先检查当前数据表中是否已经存在相同数据主键数据，为了加速这个重复主键查询性能，对于每个 SSTable 会由后台线程针对不同宏块判重频率来异步调度构建 Bloomfilter。

• 更新

  作为 LSM-Tree 数据库，OceanBase 数据库中的每次更新同样会插入一行新数据，和 Clog 不同，在 MemTable 中更新写入的数据只包含更新列的新值以及对应的主键列，即更新行并不一定包含表全部列的数据，在不断的后台 Compaction 动作中，这些增量更新会不断的融合在一起加速用户查询

• 删除

  和更新类似，删除操作同样不是直接作用在原数据上，而是使用删除行的主键写入一行数据，通过行头标记来标明删除动作。大量的删除动作对于 LSM-Tree 数据库都是不友好的，这样会导致即使一个数据范围被完全删除后，数据库还是需要迭代这个范围内所有删除标记行，再做完融合后才能确认删除状态。针对这个场景，OceanBase 数据库提供了内在的范围删除标记逻辑来规避这种场景，另外也支持让用户显示指定表模式，这样可以通过特殊的转储合并方式来提前回收这些删除行加速查询。

• 查询

  由于增量更新的策略，查询每一行数据的时候需要根据版本从新到旧遍历所有的 MemTable 以及 SSTable，将每个 Table 中对应主键的数据融合在一起返回。数据访问过程中会根据需要利用 Cache 加速，同时针对大查询场景，SQL 层会下压过滤条件到存储层，利用存数据特征进行底层的快速过滤，并支持向量化场景的批量计算和结果返回。

• 多级缓存

  为提升性能，OceanBase 数据库支持了多级的缓存系统，对于查询提供针对数据微块的 Block Cache，针对每个 SSTable 的 Row Cache，针对查询融合结果的 Fuse Row Cache，针对插入判空检查的 Bloomfilter cache 等，同一个租户下的所有缓存共享内存，当 MemTable 写入速度过快时，可以灵活的从当前各种缓存对象中挤占内存给写入使用。

数据校验

作为金融级关系数据库，OceanBase 数据库一直将数据质量和安全放在第一位，全数据链路每一个涉及持久化的数据部分都会增加数据校验保护，同时利用多副本存储的内在优势，还会增加副本间的数据校验进一步验证整体数据一致。

• 逻辑校验

  在常见部署模式下，OceanBase 数据库的每个用户表都会存在多副本，在租户每日合并时，所有的副本都会基于全局统一的快照版本生成一致的基线数据，利用这个特性，所有副本的数据会在合并完成时比对数据的校验和，保证完全一致。更进一步，基于用户表的索引，还会继续比对索引列的校验和，确保最后返回用户的数据不会因为程序内在问题出错。

• 物理校验

  针对数据存储，OceanBase 数据库从数据存储最小 I/O 粒度微块开始，在每个微块/宏块/SSTable/ 分区上都记录了相应的校验和，每次数据读取时都会进行数据校验；为了防止底层存储硬件问题，在转储合并写入数据宏块时也会在写入后马上重新对数据进行校验；最后每个 Server 后台会有定期的数据巡检线程对整体数据扫描校验，以提前发现磁盘静默错误。

在 OceanBase 数据库中, 对于用户表每个分区管理数据的基本单元就是 SSTable，当 MemTable 的大小达到某个阈值后，OceanBase 数据库会将 MemTable 冻结，然后将其中的数据转存于磁盘上，转储后的结构就称之为 Mini SSTable 或者是 Minor SSTable。当集群发生全局合并时，每个用户表分区所有的 Minor SSTable 会根据合并快照点一起参与做 Major Compaction，最后会生成 Major SSTable。每个 SSTable 的构造方式类似，都是由自身的元数据信息和一系列的数据宏块组成，每个数据宏块内部则可以继续划分为多个微块，根据用户表模式定义的不同，微块可以选择使用平铺模式或者编码格式进行数据行的组织。

• 宏块

  OceanBase 数据库将磁盘切分为大小为 2MB 的定长数据块，称之为宏块（Macro Block），宏块是数据文件写 IO 的基本单位，每个 SSTable 就由若干个宏块构成, 宏块2M固定大小的长度不可更改, 后续转储合并重用宏块以及复制迁移等任务都会以宏块为最基本粒度。

• 微块

  在宏块内部数据被组织为多个大小为 16KB 左右的变长数据块，称之为微块（Micro Block），微块中包含若干数据行（Row），微块是数据文件读 IO 的最小单位。每个数据微块在构建时都会根据用户指定的压缩算法进行压缩，因此宏块上存储的实际是压缩后的数据微块，当数据微块从磁盘读取时，会在后台进行解压并将解压后的数据放入数据块缓存中。每个数据微块的大小在用户创建表时可以指定，默认 16KB，用户可以通过语句指定微块长度，但是不能超过宏块大小，语句如下。

  ALTER TABLE mytest SET block_size = 131072;
  

  一般来说微块长度越大，数据的压缩比会越高，但相应的一次 IO 读的代价也会越大；微块长度越小，数据的压缩比会相应降低，但相应的一次随机 IO 读的代价会更小。另外根据用户表模式的不同，每个微块构建的时候可能以平铺模式（Flat）或编码模式（Encoding）分别进行构建。在目前版本中，只有基线数据可以指定使用编码模式组织微块，对于转储数据全部默认使用平铺模式进行数据组织。

OceanBase 数据库的存储引擎基于 LSM-Tree 架构，数据大体上被分为 MemTable 和 SSTable 两部分，当 MemTable 的大小超过一定阈值时，就需要将 MemTable 中的数据转存到 SSTable 中以释放内存，这一过程称之为 转储。转储会生成新的 SSTable，当转储的次数超过一定阈值时，或者在每天的业务低峰期，系统会将基线 SSTable 与之后转储的增量 SSTable 给合并为一个 SSTable，这一过程称之为 合并。

OceanBase 数据库的存储引擎基于 LSM-Tree 架构，数据大体上被分为 MemTable 和 SSTable 两部分，当 MemTable 的大小超过一定阈值时，就需要将 MemTable 中的数据转存到 SSTable 中以释放内存，我们将这一过程称之为转储。

分层转储

在 OceanBase 数据库 V2.1 版本之前，在同一时刻只会维护一个转储 SSTable，当 MemTable 需要进行转储时，会将 MemTable 中的数据和转储 SSTable 中的数据进行归并，这会带来一个问题，随着转储次数不断增多，转储 SSTable 的大小也越来越大，而一次转储需要操作的数据量也越来越多，导致转储速度越来越慢，进而导致 MemTable 内存爆。从 V2.2 版本开始，OceanBase 数据库引入了分层转储策略。

参考业界的部分实现，结合目前 OceanBase 数据库架构，OceanBase 数据库的分层转储方案可以理解为常见的 tiered-leveled compaction 变种方案，L0 层是 size-tiered Compaction, 内部继续根据不同场景分裂多层，L1 和 L2 层基于宏块粒度来维持 Leveled compaction。

L0 层

L0 层内部称为 Mini SSTable，根据不同转储策略需要的不同参数设置，L0 层 SSTable 可能存在可以为空。对于 L0 层提供 server 级配置参数来设置 L0 层内部分层数和每层最大 SSTable 个数，L0 层内部即分为level-0 到 level-n 层，每层最大容纳 SSTable 个数相同。当 L0 层 level-n 的 SSTable 到达一定数目上限或阈值后开始整体 compaction，合并成一个 SSTable 写入 level-n+1 层。当 L0 层 max level 内 SSTable 个数达到上限后，开始做 L0 层到 L1 层的整体 compaction 释放空间。在存在 L0 层的转储策略下，冻结 MemTable 直接转储在 L0-level0 写入一个新的 Mini SSTable，L0 层每个 level 内多个 SSTable 根据 base_version （这是一个用于标识 SSTable 版本的值）有序，后续本层或跨层合并时需要保持一个原则，参与合并的所有 SSTable 的 version 必须邻接，这样新合并后的 SSTable 之间仍然能维持 version 有序，简化后续读取合并逻辑。

L0 层内部分层会延缓到 L1 的 compaction，更好的降低写放大，但同时会带来读放大，假设共 n 层，每层最多 m 个 SSTable，则最差情况 L0 层会需要持有（n X m + 2）个 SSTable，包括 Minor SSTable 和 Major SSTable。因此实际应用中层数和每层 SSTable 上限都需要控制在合理范围。

L1

L1 层内部称为 Minor SSTable，L1 层的 Minor SSTable 仍然维持 rowkey 有序，每当 L0 层 Mini SSTable 达到 compaction 阈值后，L1 层 Minor SSTable 开始参与和 L0 层的 compaction。为了尽可能提升 L1 Compaction 效率, 降低整体写放大, OceanBase 数据库内部提供写放大系数设置, 当 L0 层 Mini SSTable 总大小和 L1 Minor SSTable 大小比率达到指定阈值后, 才开始调度 L1 Compaction, 否则仍调度 L0 层内部 Compaction。

L2

L2 层是基线 Major SSTable，为保持多副本间基线数据完全一致，日常转储过程中 Major SSTable 仍保持只读，不发生实际 compaction 动作。

与转储相比，合并通常是一个比较重的操作，时间也相对较长，在最佳实践中，一般期望在一天只做一次合并操作，并且控制在业务低峰期进行，因此有时也会把合并称之为每日合并。

合并操作（Major Compaction）是将动静态数据做归并，会比较费时。当转储产生的增量数据积累到一定程度时，通过 Major Freeze 实现大版本的合并。它和转储最大区别在于，合并是租户上所有的分区在一个统一的快照点和全局静态数据进行合并的行为，是一个全局的操作，最终形成一个全局快照。

转储（Minor Compaction）	合并（Major Compaction）
Partition 或者租户级别，只是 MemTable 的物化。	全局级别，产生一个全局快照。
每个 OBServer 节点的每个租户独立决定自己 MemTable 的冻结操作，主备分区不保持一致。	全局分区一起做 MemTable 的冻结操作，要求主备 Partition 保持一致，在合并时会对数据进行一致性校验。
可能包含多个不同版本的数据行。	只包含快照点的版本行。
转储只与相同大版本的 Minor SSTable 合并，产生新的 Minor SSTable，所以只包含增量数据，最终被删除的行需要特殊标记。	合并会把当前大版本的 SSTable 和 MemTable 与前一个大版本的全量静态数据进行合并，产生新的全量数据。

合并虽然比较费时, 但是同时为数据库提供了一个操作窗口，在这个窗口内 OceanBase 数据库可以利用合并特征完成多个计算密集任务, 提升整体资源利用效率。

• 数据压缩

  合并期间 OceanBase 数据库会对数据进行两层压缩，第一层是数据库内部基于语义的编码压缩，第二层是基于用户指定压缩算法的通用压缩，使用 lz4 等压缩算法对编码后的数据再做一次瘦身。压缩不仅仅节省了存储空间，同时也会极大地提升查询性能。目前 OceanBase 数据库支持（snappy、lz4、lzo，zstd）等压缩算法，允许用户在压缩率和解压缩时间上做各自的权衡。MySQL 和 Oracle 在一定程度上也支持对数据的压缩，但和 OceanBase 相比，由于传统数据库定长页的设计，压缩不可避免的会造成存储的空洞，压缩效率会受影响。而更重要的是，对于 OceanBase 数据库这样的 LSM-Tree 架构的存储系统，压缩对数据写入性能是几乎无影响的。

• 数据校验

  通过全局一致快照进行合并能够帮助 OceanBase 数据库很容易的进行多副本的数据一致校验, 合并完成后多个副本可以直接比对基线数据来确保业务数据在不同副本间是一致的。另一方面还能基于这个快照基线数据做主表和索引表的数据校验，保障数据在主表和索引表之间是一致的。

• Schema 变更

  对于加列、减列等 Schema 变更，OceanBase 数据库可以在合并中一起完成数据变更操作，DDL 操作对业务来说更加平滑。

转储触发

转储有两种触发方式：自动触发与手动触发。

当一个租户的 MemTable 内存的使用量达到 memstore_limit_percentage * freeze_trigger_percentage 所限制使用的值时，就会自动触发冻结（转储的前置动作），然后系统内部再调度转储。

您也可以通过以下的运维命令手动触发转储。

说明

memstore_limit_percentage 用于设置租户使用 MemStore 的内存占其总可用内存的百分比。有关该配置项的详细介绍，请参见 memstore_limit_percentage。

示例：

• 集群级别转储

  • 对 sys 租户发起的转储

    obclient> ALTER SYSTEM MINOR FREEZE TENANT = sys;
    

  • 对所有用户租户发起的转储

    obclient> ALTER SYSTEM MINOR FREEZE TENANT = all_user;
    

  • 对所有 META 租户发起的转储

    obclient> ALTER SYSTEM MINOR FREEZE TENANT = all_meta;
    

• 租户级别转储

  obclient> ALTER SYSTEM MINOR FREEZE TENANT= prod_tenant;

合并方式

合并有很多种不同的方式，具体的描述如下。

• 全量合并

  全量合并是 OceanBase 数据库最初的合并算法，和 HBase 与 RocksDB 的 major compaction 过程是类似的。在全量合并过程中，会把当前的静态数据都读取出来，和内存中的动态数据合并后，再写到磁盘上去作为新的静态数据。在这个过程中，会把所有数据都重写一遍。全量合并会极大的耗费磁盘 IO 和空间，除了 DBA 强制指定外，目前 OceanBase 数据库一般不会主动做全量合并。

• 增量合并

  在 OceanBase 数据库的存储引擎中，宏块是 OceanBase 数据库基本的 IO 写入单位，在很多情况下，并不是所有的宏块都会被修改，当一个宏块没有增量修改时，合并可以直接重用这个数据宏块, OceanBase 数据库中将这种合并方式称之为增量合并。增量合并极大地减少了合并的工作量，是OceanBase 数据库目前默认的合并算法。更进一步地，OceanBase 数据库会在宏块内部将数据拆分为更小的微块，很多情况下，也并不是所有的微块都会被修改，可以重用微块而不是重写微块。微块级增量合并进一步减少了合并的时间。

• 渐进合并

  为了支持业务的快速发展，用户不可避免地要做加列、减列、建索引等诸多 DDL 变更。这些 DDL 变更对于数据库来说通常是很昂贵的操作。MySQL 在很长一段时间内都不能支持在线的 DDL 变更（直到 5.6 版本才开始对 Online DDL 有比较好的支持），而即使到今天，对于 DBA 来说，在 MySQL 5.7 中做 Online DDL 仍然是一件比较有风险的操作，因为一个大的 DDL 变更就会导致 MySQL 主备间的 replication lag。

  OceanBase 数据库在设计之初就考虑到了 Online DDL 的需求，目前在 OceanBase 数据库中加列、减列、建索引等 DDL 操作都是不阻塞读写的，也不会影响到多副本间的 paxos 同步。加减列的 DDL 变更是实时生效的，将对存储数据的变更延后到每日合并的时候来做。然而对于某些 DDL 操作如加减列等，是需要将所有数据重写一遍的，如果在一次每日合并过程中完成对所有数据的重写，那么对存储空间和合并时间都会是一个比较大的考验。为了解决这个问题，OceanBase 数据库引入了渐进合并，将 DDL 变更造成的数据重写分散到多次每日合并中去做，假设渐进轮次设置为 60，那么一次合并就只会重写 60 分之一的数据，在 60 轮合并过后，数据就被整体重写了一遍。渐进合并减轻了 DBA 做 DDL 操作的负担，同时也使得 DDL 变更更加平滑。

• 并行合并

  在 OceanBase 数据库 V1.0 中增加了对分区表的支持。对于不同的数据分区，合并是会并行来做的。但是由于数据倾斜，某些分区的数据量可能非常大。尽管增量合并极大减少了合并的数据量，对于一些更新频繁的业务，合并的数据量仍然非常大，为此 OceanBase 数据库引入了分区内并行合并。合并会将数据划分到不同线程中并行做合并，极大地提升了合并速度。

合并触发

合并触发有三种触发方式：自动触发、定时触发与手动触发。

• 当租户的 Minor Freeze 次数超过阈值时，就会自动触发这个租户的合并。

• 也可以通过设置参数来在每天的业务低峰期定时触发合并。

  obclient> ALTER SYSTEM SET major_freeze_duty_time = '02:00' TENANT = t1;
  

• 也通过以下的运维命令手动触发合并。

  • 系统租户发起其他租户的合并

    • 对 sys 租户发起的合并

      obclient> ALTER SYSTEM MAJOR FREEZE TENANT = sys;
      

    • 对所有用户租户发起的合并

      obclient> ALTER SYSTEM MAJOR FREEZE TENANT = all_user;
      

    • 对所有 META 租户发起的合并

      obclient> ALTER SYSTEM MAJOR FREEZE TENANT = all_meta;
      

    • 对租户 t1 和 t2 发起的合并

      obclient> ALTER SYSTEM MAJOR FREEZE TENANT = t1,t2; 
      

  • 用户租户发起本租户的合并

    obclient> ALTER SYSTEM MAJOR FREEZE;

 

B-tree和B+树的区别：

比较项	B树	B+树
指针	所有内部和叶节点都有数据指针	只有叶节点有数据指针
搜索	由于并非所有键都在叶中可用，因此搜索通常需要更多时间。	所有的键都在叶节点，因此搜索更快更准确。
冗余键	树中没有保留键的副本。	保留密钥的副本，并且所有节点都存在于叶子中。
插入	插入需要更多时间，而且有时无法预测。	插入更容易，结果始终相同。
删除	内部节点的删除非常复杂，树必须经历很多变换。	删除任何节点都很容易，因为所有节点都在叶子上找到。
叶节点	叶节点不存储为结构链表。	叶节点存储为结构链表。
使用权	无法顺序访问节点	可以像链表一样顺序访问
高度	对于特定数量的节点高度较大	对于相同数量的节点，高度小于 B 树
应用	用于数据库、搜索引擎的 B 树	B+ 树用于多级索引、数据库索引
节点数	任何中间层 'l' 的节点数是 2 l。	每个中间节点可以有 n/2 到 n 个子节点。

 

B+树的不足，与LSM树诞生背景

传统关系型数据库使用btree或一些变体作为存储结构，能高效进行查找。

但保存在磁盘中时它也有一个明显的缺陷，那就是逻辑上相离很近但物理却可能相隔很远，这就可能造成大量的磁盘随机读写。

随机读写比顺序读写慢很多，为了提升IO性能，我们需要一种能将随机操作变为顺序操作的机制，于是便有了LSM树。

为啥 随机读写比顺序读写慢很多呢？

磁盘读写时涉及到磁盘上数据查找，地址一般由柱面号、盘面号和块号三者构成。

也就是说：

step1：移动臂先根据柱面号移动到指定柱面，

step2： 然后根据 盘面号 确定盘面

step3：最后 块号 确定磁道，最后将指定的磁道段移动到磁头下，便可开始读写。

整个过程主要有三部分时间消耗，查找时间(seek time) +等待时间(latency time)+传输时间(transmission time) 。分别表示定位柱面的耗时、将块号指定 磁道段 移到磁头的耗时、将数据传到内存的耗时。

整个磁盘IO最耗时的地方在查找时间，所以减少查找时间能大幅提升性能。

基于 B+ 树的 传统存储引擎，是为旋转磁盘设计的，写入速度很慢，并且只提供基于块的寻址。

性能比较-机械硬盘

机械硬盘在顺序读写场景下有相当出色的性能表现，但一遇到随机读写性能则直线下降。

顺序读是随机读性能的400倍以上。顺序读能达到84MB/S。

顺序写是随机读性能的100倍以上。顺序写性能能达到79M/S。

原因：是因为机械硬盘采用传统的磁头探针结构，随机读写时需要频繁寻道，也就需要磁头和探针频繁的转动，而机械结构的磁头和探针的位置调整是十分费时的，这就严重影响到硬盘的寻址速度，进而影响到随机写入速度。

性能比较-SSD固态硬盘

顺序读：220.7MB/s。随机读：24.654MB/s。 顺序写：77.2MB/s。随机写：68.910MB/s。

总结：对于固态硬盘，顺序读的速度仍然能达到随机读的10倍左右。但是随机写还是顺序写，差别不大。

HDD机械硬盘和SSD固态 硬盘性价比

1、固态硬盘（SSD），优点：读取速度快、抗震性强、功耗低、运行安静。缺点：价格较高、写入寿命有限、容量较小。

2、机械硬盘（HDD），优点：价格低廉、大容量、写入寿命长。缺点：读取速度慢、抗震性差、功耗高、运行噪音大。

选择适合的硬盘需考虑具体需求，如性能需求选SSD，大容量存储选HDD。

像HBASE这样的 海量存储集群，一般都选择 HDD。

什么是LSM树

LSM树，即日志结构合并树(Log-Structured Merge-Tree)。其实它并不属于一个具体的数据结构，它更多是一种数据结构的设计思想。

大多NoSQL数据库核心思想都是基于LSM来做的，或者说，几乎所有 NoSQL 数据库都使用 LSM Tree 的变体作为其底层存储引擎，因为它允许它们实现快速的写入吞吐量和对主键的快速查找。

LSM-Tree 全名叫Log-Structured Merge Tree，最早建立在日志结构文件之上，现在基于合并和压缩排序文件原理的存储引擎都统称为LSM存储引擎。

这种思想简单且有效：

• 即使数据集远大于内存，LSM-tree也能正常工作

• 由于键值有序，范围查询相比于hash表有很大优势

• 由于写入是顺序的（归并是后台线程在空闲时间做的）,所以可以提供非常高的写入吞吐量

我们已经基本描述了 LSM tree 引擎是如何工作的：

1. 写入操作是先写入内存的（被成为 memtable）。所有的用于加速查询的数据结构（布隆过滤器和稀疏索引）都会被同时更新；

2. 当内存中的 memtable 太大了，将会被刷到磁盘中，注意是有序的；

3. 当查询时我们先回查询布隆过滤器，如果布隆过滤器返回说键不存在，则实际不存在，如果布隆过滤器说存在，进一步遍历 segment 文件；

4. 对于遍历 segment 文件的过程，我们将会先通过稀疏索引找到最小的文件范围，并开始由新到老开始遍历，找到一个key则直接返回。

    LSM存储结构与优化

1. HBase使用LSM(Log-Structured Merge Tree)的存储结构，将磁盘的随机IO转化为顺序IO来提高批量读写的性能，代价就是在点查询上性能有所牺牲。

2. 在HBase中当写入一条数据后，率先会写入WAL，然后写入MemStore中。当Mem-Store满足一定条件后，开始flush数据到磁盘中，随着写入的不断增加，磁盘文件HFile也会越来越多，由于数据位置不确定，所以要遍历所有的HFile，因此在点查询时LSM树读性能时没有B+树好(这也是为什么在点查询上HBase不如Mysql的主要原因)。但是HBase也做了一定的优化，会定期合并若干个HFile，即多个文件合并成1个文件，以此来提高读性能。