InnoDB存储引擎


InnoDB是事务安全的mysql存储引擎,设计上采用了类似于Oracle数据库的架构。InnoDB存储引擎是多线程模型,其后台有多个不同的后台线程,负责处理不同的任务

  • Master Thread:主要负责将缓存池中的数据异步刷新到磁盘,保证数据的一致性,包括脏页的刷新、合并插入缓冲(INSERT BUFFER)、UNDO页的回收。
  • IO Thread:主要负责 Async IO 请求的回调处理,包含 write、read、insert buffer 和 log IO thread。
  • Purge Thread:Purge Thread 负责回收已经使用并分配的 undo 页,减轻 Master Thread 的工作。
  • Page Cleaner Thread:Page Cleaner Thread 作用是将之前版本中脏页的刷新操作都放入到单独的线程中来完成,减轻 Master Thread 的工作及对于用户查询线程的阻塞。

本文内容主要基于Mysql官网对于InnoDB的介绍以及一些个人的整理和总结,下面是MYSQL 官方InnoDB架构图,图中显示了组成InnoDB存储引擎体系结构的内存和磁盘结构

InnoDB架构图

In-Memory Structures

InnoDB的内存结构分为四个部分:Buffer PoolChange BufferAdaptive Hash IndexLog Buffer

Buffer Pool

缓冲池是主内存中的一个区域,InnoDB在访问表和索引数据时将数据缓存。缓冲池允许直接从内存访问经常使用的数据,这加快了响应速度。在专用服务器上,高达80%的物理内存通常分配给缓冲池。为了提高大容量读取操作的效率,缓冲池被划分为容纳多行的页。为了提高缓存管理的效率,缓冲池通过(LRU)算法实现。了解如何利用缓冲池将频繁访问的数据保存在内存中是MySQL调优的一个重要方面

简单类似,Buffer Pool是一个有LRU算法维护的列表,LRU链表被分成两部分,一部分是New Sublist(Young 链表),用来存放经常被读取的页的地址,另外一部分是Old Sublist(Old 链表)

  • 列表前面的部分是最近访问的新page的热数据(也叫Yong链表)
  • 列表尾部的部分是最近访问较少page的冷数据(也叫Old链表)

Buffer Pool List

默认情况下链表的读写操作如下

  1. Old 链表占整个LRU 链表的比例是3/8。该比例由innodb_old_blocks_pct控制,默认值是37(3/8*100)。该值取值范围为5~95,为全局动态变量。
  2. 当新的page页被读取到Buffer Pool里面的时候,和传统的LRU算法插入到LRU链表头部不同,Innodb LRU算法是将新的page页插入到Yong 链表的尾部和Old 链表的头部中间的位置,这个位置叫做Mid Point,如上图所示。
  3. 频繁访问一个Buffer Pool的page页,会促使page页往Young链表的头部移动。如果一个Page在被读到Buffer Pool后很快就被访问,那么该Page会往Young List的头部移动,但是如果一个page页是通过预读的方式读到Buffer Pool,且之后短时间内没有被访问,那么很可能在下次访问之前就被移动到Old List的尾部,而被移除了。
  4. 随着数据库的持续运行,新的page页被不断的插入到LRU链表的Mid Point,Old 链表里的page页会逐渐的被移动Old链表的尾部。同时,当经常被访问的page页移动到LRU链表头部的时候,那些没有被访问的page页会逐渐的被移动到链表的尾部。最终,位于Old 链表尾部的page页将从链表中移除。

毫无疑问,对于读请求,Buffer Pool 能够减少磁盘IO,提升性能。问题来了,那写请求呢? 这时就该Change Buffer登场了 !

Change Buffer

在进行DML操作时,如果Buffer Pool没有其相应的Page数据,并不会立刻将磁盘页加载到缓冲池,而是在Change Buffer记录缓冲变更,等未来数据被读取时,再将数据合并(称为merge操作)恢复到Buffer Pool中。Change Buffer占用Buffer Pool空间,默认占25%,最大允许占50%,可以根据读写业务量来进行调整。我们一步一步来思考Change Buffer到底做了什么?如下例子

  • 情况一:假如要修改页号为4的索引页,而这个页正好缓冲池内。

    此时的操作步骤为两步:

    1. 直接修改Buffer Pool中的页,一次内存操作
    2. 写入redo log,一次磁盘顺序写操作

    这样的效率是最高的。(日志这种顺序写,每秒几万次没问题。这种情况是否会出现一致性问题呢?并不会,a.读取,会命中缓冲池的页,b.缓冲池LRU数据淘汰,会将“脏页”刷回磁盘,c.数据库异常奔溃,能够从redo log中恢复数据

  • 情况二:假如要修改页号为40的索引页,而这个页正好在缓冲池内。

    此时麻烦一点,步骤为三步:

    1. 先把页号为40的索引页,从磁盘加载到Buffer Pool,一次磁盘随机读操作
    2. 修改Buffer Pool中的页,一次内存操作
    3. 写入redo log,一次磁盘顺序写操作

    没有命中缓冲池的时候,至少产生一次磁盘IO,对于写多读少的业务场景,是否还有优化的空间呢?这即是InnoDB考虑的问题,于是写缓冲(change buffer)诞生了

在MySQL5.5之前,叫插入缓冲(insert buffer),只针对insert做了优化;现在对delete和update也有效,叫做写缓冲(change buffer)。它是一种应用在非唯一普通索引页(non-unique secondary index page)不在缓冲池中,对页进行了写操作,并不会立刻将磁盘页加载到缓冲池,而仅仅记录缓冲变更(buffer changes),等未来数据被读取时,再将数据合并(merge)恢复到缓冲池中的技术。写缓冲的目的是降低写操作的磁盘IO,提升数据库性能。Change Buffer的运行时结构图大致如下

change buffer

在引入了change buffer后上述的情况二会发生什么变化呢?加入写缓冲优化后,流程优化为:

  1. 在写缓冲中记录这个操作,一次内存操作
  2. 写入redo log,一次磁盘顺序写操作

其性能与情况一这个索引页在缓冲池中相近,那是否会出现一致性问题呢?也不会。

  1. 数据库异常奔溃,能够从redo log中恢复数据
  2. 写缓冲不只是一个内存结构,它也会被定期刷盘到写缓冲系统表空间
  3. 数据读取时,触发merge流程。下面来说一下merge操作

不妨假设稍后的一个时间,有请求查询索引页40的数据,此时Buffer Pool中没有页号40的数据,此时的流程如下:

  1. 查询请求读40索引页,缓冲池未命中,从磁盘入索引页,这次磁盘IO不可避免
  2. change buffer读取相关信息
  3. 对比得到新数据页,同时把新数据刷新到磁盘(这个过程叫merge)

写缓冲区,仅适用于非唯一普通索引页,为什么?

如果在索引设置唯一性,在进行修改时,InnoDB必须要做唯一性校验,因此必须查询磁盘,做一次IO操作。会直接将记录查询到BufferPool中,然后在缓冲池修改,不会在ChangeBuffer操作。

这又引出另一个问题,哪些情况会触发merge操作?

  • 正如刚刚所说,有其他查询请求,访问到了当前页的数据,就会merge
  • 系统后台定时触发 merge 操作。
  • 系统正常shut down之前,merge一次
  • redo log写满的时,merge到磁盘

Adaptive Hash Index

Adaptive Hash Index(以下简称 AHI)估计是 MySQL 的各大特性中,大家都知道名字但最说不清原理的一个特性。根据InnoDB的官方文档显示,启用自适应哈希索引后,读取和写入速度可以提高2倍;对于辅助索引的连接操作,性能可以提高5倍。我们思考一下 AHI 是为了解决什么问题:

  • 随着 MySQL 单表数据量增大,(尽管 B+ 树算法极好地控制了树的层数)索引 B+ 树的层数会逐渐增多;
  • 随着索引树层数增多,检索某一个数据页需要沿着 B+ 树从上往下逐层定位,时间成本就会上升,因为需要搜索更多的枝节点。
  • 为解决检索成本问题,MySQL 就想到使用某一种缓存结构:根据某个检索条件,直接查询到对应的数据页,跳过逐层定位的步骤。这种缓存结构就是 AHI。

AHI 在实现上就是一个哈希表:从某个检索条件到某个数据页的哈希表,仿佛并不复杂,但其中的关窍在于哈希表不能太大(哈希表维护本身就有成本,哈希表太大则成本会高于收益),又不能太小(太小则缓存命中率太低,没有任何收益)。

Log Buffer

Log Buffer 用于加速redo log写的,redo log是磁盘顺序写所以很快。innodb 通过innodb_flush_log_at_trx_commit变量控制如何将日志缓冲区的内容写入并刷新到磁盘,通过事务提交操作的严格遵从ACID在重新排列和成批执行提交相关I/O操作时可能实现的更高性能之间的平衡。您可以通过更改默认值来获得更好的性能,但是在崩溃时可能会丢失事务。它有几个值可以设置,默认是 1

innodb_flush_log_at_trx_commit 枚举值
Default Value 1
Valid Values 0 1 2
  1. 完全符合ACID要求的需要默认设置为1。每次事务提交时,日志都会写入并刷新到磁盘
  2. 设置为0时,日志每秒写入并刷新到磁盘一次。未刷新日志的事务可能会在崩溃中丢失。
  3. 设置为2时,日志在每个事务提交后写入,并每秒刷新一次到磁盘。未刷新日志的事务可能会在崩溃中丢失。

内存结构总结

  1. Buffer Pool 用于加速读
  2. Change Buffer 用于没有非唯一索引的加速写
  3. Adaptive Hash Index要用于加快查询页
  4. Log Buffer 用于加速redo log写

On-Disk Structures

用于存储表结构和数据。表空间又分为系统表空间、独立表空间、通用表空间、临时表空间、Undo表空间等多种类型;

  1. 系统表空间(The System Tablespace)

    包含InnoDB数据字典,Doublewrite Buffer,Change Buffer,Undo Logs的存储区域。系统表空间也默认包含任何用户在系统表空间创建的表数据和索引数据。系统表空间是一个共享的表空间因为它是被多个表共享的。该空间的数据文件通过参数innodb_data_file_path控制,默认值是ibdata1:12M:autoextend(文件名为ibdata1、12MB、自动扩展)

  2. 独立表空间(File-Per-Table Tablespaces)

    默认开启,独立表空间是一个单表表空间,该表创建于自己的数据文件中,而非创建于系统表空间中。当innodb_file_per_table选项开启时,表将被创建于表空间中。否则,innodb将被创建于系统表空间中。每个表文件表空间由一个.ibd数据文件代表,该文件默认被创建于数据库目录中。表空间的表文件支持动态(dynamic)和压缩(commpressed)行格式。

  3. 通用表空间(General Tablespaces)

    通用表空间为通过create tablespace语法创建的共享表空间。通用表空间可以创建于mysql数据目录外的其他表空间,其可以容纳多张表,且其支持所有的行格式。

    CREATE TABLESPACE ts1 ADD DATAFILE ts1.ibd Engine=InnoDB; //创建表空间ts1 
    CREATE TABLE t1 (c1 INT PRIMARY KEY) TABLESPACE ts1; //将表添加到ts1表空
  4. 临时表空间(Temporary Tablespaces)

    分为session temporary tablespaces 和global temporary tablespace两种。session temporary tablespaces 存储的是用户创建的临时表和磁盘内部的临时表。 global temporary tablespace 存储用户临时表的回滚段(rollback segments )。 mysql服务器正常关闭或异常终止时,临时表空间将被移除,每次启动时会被重新创建。

  5. 撤销表空间(Undo Tablespaces)

    撤销表空间由一个或多个包含Undo日志文件组成。在MySQL 5.7版本之前Undo占用的是System Tablespace共享区,从5.7开始将Undo从System Tablespace分离了出来。InnoDB使用的undo表空间由innodb_undo_tablespaces配置选项控制,默认为0。参数值为0表示使用系统表空间ibdata1;大于0表示使用undo表空间undo_001、undo_002等。

Undo Tablespaces提供修改操作的 原子性,即当修改到一半,出现异常,可以通过Undo 日志回滚。它存储了,事务开始前的原始数据与这次的修改操作。Undo log 存在于回滚段(rollback segment)中,回滚段又存在系统表空间撤销表空间临时表空间

Double Write

Innodb的double write是保证数据库持久性的重要操作,在理解double write之前我们需要了解一些数据存储的知识吗,数据库,OS文件系统和磁盘读写IO的基本单位是块,也可以称之为 (page size) block size。数据库的块最小单位是16K(MySQL默认,oracle是8K),文件系统IO的最小单位是4K(也有1K的),磁盘IO的则更小,linux内核要求IO block size<=OS block size,磁盘IO除了IO block size,还有一个概念是扇区(IO sector),扇区是磁盘物理操作的基本单位,而IO 块是磁盘操作的逻辑单位,一个IO块对应一个或多个扇区,扇区大小一般为512个字节。

各个数据块大小的关系可以梳理如下:

DB block > OS block >= IO block > 磁盘 sector,而且他们之间保持了整数倍的关系。DB page=4OS page=16IO page=32*sector size

任何DB page的写入,最终都会转为sector的写入,如果在写磁盘的过程中,出现异常重启,就可能会发生一个DB页只写了部分sector到磁盘,进而出现页断裂的情况。InnoDB 的Page Size一般是16KB,其数据校验也是针对这16KB来计算的,将数据写入到磁盘是以Page为单位进行操作的。而计算机硬件和操作系统,在极端情况下 (比如断电)往往并不能保证这一操作的原子性,16K的数据,写入4K 时,发生了系统断电/os crash ,只有一部分写是成功的,这种情况下就是 partial page write 问题。为了解决这个问题于是引入了Double Write

在InnoDB将Buffer Pool中的Dirty Page刷(flush)到磁盘上时,首先会将(memcpy函数)Page刷到InnoDB tablespace的一个区域中,我们称该区域为Double write Buffer(大小为2MB,每次写入1MB,128个页)。在向Double write Buffer写入成功后,第二步、再将数据拷贝到数据文件对应的位置。当第二步过程中发生故障,也就是发生partial page write的问题。恢复的时候先检查页内的checksum是否相同,不一致,则直接从doublewrite中恢复

  1. 如果写dw buffer失败,那么这些数据不会写到磁盘,innodb会载入磁盘原始数据和redo日志比较,并重新刷到dw buffer。
  2. 如果写dw buffer成功,但是刷新到磁盘失败,那么innodb就不会通过事务日志来恢复了,而是直接刷新dw buffer中的数据。

脏页刷新

Double Write通常是在刷新脏页时发生宕机保证数据持久性的机制,那什么是刷脏,到这里我们知道InnoDB采用Write Ahead Log策略来防止宕机数据丢失,即事务提交时,先写重做日志,再修改内存数据页,这样就产生了脏页。既然有重做日志保证数据持久性,查询时也可以直接从缓冲池页中取数据,那为什么还要刷新脏页到磁盘呢?如果重做日志可以无限增大,同时缓冲池足够大,能够缓存所有数据,那么是不需要将缓冲池中的脏页刷新到磁盘。但是,通常会有以下几个问题

  • 服务器内存有限,缓冲池不够用,无法缓存全部数据
  • 重做日志无限增大成本要求太高
  • 宕机时如果重做全部日志恢复时间过长

事实上,当数据库宕机时,数据库不需要重做所有的日志,只需要执行上次刷入点之后的日志。这个点就叫做Checkpoint,它解决了以上的问题:

  • 缩短数据库恢复时间
  • 缓冲池不够用时,将脏页刷新到磁盘
  • 重做日志不可用时,刷新脏页

重做日志被设计成可循环使用,当日志文件写满时,重做日志中对应数据已经被刷新到磁盘的那部分不再需要的日志可以被覆盖重用。

InnoDB引擎通过LSN(Log Sequence Number)来标记版本,LSN是日志空间中每条日志的结束点,用字节偏移量来表示。每个page有LSN,redo log也有LSN,Checkpoint也有LSN。可以通过命令show engine innodb status来观察

总结一下,我们执行一句update SQL 会发生什么

  1. 查询到我们要修改的那条数据,我们这里称做 origin,返给执行器。在执行器中,修改数据,称为 modification
  2. 将modification刷入内存,Buffer Pool的 Change Buffer
  3. 引擎层:记录undo log (实现事务原子性)
  4. 引擎层:记录redo log (崩溃恢复使用)
  5. 服务层:记录bin log(记录DDL)
  6. 返回更新成功结果

索引篇

要想彻底弄明白InnoDB中的索引是个什么东西,就必须要了解它的文件存储级别Innodb中将文件存储分为了四个级别
Pages, Extents, Segments, Tablespaces

默认的 extent 大小为 1M 即 64个 16KB的Page。平常我们文件系统所说的页大小是 4KB,包含 8 个 512Byte的扇区。存储结构 B+树

B+树

几种不同的索引组织形式:

  1. 聚簇索引:如上面B+树图所示,子节点上存储行数据,并且索引的排列的顺序和索引键值顺序一致的话就是 聚簇索引。主键索引就是聚簇索引,除了主键索引,其他所以都是辅助索引
  2. 辅助索引:如果我们创建了一个辅助索引,它的叶子节点上只存储自己的值主键索引的值。这就意味着,如果我们通过辅助索引查询所有数据,就会先去查找辅助索引中的主键键值,然后再去主键索引里面,查到相关数据。这个过程称为回表

rowid 如果没有主键索引怎么办呢?没有主键,但是有一个 Unique key 而且都不是 null的,则会根据这个 key来创建聚簇索引。那上面两种都没有呢,别担心,innodb自己维护了一个叫 rowid 的东西,根据这个id来创建 聚簇索引

有时候我们被要求主键为什么要是有序的原因就是,如果我们在一个有序的字段上,建立索引,然后插入数据。 在存储的时候,innodb就会按着顺序一个个存储到 页 上,存满一个页再去申请新的页,然后接着存。但如果我们的字段是无序的,存储的位置就会在不同的页上。当我们的数据存储到一个已经被 存满的页上时,就会造成页分裂,从而形成碎片。

搞清楚什么是索引,结构是什么之后。 我们来看看,什么时候我们要用到索引,理解了这些能更好的帮助我们创建正确高效的索引,离散度低不建索引,也就是数据之间相差不大的就没必要建立索引。(因为建立索引,在查询的时候,innodb大多数据都是相同的,我走索引 和全表没什么差别就会直接全表查询)。比如 性别字段。这样反而浪费了大量的存储空间。

联合字段索引

假设有这样一个联合索引比如 idx(name, class_name),那么在查询时会有两种情况

  1. 当执行 select * from stu where class_name = xx and name = lzw 查询时,也能走 idx 这个索引的,因为优化器将SQL优化为了 name = lzw and class_name = xx
  2. 当需要有 select ··· where name = lzw 的时候,不需要创建一个单独的 name索引,会直接走 idx这个索引
    覆盖索引。如果我们此次查询的所有数据全都包含在索引里面了,就不需要再 回表去查询了。比如:select class_name from stu where name =lzw(如果 where 条件的列和 select 的列都在一个索引中,通过这个索引就可以完成查询,这就叫就叫覆盖索引

索引条件下推

索引条件下推(Index Condition Pushdown)简称ICP,是MySQL 5.6 中引入的一种优化策略。where 条件会被提取成 3 部分: Index KeyIndex FilterTable Filter ,在 MySQL 5.6 之前,并不区分 Index Filter 与 Table Filter,统统将 Index First Key 与 Index Last Key 范围内的索引记录,回表读取完整记录,然后返回给 MySQL Server 层进行过滤,而在 MySQL 5.6 之后,Index Filter 与 Table Filter 分离,Index Filter 下降到引擎层(InnoDB和MyISAM)的索引层面进行过滤,减少了回表与返回 MySQL Server 层的记录交互开销,提高了 SQL 的执行效率。

假设有这样一条SQL,select * from stu where name = lzw and class_name like '%xx',在有索引下推和没有索引下推的执行过程如下

  1. 如果没有索引条件下推,因为后面是 like ‘%xx’的查询条件,所以这里首先根据 name 走 idx联合索引 查询到几条数据后,再回表查询到全量row数据,然后在server层进行 like 过滤找到数据
  2. 如果有索引条件下推,则直接在innodb引擎层对like也进行过滤了,相当于把server层这个过滤操作下推到引擎层了。

建立索引注意事项

  • 在where、order、join的on 使用次数多的时候,加上索引
  • 离散度高的字段才能建立索引
  • 联合索引把离散度高的放前面(因为首先根据第一个字段匹配,能迅速定位数据位置。)
  • 频繁更新的字段不能建索引(造成页分裂,索引按顺序存储,如果存储页满了,再去插入就会造成页分裂)
  • 使用比如replace、sum、count等函数的时候不会使用索引,所以没必要额外建
  • 出现隐式转化的时候,比如字符串转int,也用不到索引
  • 特别长的字段,可以截取前面几位创建索引(可以通过 select count(distinct left(name, 10))/count(*) 来看离散度,决定到底提取前几位)

弄懂了索引,我们就有能力打开 锁篇 的副本了

锁篇

ACID是一系列数据库的设计模型,它强调业务数据的可靠性。MySQL 的InnoDB 存储引擎是使用ACID模型来实现的。

  1. 原子性(Atomicity):主要通过undo.log日志实现。即在事务失败时执行回滚。undo.log日志会记录事务执行的sql,当事务需要回滚时,通过反向补偿回滚数据库状态
  2. 持久性(durability):主要通过redo.log日志实现。首先,mysql持久化通过缓存来提高效率,即在select时先查缓存,再查磁盘;在update时先更新缓冲,再更新磁盘。以减少磁盘io次数,提高效率。但由于缓存断电就没了,所以需要redo.log日志。在执行修改操作时,sql会先写入到redo.log日志,再写入缓存中。这样即使断电,也能保证数据不丢失,达到持久性
  3. 隔离性(isolation):主要通过锁实现。我的理解就是多线程时多事务之间互相产生了影响,要避免这个影响,那就加锁。mysql的锁有表锁,行锁,间隙锁。写写操作通过加锁实现隔离性,写读操作通过MVCC实现
  4. 一致性(consistency):就是事务再执行的前和后数据库的状态都是正常的,表现为没有违反数据完整性,参照完整性和用户自定义完整性等等。而上面三种特性就是为了保证数据库的有一致性

在数据库操作中,为了有效保证并发读取数据的正确性,提出的事务隔离级别。我们的数据库锁,也是为了构建这些隔离级别存在的,事务的隔离级别如下

隔离级别 脏读(Dirty Read) 不可重复读(NonRepeatable Read) 幻读(Phantom Read)
未提交读(Read uncommitted) 可能 可能 可能
已提交读(Read committed) 不可能 可能 可能
可重复读(Repeatable read) 不可能 不可能 可能
可串行化(Serializable ) 不可能 不可能 不可能
  • 未提交读(Read Uncommitted):允许脏读,也就是可能读取到其他会话中未提交事务修改的数据
  • 已提交读(Read Committed):只能读取到已经提交的数据。Oracle等多数数据库默认都是该级别 (不重复读)
  • 可重复读(Repeated Read):可重复读。在同一个事务内的查询都是事务开始时刻一致的,InnoDB默认级别。在SQL标准中,该隔离级别消除了不可重复读,但是还存在幻象读。(在高版本的InnoDB和Falcon存储引擎通过多版本并发控制 [ MVCC,Multiversion Concurrency Control 间隙锁 ] 机制解决了该问题。)
  • 串行读(Serializable):完全串行化的读,每次读都需要获得表级共享锁,读写相互都会阻塞

MVCC

下面来到又一个重要知识点了,它是实现事务隔离性的原理,MVCC (Multiversion Concurrency Control) 中文全程叫多版本并发控制,是现代数据库(包括 MySQLOraclePostgreSQL 等)引擎实现中常用的处理读写冲突的手段,目的在于提高数据库高并发场景下的吞吐性能。如此一来,不同事务并发过程中,SELECT 操作可以不加锁而是通过 MVCC 机制读取指定的版本历史记录,并通过一些手段保证保证读取的记录值符合事务所处的隔离级别,从而解决并发场景下的读写冲突。


Author: 顺坚
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source 顺坚 !
评论
 Previous
React面试题总结 React面试题总结
虽然前端并不是我的强项,但是工作几年了一直做着以后端为主的全栈开发。所以对前端的一些技术框架也比较关注,履历中也有前端开发的经历,因此有时也会被问到一些前端的知识。现如今前端技术发展迅速,JavaScript 工具缓慢而稳定地在市场中扎根,
2021-04-11
Next 
买卖股票的最佳时机 买卖股票的最佳时机
力扣上几道关于股票最佳买卖时机的算法题,在此记录一下解题思路,对比官方的解题发现自己的思路还是太弱了 题号 题解 121. 买卖股票的最佳时机 暴力解法、动态规划 122. 买卖股票的最佳时机 II 暴力搜索、贪心算法、动态
2021-03-28
  TOC