Mysql 5.7 InnoDB 存储引擎整体逻辑架构图

一、Buffer Pool 概述

InnoDB 作为一个存储引擎,为了降低磁盘 IO,提升读写性能,必然有相应的缓冲池机制,这个缓冲池就是 Buffer Pool

为了方便理解,对于磁盘上的数据所在的页,叫做数据页,当数据页加载进 Buffer Pool 之后,叫做缓存页,这两者是一一对应的,只不过数据是在磁盘上,缓存页是在内存中

Buffer Pool 作为 InnoDB 存储引擎内存结构的四大组件之一,它主要由以下特点

1、Buffer Pool 缓存的是
最热的数据页和索引页
,把磁盘上的数据页缓存到内存中,避免每次访问数据都要进行磁盘 IO 操作,提升了数据的读写性能

2、Buffer Pool 以缓存页为基本单位,每个缓存页的默认大小是 16KB,Buffer Pool 底层采用双向链表的数据结构管理缓存页

3、Buffer Pool 是一块连续的内存区域,
它的作用是为了降低磁盘 IO,提升数据的读写性能,所有数据的读写操作都需要通过 Buffer Pool 才能进行

• 读操作: 先判断 Buffer Pool 中是否存在对应的缓存页,如果存在就直接操作 Buffer Pool 中的缓存页,如果不存在,则需要将磁盘上的数据页读入到 Buffer Pool 中,然后操作 Buffer Pool 中对应的缓存页即可
• 写操作: 先把数据和日志等信息分别写入 Buffer Pool 和 Log Buffer,再由后台线程将 Buffer Pool 中的数据刷盘

二、Buffer Pool 控制块

Buffer Pool 中存放的是缓存页,缓存页大小跟磁盘数据页大小一样,都是默认 16KB,为了更好的管理缓存页,InnoDB 为每一个缓存的数据页都创建一个单独的区域,用于记录数据页的元数据信息,这些信息主要包括
数据页
所属表空间编号、数据页编号
、缓存页在 Buffer Pool 中的地址、链表节点信息、索信息、LSN 信息等,这个特殊的区域被称为控制块

控制块和缓存页是一一对应的,它们都被存放在 Buffer Pool 中,控制块的大小大概占缓存页大小的 5% 约为 819 个字节(16 * 1024 * 0.05 = 819.2B)

图示中存在一个碎片空间,这个碎片空间是怎么产生的?

数据页大小为 16KB,控制块大概为 800B,当我们划分好所有的控制块与数据页后,可能会有剩余的空间不够一对控制块和缓存页的大小,这部分就是多余的碎片空间.如果把 Buffer Pool 的大小设置的刚刚好的话,也可能不会产生碎片

三、Buffer Pool 缓存页管理机制

Buffer Pool 底层采用双向链表这种数据结构来管理缓存页,在 InnoDB 访问表记录和索引时会将对应的数据页缓存在 Buffer Pool 中,以后如果需要再次使用时直接操作 Buffer Pool 中的缓存页即可,减少了磁盘 IO 操作,提升读写效率

当启动 Mysql 服务器的时候,需要完成对 Buffer Pool 的初始化,即分配 Buffer Pool 的内存空间,把它划分为若干对控制块 + 缓存页的组合,整个初始化过程大致如下

• 申请空间: Mysql 服务器启动时,会根据设置的 Buffer Pool 大小(innodb_buffer_pool_size),去操作系统申请
  一块连续的内存区域
  作为 Buffer Pool 的内存空间,实际的内存空间大小应该要大于 innodb_buffer_pool_size,主要原因是里面还要存放每个缓存页的控制块,这些控制块占用的内存大小不计算进入 innodb_buffer_pool_size 中
• 划分空间: 当内存区域申请完毕之后,Mysql 就会按照默认的缓存页大小(16KB) 以及对应的控制块大小(约 800B),将整个 Buffer Pool 划分为若干个
  控制块 + 缓存页
  的组合

Buffer Pool 中的缓存页根据状态可以分为三种类型

Free page: 空闲 page,未被使用的 page 页

Clean page: 已经被使用,但是数据没有被修改过,Buffer Pool 和磁盘上的数据是一致的

Dirty page: 脏页,已经被使用,并且数据被修改过,Buffer Pool 和磁盘上的数据不一致

针对上面所说的三种 page 页类型,InnoDB 通过三种链表来维护和管理这些 page 页,这三种链表分别是 Free 链表、Flush 链表、LRU 链表

3.1、Free 链表

在 Buffer Pool 刚被初始化出来的时候,所有的控制块和数据页都是空的,当执行读写操作的时候,磁盘的数据页会被加载到 Buffer Pool 的缓存页中,当 Buffer Pool 中有的数据页持久化到磁盘的时候,这些缓存页又要被空闲出来,如何知道哪些数据页是空的,哪些数据页是有数据的,只有找到空的数据页,才能把数据写进行去,一种方式是遍历所有的数据页,挨个查找,找到符合要求的空数据页,还有
另外一种方式就是通过某种数据结构来进行管理,这种数据结构就是 Free 链表

Free 链表表示
空闲缓冲区
,其作用是管理 Buffer Pool 中所有的 free page,它是一个双向链表,由一个基节点和若干个子节点组成,
记录空闲的数据页对应的控制块信息
,

Free 链表是把所有空闲的缓冲页对应的控制块作为一个个节点放在一个链表中,

基节点: Free 链表中基节点是不记录缓存页信息的,需要单独申请,它里面就存放了 free 链表的头结点的地址、尾节点的地址、以及整个 Free 链表里面当前有多少个节点

磁盘加载数据页到 Free page 的流程

1、从 Free 链表中取出一个空闲的控制块

2、把该空闲控制块的信息填上(缓存页所在的表空间、页号等信息),通过控制块与缓存页一一对应的关系,找到 Buffer Pool 中的缓存页,然后把磁盘中的数据页读入到 Buffer Pool 的缓存页中

3、把该空闲控制块从 free 链表中移除,这样就代表该缓冲页已经被使用了

如何判断要操作的数据所在的数据页是否已经缓存在 Buffer Pool 中呢?

Mysql 中有一个哈希表数据结构,它使用 表空间编号 + 数据页编号作为 key,缓存页对应的控制块作为 value

当使用数据页时,会先在数据页缓存 Hash 表中进行查找,找到了之后取出 value 值对应的控制块,由于控制块和 Bufer Pool 中的缓存页是一一对应的,通过控制块就能定位到缓存页如果在数据页缓存的 Hash 表中查找失败,那么就要从磁盘读入了

需要注意的是 value 是控制块编号,而不是缓存页号

3.2、Flush 链表

InnoDB 为了提高处理效率,在每次修改缓冲页之后,并不是立刻把修改刷新到磁盘上,而是在未来的某个时间点进行刷盘操作,所以需要使用 Flush 链表来存储脏页,凡是被修改过的缓冲页对应的控制块都会作为节点被加入到 Flush 链表中

Flush 链表表示
需要刷新到磁盘的缓冲区
,其作用是为了管理 Dirty page

Flush 链表的结构和 Free 链表结构相似,这里就不再画图赘述了

需要注意的是脏页既存在 Flush 链表中,也存在 LRU 链表中,两种链表互不影响,LRU 链表负责管理缓存页的可用性和释放,而 Flush 链表负责管理脏页的刷盘操作

当我们写入数据的时候,磁盘 IO 的效率是很低下的,所以 Mysql 不会直接进行磁盘刷新操作,而是要经过以下两个步骤

• 更新 Buffer Pool 中的数据页(一次内存更新操作)
• 将更新操作顺序写 Redo log file(一次磁盘顺序写)

这样的效率是很高的,顺序写 Redo log 大概每秒几万次
当脏页对应的控制块被加入到 Flush 链表后,后台线程就可以遍历 Flush 链表,将脏页写入磁盘

3.3、LRU 链表

表示正在使用的缓冲区,其作用是为了管理 Clean page 和 Dirty page

InnoDB 的 Buffer Pool 的大小是有限的,并不能无限缓存数据,对于一些频繁访问的数据我们希望可以一直留在内存中,而一些很少访问的数据希望在某些时机可以淘汰掉,从而保证内存不会因为满了而导致无法再缓存新的数据,要实现这个目的,我们很容易想到 LRU(Least Recently Used)算法
LRU 算法一般是使用链表作为数据结构来实现的,链表头部的数据是最近使用的,而链表末尾的数据是最久没有被使用的,那么当空间不够的时候,就会淘汰最久没被使用的节点,也就是链表末尾的数据,从而腾出内存空间

传统的 LRU 算法实现思路
当访问的数据页在内存中,就直接把该页对应的链表节点移动到 LRU 链表的头部
当访问的页不在内存中,除了要把该页对应的节点放入到 LRU 链表的头部,还要淘汰链表最末尾的页

假设有一个 LRU 链表,初始状态如下图所示

如果访问了 3 号页,由于 3 号页在内存中,需要将 3 号页移动到链表的头部,表示最近被访问了,同时 1,2 号页需要向后移动

假设此时再次访问了一个内存中不存在的 9 号页,需要将 9 号页移动到 LRU 链表的头部,其它节点向后移动,由于整个链表长度是 8,所以要将原来末尾的 8 号页淘汰掉

传统的 LRU 算法并没有被 Mysql 使用,因为传统的 LRU 算法无法避免下面两个问题

• 预读失效导致缓存命中率下降；
• Buffer Pool 污染导致缓存命中率下降

什么是预读机制?
预读是 InnoDB 存储引擎的一种优化机制,当 Mysql 从磁盘加载页时,会提前把它相邻的页一并加载进来

InnoDB 为什么要预读呢?
一般来说,数据的读取会遵循集中读写的原则,也就是说当我们需要使用某一些数据的时候,很大概率也会用到附近的数据(即局部性原理),如果要使用的数据页是连续的,一次读取多个数据页相较于多次读取但是每次只读一个页来说,速度是更快的,因为一次读取连续的多个数据页是顺序 IO,由于磁盘快速旋转,磁头只要在对应的磁道上就能快速获取数据,而多次读取每次只读一个页是随机 IO,磁头要不断的移动,寻找磁道然后才能读取数据,磁头的移动是机械性的,速度很慢

在两种情况下会触发 InnoDB 的预读机制
1、顺序访问了磁盘上一个区的多个数据页,当这个数量超过一个阈值时,InnoDB 就会认为你对下一个区的数据也感兴趣,因此触发预读机制,将下个区的数据页也全部加载进 Buffer Pool,这个阈值由参数 innodb_read_ahead_threshold,默认值为 56,可以通过如下命令查看

show variables like '%innodb_read_ahead_threshold%';

2、Buffer Pool 中已经缓存了同一个区数据页的个数超过 13 时,InnoDB 就会将这个区的其它数据页也读取到 Buffer Pool 中,这个开关由参数 innodb_random_read_ahead 控制,默认是关闭的,可以通过如下命令查看

show variables like 'innodb_random_read_ahead';

什么是预读失效,预读失效会带来什么影响?
如果这些提前加载进来的页,并没有被访问,相当于这个预读的工作是白做的,这就是所谓的预读失效
如果使用传统的 LRU 算法,就会把预读页放到 LRU 链表的头部,当内存空间不足的时候,还需要把链表末尾的页淘汰掉
如果这些预读页一直不被访问,就会出现一个很奇怪的问题,不会被访问的预读页反而占据了整个 LRU 链表的前排位置,而链表末尾的页,可能是真正的热点数据,这样就大大降低了缓存的命中率

如何避免预读失效造成的影响?
我们不能因为害怕预读失效,而将预读机制去掉,在大部分的情况下,空间局部性原理还是成立的
要避免预读失效带来的影响,最好的做法就是让预读页在内存中停留的时间尽可能的短,这样真正被访问的页才能移动到 LRU 链表的头部,从而保证真正被读取的热数据停留在内存中的时间尽可能长

那要怎么做才能达成上面的预期呢?
Mysql InnoDB 存储引擎通过改进传统的 LRU 链表来避免预读失效带来的负面影响,具体的改进方式如下
Mysql 的 InnoDB 存储引擎在一个 LRU 链表上划分出两个区域,young 区域和 old 区域,young 区域在 LRU 链表的前半部分,old 区域在后半部分,这两个区域都有各自的头节点和尾节点
young 区域和 old 区域在 LRU 链表中的占比关系并不是 1:1,比例关系由 innodb_old_blocks_pct 参数进行控制,默认热数据区域占 63%,冷数据区域占 37%

划分好这两个区域之后,预读的页就只需要加入到 old 区域的头部,当数据页真正被访问的时候,才将页插入到 young 区域的头部,如果预读的页一直没有被访问,就会从 old 区域移除,整个过程并不会影响 young 区域中的热点数据

假设有一个 LRU 链表初始长度为 8

现在有个编号为 9 的页被预读了,这个页只会被插入到 old 区域头部,而 old 区域末尾的页 (8号) 会被淘汰掉

如果 9 号页一直不会被访问,它也没有占用到 young 区域的位置,也就不会影响到热数据区域,而且还会比 young 区域的数据更早被淘汰出去

如果 9号页被预读后,立刻被访问了,那么就会将它插入到 young 区域的头部,young 区域末尾的页 (5号) 会被挤到 old 区域,作为 old 区域的头部,这个过程并不会有页被淘汰

从上可知,通过 young 和 old 区域的划分,可以很好的解决预读失效的问题

什么是 Buffer Pool 污染?
虽然 Mysql 通过改进传统的 LRU 链表(划分两个区域),避免了预读失效带来的负面影响,但是如果还是使用只要数据被访问一次就加入到 LRU 链表的头部这种方式的话,那么还存在缓存污染的问题
当我们批量读取数据的时候,由于数据被访问了一次,这些大量的数据就会被加入到 young 区域头部,之前缓存在 young 区域的热点数据就被淘汰了,下次访问热点数据的时候又要重新去磁盘读取,大量的 IO 操作导致数据库的性能下降,这个过程就是 Buffer Pool 污染

Buffer Pool 污染会带来什么问题?
Buffer Pool 污染带来的影响是致命的,当某一个 SQL 语句扫描了大量数据的时候,在 Buffer Pool 空间比较有限的情况下,可能会将 Buffer Pool 中的所有页都替换出去,导致大量的热数据被淘汰了,等这些热数据又再次被访问的时候,由于缓存未命中,又要重新去磁盘加载,这样就会产生大量的磁盘 IO,Mysql 性能就会急剧下降
注意: 缓存污染并不只是查询语句查询除了大量的数据才出现的问题,即使查询出来的结果集很小,也会造成缓存污染

比如,在一个数据量非常大的表,执行了下面这条 SQL 语句

select * from user where name like "%xiaomaomao";

从磁盘读取数据页加入到 LRU 链表的 old 区域头部
从数据页中读取行记录时,也就是页被访问的时候,就要将该页放入到 young 区域的头部
接着拿行记录中的 name 字段和字符串 xiaomaomao 进行模糊匹配,如果符合条件,加入到结果集中
如此往复,直到扫描完表中的所有记录,经过这一番折腾,由于这条 SQL 语句访问的的页非常多,每访问一个页就会将其加入到 young 区域的头部,那么原本 young 区域的热点数据都会被替换掉,导致缓存命中率下降,那些在批量扫描时,而被加入到 young 区域的页,如果在很长的一段时间都不会再被访问的话,那么就污染了 young 区域

如何解决 Buffer Pool 污染?
造成 Buffer Pool 污染的原因是,全表扫描导致加载大量数据页到 old 区域,紧接着这些数据页只被访问一次就从 old 区域移动到了 young 区域,导致原本缓存在 young 区域的热点数据失效
全表扫描有一个特点,就是
相同的数据页在短时间内被频繁访问

select * from t_user where id >= 1　

例如上面这条 SQL,假设 id = 1 这行数据所在的页号是 page 10,该页有 10000 条记录,那么执行这条 SQL 时会在短时间内对 page 10 扫描 10000 次

老年代时间停留窗口机制
全表扫描之所以会替换淘汰原有的 LRU 链表 young 区域数据,主要是因为我们将原本只会访问一次的数据页加载到 young 区,这些数据实际上刚刚从磁盘被加载到 Buffer Pool,然后就被访问,之后就不会用,基于此,我们是不是可以将数据移动到 young 区的门槛提高有点,从而把这种访问一次就不会用的数据过滤掉,把它停留在 old 区域,这样就不会污染 young 区的热点数据了
我们只需要提前设定一个时间阈值,然后记录下两次访问同一个数据页的时间间隔,如果两次的时间间隔大于这个阈值,就证明不是全表扫描(全表扫描的特点是相同的数据页短时间内被频繁访问)

Mysql 先设定一个间隔时间 innodb_old_blocks_time,然后将 old 区域数据页的第一次访问时间在其对应的控制块中记录下来
如果后续的访问时间与第一次访问的时间小于 innodb_old_blocks_time 则不将该缓存页从 old 区域移动到 young 区域
如果后续的访问时间与第一次访问的时间大于 innodb_old_blocks_time 才会将该缓存页移动到 young 区域的头部
这样看,其实这个间隔时间 innodb_old_blocks_time 就是数据页必须在 old 区域停留的时间,有了这个 old 区域停留机制,那些短时间内被多次访问的页,并不会立刻插入新生代头部(完美的避开了全表扫描).而是优先淘汰老年代中短期内仅仅访问了一次的页

这个老年代时间停留参数,可以通过如下命令查看,默认值是 1秒

show variables like '%innodb_old_blocks_time%';

所以在 InnoDB 中,只有同时满足
数据页被访问
与
数据页在 old 区域停留时间超过 1 秒
两个条件,才会被插入到 young 区域头部

实际上,Mysql 在冷热分离的基础上还做了一层更深入的优化
当一个缓存页处于热数据区域的时候,我们去访问这个缓存页,这个时候我们真的有必要把它移动到 young 区域的头部吗?
将链表中的数据移动到头部,实际上就是修改节点的指针指向,这个操作是非常快的,但是为了安全期间,在修改链表指针期间,我们需要对链表加上锁,否则会出现并发问题,在并发量大的时候,因为要加锁,会存在锁竞争,每次移动显然效率就会下降,因此 Mysql 针对这一点又做了一层优化

• 如果一个缓存页处于热数据区域,并且在热数据区域的前 1/4 区域(注意是热数据区域的 1/4,而不是整个 LRU 链表的 1/4),那么访问这个缓存页的时候,就不用把它移动到热数据区域的头部,
• 如果缓存页处于热数据的 3/4 区域,那么访问这个缓存页的时候,会把它移动到热数据区域的头部

四、多实例 Buffer Pool
Buffer Pool 本质是 InnoDB 向操作系统申请的一块连续的内存空间,既然是内存空间,那么在多线程环境下,为了保证数据安全,访问 Buffer Pool 中的数据都需要 加锁 处理,当多线程并发访问量特别高时,单一个 Buffer Pool 可能会影响请求的处理速度,因此当 Buffer Pool 的内存空间很大的时候,可以将单一的 Buffer Pool 拆分成若干个小的 Buffer Pool,每个 Buffer Pool 都称为一个独立的实例,各自去申请内存空间、分配内存空间、管理各种链表,以此保证在多线程并发访问时不会相互影响,从而提高并发能力
通过设置 innodb_buffer_pool_instances 的值来修改 Buffer Pool 实例的个数,默认为 1,最大可以设置为 64

[server]

innodb_buffer_pool_instances = 2

上面配置标识创建两个 Buffer Pool 实例(每个 Buffer Pool 的大小为 innodb_buffer_pool_size / 2)

单个 Buffer Pool 实际占用内存空间 = innodb_buffer_pool_size / innodb_buffer_pool_instances

由于管理 Buffer Pool 需要额外的性能开销,因此 innodb_buffer_pool_instances 的个数并不是越多越好

特别需要注意,在 InnoDB 中,当 innodb_buffer_pool_size 小于 1GB 时,innodb_buffer_pool_instances 无效,即使设置的 innodb_buffer_pool_instances 值不为 1,InnoDB 默认也会把它改为 1,这是需要同时考虑单个 Buffer Pool 大小和多实例管理的性能开销而作出的选择

关于 Buffer Pool 的详细参数可以通过如下命令查看

show variables like '%innodb_buffer_pool%'

innodb_buffer_pool_chunk_size：指定了 InnoDB 缓冲池内存的分配单位大小,默认值为 128MB,表示以 128MB 为单位进行内存分配
innodb_buffer_pool_instances：这个参数指定了 InnoDB 缓冲池被划分为多少个实例,每个实例独立管理一部分缓冲池内存,可以提高并发读取的性能,建议设置为 CPU 核心数
innodb_buffer_pool_size：指定了 InnoDB 缓冲池的大小,即用于缓存数据和索引的内存池大小,默认单位是字节,适当调整此参数可以提高读取性能,过大或过小都可能导致性能下降

Go 包操作之如何拉取私有的Go Module

在前面，我们已经了解了
GO 项目依赖包管理与Go Module常规操作
，Go Module 构建模式已经成为了 Go 语言的依赖管理与构建的标准。

在平时使用Go Module 时候，可能会遇到以下问题：

• 在某 module 尚未发布到类似GitHub 或 Gitee 这样的网站前，如何 import 这个本地的 module？
• 如何拉取私有 module？

一、导入本地 module

1.1 依赖本地尚未发布的 module

如果我们的项目依赖的是本地正在开发、尚未发布到公共站点上的 Go Module，那么我们应该如何做呢？

例如：假设有个hello-module的项目，你的main包中依赖了moduleA,代码如下:

package main

import "gitee.com/tao-xiaoxin/study-basic-go/hello-module/moduleA"

func main() {
	moduleA.ModuleA()
}

并且，这个项目中的moduleA 依赖 moduleB,此时此刻，module A 和 moduleB 还没有发布到
gitee
公共托管站点上，它的源码还在你的开发机器上。也就是说，Go 命令无法在
gitee.com/user/
上找到并拉取 module A 和 module B，这时，使用
go mod tidy
命令，就会收到类似下面这样的报错信息：

$go mod tidy
go: finding module for package gitee.com/user/moduleB
go: finding module for package gitee.com/user/moduleA
go: gitee.com/tao-xiaoxin/study-basic-go imports
        gitee.com/user/moduleA: module gitee.com/user: git ls-remote -q origin in /Users/thinkook/go/pkg/mod/cache/vcs/ff424152e6f6be73e07b96e5d8e06c6cd9f86dc9903058919a7b8737718a8418: exit status 128:
        致命错误：仓库 'https://gitee.com/user/' 未找到
go: gitee.com/tao-xiaoxin/study-basic-go/moduleA imports
        gitee.com/user/moduleB: module gitee.com/user: git ls-remote -q origin in /Users/thinkook/go/pkg/mod/cache/vcs/ff424152e6f6be73e07b96e5d8e06c6cd9f86dc9903058919a7b8737718a8418: exit status 128:
        致命错误：仓库 'https://gitee.com/user/' 未找到

所以，Go提供了两种方式可以导入本地正在开发的 Go Module

1.2 Go Module 开发中本地导入两种方式

1.2.1 使用 replace 指令

介绍：
使用
replace
指令可以替代远程依赖模块的路径，将其指向本地的模块路径，便于本地开发和测试。

基本使用：
下面是一个示例replace指令的使用方式：

replace example.com/module@版本号 => 你的本地Module路径（可以使用相对路径或者绝对路径）

接着，我们继续回到上面的举例中，首先，我们需要在 module a 的 go.mod 中的
require
块中手工加上这一条并且替换为本地路径上的
module A
和
moduleB
:

replace (
	gitee.com/user/moduleA v1.0.0 => ../moduleA
	gitee.com/user/moduleB v1.0.0 => ../moduleB
)

这里的
v1.0.0
版本号是一个“假版本号”，目的是满足
go.mod
中
require
块的语法要求。

或者使用
go mod edit
命令编辑
go.mod
文件:

go mod edit -replace=gitee.com/user/moduleA@v1.0.0=../moduleA -replace=gitee.com/user/moduleB@v1.0.0=../moduleB

这样修改之后，Go 命令就会让
module A
依赖你本地正在开发、尚未发布到代码托管网站的
module B
的源码了，并且
main
函数依赖你本地正在开发、尚未发布到代码托管网站的
module B
的源码了。

虽然虽然这个方案可以解决上述问题，但是在平时开发过程中，
go.mod
文件通常需要上传到代码服务器上，这意味着，另一个开发人员下载了这份代码后，很可能无法成功编译。在这个方法中，
require
指示符将
gitee.com/user/moduleA v1.0.0
替换为一个本地路径下的
module A
的源码版本，但这个
本地路径因开发者环境而异
。为了成功编译
module A
和主程序，该开发人员必须将
replace
后面的本地路径更改为适应自己的环境路径。

于是，每当开发人员 pull 代码后，第一件事就是要修改
go.mod
中的
replace
块。每次上传代码前，可能还要将
replace
路径还原，这是一个很繁琐的事情。于是，Go开发团队在Go 1.18 版本中加入了 Go 工作区（Go workspace，也译作 Go 工作空间）辅助构建机制。

上述举例代码仓库地址:
点我进入

1.2.2 使用工作区模式

介绍：
Go 工作区模式是 Go 语言 1.18 版本引入的新功能，允许开发者将多个本地路径放入同一个工作区中，这样，在这个工作区下各个模块的构建将优先使用工作区下的模块的源码。工作区模式具有以下优势：

• 可以将多个本地模块放入同一个工作区中，方便开发者管理。
• 可以解决“伪造 go.mod”方案带来的那些问题。
• 可以提高模块构建的性能。

常用命令：

Go 工具提供了以下命令来帮助开发者使用工作区模式：

• go work edit
  ：提供了用于修改
  go.work
  的命令行接口，主要是给工具或脚本使用。
• go work init
  ：初始化工作区文件 go.work
• go work use
  ：将模块添加到工作区文件
• go work sync
  ：把
  go.work
  文件里的依赖同步到workspace包含的Module的
  go.mod
  文件中。

基本使用：

1. 首先，我们初始化 Go workspace 使用命令
   go work init
   命令如下：

go work init [moddirs]

moddirs
是Go Module所在的本地目录。如果有多个Go Module，就用空格分开。如果
go work init
后面没有参数，会创建一个空的workspace。

执行
go work init
后会生成一个
go.work
文件，
go.work
里列出了该workspace需要用到的Go Module所在的目录，workspace目录不需要包含你当前正在开发的Go Module代码。

2. 如果要给workspace新增Go Module，可以使用如下命令：

go work use [-r] moddir

如果带有
-r
参数，会递归查找
-r
后面的路径参数下的所有子目录，把所有包含
go.mod
文件的子目录都添加到
go work
文件中。

3. 如果要同步依赖到workspace包含的Module的
   go.mod
   文件中，可以使用如下命令：

   go work sync
   

介绍完之后,我们回到上面的例子中，现在我们进入 gowork下面，然后通过下面命令初始化一个go.work:

go work init .

我们看到
go work init
命令创建了一个
go.work
文件，使用
go env GOWORK
命令查看
go.work
所在位置

$go env GOWORK
~/workspace/GolandProjects/study-basic-go/syntax/gowork/go.work

接着，我们在
module a
的
go.work
中的
use
块中替换为本地路径上的
module A
和
moduleB
:

go 1.21.1

use (
	.
	./moduleA
	./moduleB
)

支持replace指示符
：go.work还支持replace指示符,使用方法和上面一样

上面的代码地址:
点我

二、拉取私有 module 的需求与参考方案

自从 Go 1.11 版本引入 Go Module 构建模式后，通过 Go 命令拉取项目依赖的公共 Go Module，已不再是一个“痛点”。现在，我们只需要在每个开发机上设置环境变量 GOPROXY，配置一个高效且可靠的公共 GOPROXY 服务，就可以轻松地拉取所有公共 Go Module 了。

但随着公司内 Go 使用者和 Go 项目的增多，“重造轮子”的问题就出现了。抽取公共代码放入一个独立的、可被复用的内部私有仓库成为了必然，这样我们就有了拉取私有 Go Module 的需求。

一些公司或组织的所有代码，都放在公共 vcs 托管服务商那里（比如 github.com），私有 Go Module 则直接放在对应的公共 vcs 服务的 private repository（私有仓库）中。如果你的公司也是这样，那么拉取托管在公共 vcs 私有仓库中的私有 Go Module，也很容易，见下图：

也就是说，只要我们在每个开发机上，配置公共 GOPROXY 服务拉取公共 Go Module，同时将私有仓库配置到 GOPRIVATE 环境变量，就可以了。这样，所有私有模块的拉取都将直接连接到代码托管服务器，不会通过 GOPROXY 代理服务，并且不会向 GOSUMDB 服务器发出 Go 包的哈希值校验请求。

当然，这个方案有一个前提，那就是每个开发人员都需要具有访问公共 vcs 服务上的私有 Go Module 仓库的权限，凭证的形式不限，可以是 basic auth 的 user 和 password，也可以是 personal access token（类似 GitHub 那种），只要按照公共 vcs 的身份认证要求提供就可以了。

不过，更多的公司 / 组织，可能会将私有 Go Module 放在公司 / 组织内部的 vcs（代码版本控制）服务器上，就像下面图中所示：

那么这种情况，我们该如何让 Go 命令，自动拉取内部服务器上的私有 Go Module 呢？这里给出两个参考方案。

2.1 方案一：通过直连组织公司内部的私有 Go Module 服务器拉取

在这个方案中，我们看到，公司内部会搭建一个内部 goproxy 服务（也就是上图中的 in-house goproxy）。这样做有两个目的，一是为那些无法直接访问外网的开发机器，以及 ci 机器提供拉取外部 Go Module 的途径，二来，由于 in-house goproxy 的 cache 的存在，这样做还可以加速公共 Go Module 的拉取效率。

另外，对于私有 Go Module，开发机只需要将它配置到 GOPRIVATE 环境变量中就可以了，这样，Go 命令在拉取私有 Go Module 时，就不会再走 GOPROXY，而会采用直接访问 vcs（如上图中的 git.yourcompany.com）的方式拉取私有 Go Module。

这个方案十分适合内部有完备 IT 基础设施的公司。这类型的公司内部的 vcs 服务器都可以通过域名访问（比如 git.yourcompany.com/user/repo），因此，公司内部员工可以像访问公共 vcs 服务那样，访问内部 vcs 服务器上的私有 Go Module。

2.2 方案二：将外部 Go Module 与私有 Go Module 都交给内部统一的 GOPROXY 服务去处理：

在这种方案中，开发者只需要把 GOPROXY 配置为 in-house goproxy，就可以统一拉取外部 Go Module 与私有 Go Module。

但由于 go 命令默认会对所有通过 goproxy 拉取的 Go Module，进行 sum 校验（默认到 sum.golang.org)，而我们的私有 Go Module 在公共 sum 验证 server 中又没有数据记录。因此，开发者需要将私有 Go Module 填到 GONOSUMDB 环境变量中，这样，go 命令就不会对其进行 sum 校验了。

不过这种方案有一处要注意：in-house goproxy 需要拥有对所有 private module 所在 repo 的访问权限，才能保证每个私有 Go Module 都拉取成功。

在平时开发中，更推荐第二个方案。在第二个方案中，我们可以将所有复杂性都交给 in-house goproxy 这个节点，开发人员可以无差别地拉取公共 module 与私有 module，心智负担降到最低。

三、统一 Goproxy 方案的实现思路与步骤

3.1 goproxy 服务搭建

Go module proxy
协议规范发布后，Go 社区出现了很多成熟的 Goproxy 开源实现，比如最初的
Athens
，还有国内的两个优秀的开源实现：
goproxy.cn
和
goproxy.io
等。其中，goproxy.io 在官方站点给出了
企业内部部署的方法
，所以今天我们将基于 goproxy.io 来实现我们的方案。

我们在上图中的 in-house goproxy 节点上执行这几个步骤安装 goproxy：

$mkdir ~/.bin/goproxy
$cd ~/.bin/goproxy
$git clone https://github.com/goproxyio/goproxy.git
$cd goproxy
$make

编译后，我们会在当前的 bin 目录（~/.bin/goproxy/goproxy/bin）下看到名为 goproxy 的可执行文件。

然后，我们建立 goproxy cache 目录：

$mkdir /root/.bin/goproxy/goproxy/bin/cache

再启动 goproxy：

$./goproxy -listen=0.0.0.0:8081 -cacheDir=/root/.bin/goproxy/goproxy/bin/cache -proxy https://goproxy.io
goproxy.io: ProxyHost https://goproxy.io

启动后，goproxy 会在 8081 端口上监听（即便不指定，goproxy 的默认端口也是 8081），指定的上游 goproxy 服务为 goproxy.io。

不过要注意下：goproxy 的这个启动参数并不是最终版本的，这里我仅仅想验证一下 goproxy 是否能按预期工作。我们现在就来实际验证一下。

首先，我们在开发机上配置 GOPROXY 环境变量指向 10.10.20.20:8081：

// .bashrc
export GOPROXY=http://10.10.20.20:8081

生效环境变量后，执行下面命令：

$go get github.com/pkg/errors

结果和我们预期的一致，开发机顺利下载了 github.com/pkg/errors 包。我们可以在 goproxy 侧，看到了相应的日志：

goproxy.io: ------ --- /github.com/pkg/@v/list [proxy]
goproxy.io: ------ --- /github.com/pkg/errors/@v/list [proxy]
goproxy.io: ------ --- /github.com/@v/list [proxy]
goproxy.io: 0.146s 404 /github.com/@v/list
goproxy.io: 0.156s 404 /github.com/pkg/@v/list
goproxy.io: 0.157s 200 /github.com/pkg/errors/@v/list

在 goproxy 的 cache 目录下，我们也看到了下载并缓存的 github.com/pkg/errors 包：

$cd /root/.bin/goproxy/goproxy/bin/cache
$tree
.
└── pkg
    └── mod
        └── cache
            └── download
                └── github.com
                    └── pkg
                        └── errors
                            └── @v
                                └── list

8 directories, 1 file

这就标志着我们的 goproxy 服务搭建成功，并可以正常运作了。

3.2 自定义包导入路径并将其映射到内部的 vcs 仓库

一般公司可能没有为 VCS 服务器分配域名，我们也不能在 Go 私有包的导入路径中放入 IP 地址，因此我们需要给我们的私有 Go Module 自定义一个路径，比如：
mycompany.com/go/module1
。我们统一将私有 Go Module 放在
mycompany.com/go
下面的代码仓库中。

那么，接下来的问题就是，当 goproxy 去拉取
mycompany.com/go/module1
时，应该得到
mycompany.com/go/module1
对应的内部 VCS 上
module1
仓库的地址，这样，goproxy 才能从内部 VCS 代码服务器上下载
module1
对应的代码，具体的过程如下：

那么我们如何实现为私有 module 自定义包导入路径，并将它映射到内部的 vcs 仓库呢？

其实方案不止一种，这里我使用了 Google 云开源的一个名为 govanityurls 的工具，来为私有 module 自定义包导入路径。然后，结合
govanityurls
和 Nginx，我们就可以将私有 Go Module 的导入路径映射为其在 VCS 上的代码仓库的真实地址。具体原理你可以看一下这张图：

首先，goproxy 要想不把收到的拉取私有 Go Module（mycompany.com/go/module1）的请求转发给公共代理，需要在其启动参数上做一些手脚，比如下面这个就是修改后的 goproxy 启动命令：

$./goproxy -listen=0.0.0.0:8081 -cacheDir=/root/.bin/goproxy/goproxy/bin/cache -proxy https://goproxy.io -exclude "mycompany.com/go"

这样，凡是与
-exclude
后面的值匹配的 Go Module 拉取请求，goproxy 都不会将其转发给 goproxy.io，而是直接请求 Go Module 的“源站”。

而上面这张图中要做的，就是将这个“源站”的地址，转换为企业内部 VCS 服务中的一个仓库地址。然后我们假设
mycompany.com
这个域名并不存在（很多小公司没有内部域名解析能力），从图中我们可以看到，我们会在
goproxy
所在节点的
/etc/hosts
中添加这样一条记录：

127.0.0.1 mycompany.com

这样做了后，goproxy 发出的到
mycompany.com
的请求实际上是发向了本机。而上面这图中显示，监听本机
80
端口的正是
nginx
，
nginx
关于
mycompany.com
这一主机的配置如下：

// /etc/nginx/conf.d/gomodule.conf

server {
        listen 80;
        server_name mycompany.com;

        location /go {
                proxy_pass http://127.0.0.1:8080;
                proxy_redirect off;
                proxy_set_header Host $host;
                proxy_set_header X-Real-IP $remote_addr;
                proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;

                proxy_http_version 1.1;
                proxy_set_header Upgrade $http_upgrade;
                proxy_set_header Connection "upgrade";
        }
}

我们看到，对于路径为
mycompany.com/go/xxx
的请求，
nginx
将请求转发给了
127.0.0.1:8080
，而这个服务地址恰恰就是
govanityurls
工具监听的地址。

govanityurls
这个工具，是前 Go 核心开发团队成员
Jaana B. Dogan
开源的一个工具，这个工具可以帮助 Gopher 快速实现自定义 Go 包的
go get
导入路径。

govanityurls 本身，就好比一个“导航”服务器。当 go 命令向自定义包地址发起请求时，实际上是将请求发送给了 govanityurls 服务，之后，govanityurls 会将请求中的包所在仓库的真实地址（从 vanity.yaml 配置文件中读取）返回给 go 命令，后续 go 命令再从真实的仓库地址获取包数据。

注：govanityurls 的安装方法很简单，直接 go install/go get github.com/GoogleCloudPlatform/govanityurls 就可以了。在我们的示例中，vanity.yaml 的配置如下：

host: mycompany.com

paths:
  /go/module1:
      repo: ssh://admin@10.10.30.30/module1
      vcs: git

也就是说，当
govanityurls
收到
nginx
转发的请求后，会将请求与
vanity.yaml
中配置的
module
路径相匹配，如果匹配 OK，就会将该
module
的真实 repo 地址，通过
go
命令期望的应答格式返回。在这里我们看到，
module1
对应的真实 VCS 上的仓库地址为：
ssh://admin@10.10.30.30/module1
。

所以，
goproxy
会收到这个地址，并再次向这个真实地址发起请求，并最终将
module1
缓存到本地
cache
并返回给客户端。

3.3 开发机 (客户端) 的设置

前面示例中，我们已经将开发机的
GOPROXY
环境变量，设置为
goproxy
的服务地址。但我们说过，凡是通过
GOPROXY
拉取的 Go Module，
go
命令都会默认把它的
sum
值放到公共
GOSUM
服务器上去校验。

但我们实质上拉取的是私有 Go Module，
GOSUM
服务器上并没有我们的 Go Module 的
sum
数据。这样就会导致
go build
命令报错，无法继续构建过程。

因此，开发机客户端还需要将
mycompany.com/go
，作为一个值设置到
GONOSUMDB
环境变量中：

export GONOSUMDB=mycompany.com/go

这个环境变量配置一旦生效，就相当于告诉
go
命令，凡是与
mycompany.com/go
匹配的 Go Module，都不需要再做
sum
校验了。

到这里，我们就实现了拉取私有 Go Module 的方案。

3.4 方案的“不足”

3.4.1 第一点：开发者还是需要额外配置 GONOSUMDB 变量

由于 Go 命令默认会对从
GOPROXY
拉取的 Go Module 进行
sum
校验，因此我们需要将私有 Go Module 配置到
GONOSUMDB
环境变量中，这就给开发者带来了一个小小的“负担”。

对于这个问题，我的解决建议是：公司内部可以将私有 Go 项目都放在一个特定域名下，这样就不需要为每个 Go 私有项目单独增加
GONOSUMDB
配置了，只需要配置一次就可以了。

3.4.2 第二点：新增私有 Go Module，vanity.yaml 需要手工同步更新

这是这个方案最不灵活的地方了，由于目前
govanityurls
功能有限，针对每个私有 Go Module，我们可能都需要单独配置它对应的 VCS 仓库地址，以及获取方式（git、svn 或 hg）。

关于这一点，我的建议是：在一个 VCS 仓库中管理多个私有 Go Module。相比于最初 Go 官方建议的
一个 repo 只管理一个 module
，新版本的 Go 在一个 repo 下管理多个 Go Module 方面，已经有了长足的进步，我们已经可以通过 repo 的 tag 来区别同一个 repo 下的不同 Go Module。

不过对于一个公司或组织来说，这点额外工作与得到的收益相比，应该也不算什么！

3.4.3 第三点：无法划分权限

在讲解上面的方案的时候，我们也提到过，
goproxy
所在节点需要具备访问所有私有 Go Module 所在 VCS repo 的权限，但又无法对 Go 开发者端做出有差别授权。这样，只要是
goproxy
能拉取到的私有 Go Module，Go 开发者都能拉取到。

不过对于多数公司而言，内部所有源码原则上都是企业内部公开的，这个问题似乎也不大。如果觉得这是个问题，那么只能使用前面提到的第一个方案，也就是直连私有 Go Module 的源码服务器的方案了。

参考链接：

• 小厂内部私有Go module拉取方案3
• Go 1.18新特性前瞻：Go工作区模式

数据库系列：MySQL慢查询分析和性能优化
数据库系列：MySQL索引优化总结（综合版）
数据库系列：高并发下的数据字段变更

1 背景

我们常常在创建组合索引的时候，会纠结一个问题，组合索引包含多个索引字段，它的顺序应该怎么放，怎样能达到更大的性能利用。
正确的索引字段顺序应该取决于使用该索引的查询的最高效率利用，并且同时需要考虑如何更好地满足排序和分组的需要。下面我们详细来说说。

2 索引检索的原理

以innodb为例子， innodb是MySQL默认的存储引擎，使用范围较广，而 innodb的数据组织结构是B+Tree模式。
B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构。
从上面的B-Tree结构图中可以看到每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度，提高查找效率。

B+Tree相比较于B-Tree的不同点：
1、非叶子节点只存储键值信息。
2、所有叶子节点之间都有一个链指针。
3、数据记录都存放在叶子节点中。
将上面的B-Tree优化，由于B+Tree的非叶子节点只存储键值信息，假设每个磁盘块能存储4个键值及指针信息，则变成B+Tree后其结构如下图所示：

InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为〖10〗^3 ）。也就是说一个深度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3 = 10亿 条记录。

★ 当你查找的数据越大的时候，存储的空间需求就越大，你这棵属树的深度也就越大，越往下搜索，IO次数越多，性能也就越差。
所以说，优质的索引是尽量压缩搜索次数，更快的查到数据结果为最佳。

索引的详细说明可以参考我得这一篇《
MySQL全面瓦解23：MySQL索引实现和使用
》

3 索引区分度的分析

3.1 索引区分度衡量策略

假设我们有一个500w数据容量的部门表 emp，想在
雇员名称
和
部门编号
这两个字段上做索引，哪个字段的索引区分度更高，执行效率更高呢？
下面以两个有序的数组为例子，都包含10条记录，分别代表
雇员名称
和
部门编号
的索引。

[
ali
, brand , candy , david , ela , fin , gagn , halande , ivil , jay , kikol]

和

[dep-a , dep-a , dep-a , dep-a ,
dep-a
, dep-b , dep-b , dep-b , dep-b , dep-b]

如果要检索值为 empname ='brand' 和 depno='dep-b' 的所有记录，哪个效率会高一点？
使用二分法查找执行步骤如下：

• 雇员名称查找
  
  • 使用二分法找到最后一个小于指定值
    brand
    （就是上面数组中标红色的
    ali
    的记录）
  • 沿着这条记录向后扫描，和指定值
    brand
    对比，直到遇到第一个大于指定值即结束，或者直到扫描完所有数据。
• 部门编号查找
  
  • 使用二分法找到最后一个小于指定值
    dep-b
    （就是上面数组中标红色的
    dep-a
    的记录）
  • 沿着这条记录向后扫描，和指定值
    dep-b
    对比，直到遇到第一个大于指定值即结束，或者直到扫描完所有数据。

采用上面的方法找到需要检索的记录，第一个数组中更快的一些。因为第二个数组中含有dep-b的基数更大，需要访问和比较的次数也更多一点。
所以说区分度越高的。
举个例子就明白了，假如一个班级50名学生（25名男生、25名女生），所用性别作为索引字段，你需要扫描25次才能把数据完全扫出。
使用是学生姓名，就不需要计算那么多次。明显的过滤范围不是一个量级。
这种区分是有一种计算公式来衡量的：

selecttivity = count(distinct c_name)/count(*) 

当索引区分度越高，检索速度越快，索引区分度低，则说明重复的数据比较多，检索的时候需要访问更多的记录才能够找到所有目标数据。
当索引区分度小到无限趋近于0的时候，基本等同于全表扫描了，此时检索效率肯定是慢的。
第一个数组没有重复数据，索引区分度为1，第二个区分度为0.2，所以第一个检索效率更高。
我们创建索引的时候，尽量选择区分度高的列作为索引，如果是组合索引，也尽量以区分度更高的排在前面。

3.2 真实数据对比

我们回过头来看看emp 表中的两个字段，empname 和 depno 字段，
empname基本不重复，所以每个empname只有一条数据；而 500W的数据大约分配了10个部门，所以每个的depno下有约50W的数据。

1 mysql> select count(distinct empname)/count(*),count(distinct depno)/count(*) from emp; 
2 +----------------------------------+--------------------------------+
3 | count(distinct empname)/count(*) | count(distinct depno)/count(*) |
4 +----------------------------------+--------------------------------+
5 | 0.1713                           | 0.0000                         |
6 +----------------------------------+--------------------------------+
7 1 row in set

再看看两种不同组合索引查询的效率对比，耗时不是一个级别的

• 按照 empname,depno 组合

mysql> create index idx_emp_empname_depno on emp(empname,depno);
Query OK, 0 rows affected
Records: 0  Duplicates: 0  Warnings: 0

mysql> select * from emp where empname='LsHfFJA' and depno='106';
+---------+---------+---------+---------+-----+---------------------+------+------+-------+
| id      | empno   | empname | job     | mgr | hiredate            | sal  | comn | depno |
+---------+---------+---------+---------+-----+---------------------+------+------+-------+
| 4582071 | 4582071 | LsHfFJA | SALEMAN |   1 | 2021-01-23 16:46:03 | 2000 | 400  |   106 |
+---------+---------+---------+---------+-----+---------------------+------+------+-------+
1 row in set  (0.021 sec)

• 按照 depno,empname 组合

mysql> create index idx_emp_depno_empname on emp(depno,empname);
Query OK, 0 rows affected
Records: 0  Duplicates: 0  Warnings: 0

mysql> select * from emp where depno='106' and empname='LsHfFJA';
+---------+---------+---------+---------+-----+---------------------+------+------+-------+
| id      | empno   | empname | job     | mgr | hiredate            | sal  | comn | depno |
+---------+---------+---------+---------+-----+---------------------+------+------+-------+
| 4582071 | 4582071 | LsHfFJA | SALEMAN |   1 | 2021-01-23 16:46:03 | 2000 | 400  |   106 |
+---------+---------+---------+---------+-----+---------------------+------+------+-------+
1 row in set  (0.393 sec)

4 总结

匹配度分析和基数容量的计算法则是非常值得借鉴的，但在真实的环境下，查询的复杂度要高的多，WHERE子句中的排序、分组和范围条件等其他因素，都可能对查询的性能造成非常大的影响。后面我们结合实际的排序、分组、范围条件变化的情况来做更深入的分析。

一、背包问题

1.1 问题描述

设有编号为1、2、......、n的n个物品，它们的重量分别为w1、w2、......、wn，价值分别为v1、v2、......、vn，其中wi和vi均为正数，有一个背包可以懈怠的最大重量不超过W。求解目标是在不超过背包附中的前提下使背包装入的总价值最大（即效益最大化）。与0/1背包问题的区别是，这里的每个物品可以
取一部分
装入背包。

1.2 求解思路

采用贪心法求解。用结构体存储物品的价值、重量和价重比，在输入价值重量后，首先求每个物品的
价重比
p=v/w，将所有物品按照价重比进行排序，从价重比最大的物品开始遍历，若当前物品的重量小于背包剩余容量wieght，将这个物品全部放入背包中，直到其中一个物品的重量w大于背包剩余容量或者物品放完，若其中一个物品的重量w大于背包剩余容量，就将其一部分装入背包，剩余若还有物品没装，便置为0。

1.3 详细代码

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXV 51

struct NodeType{
	double v;//价值
	double w;//重量
	double p;//价重比 
}; 

int n;		 //物品件数 
double W;//背包限重 
NodeType a[MAXV]={{0}};//所有物品

double sumv=0;		 //当前背包中物品价值
double x[MAXV]={0};//标记每件物品装了多少进背包 

void KNap(){
	double weight=W;//背包剩余重量
	int i;
	for(i=0;i<n;i++){
		if(a[i].w<weight){//从价重比最大的开始，若能直接装入，就直接装入 
			x[i]=1;
			weight-=a[i].w;
			sumv+=a[i].v;
		}
		else if(a[i].w>weight){//直到其中一个不能完全装入，退出循环 
			break;
		}
	} 
	if(weight>0){//还能继续装入 
		x[i]=weight/a[i].w;			//这件物品装入一部分 
		sumv+=x[i]*a[i].v;
	}
}

bool cmp(NodeType p1,NodeType p2){//排序 
	return p1.p>p2.p;
}

void Disp(){				//输出 
	cout<<"W\t"<<"V\t"<<"V/W"<<endl; 
	for(int i=0;i<n;i++){
		cout<<a[i].v<<"\t"<<a[i].w<<"\t"<<a[i].p<<endl;
	}
}
void Init(){
	cout<<"请输入物品件数："<<endl;
	cin>>n;
	cout<<"请输入背包限重："<<endl;
	cin>>W;
	cout<<"请输入物品重量和价值："<<endl;
	double v,w;
	for(int i=0;i<n;i++){
		cout<<"第"<<i+1<<"件物品：";
		cin>>w>>v;
		a[i].v=v;
		a[i].w=w;
		a[i].p=v/w;
	}
	cout<<"排序前："<<endl;
	Disp(); 
	sort(a,a+n,cmp);		//排序 
	cout<<"排序后："<<endl;
	Disp();
	KNap();
	cout<<"求解结果："<<endl;
	cout<<"x：[ ";
	for(int i=0;i<n;i++){
		if(i==n-1) cout<<x[i];
		else cout<<x[i]<<" , ";
	}
	cout<<"]"<<endl;
	cout<<"总价值："<<sumv<<endl;
}

int main(){
	Init();
	return 0;
}

1.4 复杂度分析

排序算法时间复杂度O(nlogn)，while循环时间复杂度为O(n)，所以本算法的时间复杂度为O(nlogn)。

二、最优装载问题

2.1 问题描述

有n个集装箱要装上一艘载重量为W的轮船，其中集装箱i（1<=i<=n）的重量为wi。不考虑集装箱的体积限制，现要尽可能多的集装箱装上轮船，使他们的重量之和不超过W。

2.2 求解思路

题说
要尽可能多的集装箱装上轮船
，这里采用贪心法求解，选出尽可能多的集装箱个数。因此，当重量限制为W时，wi越小可装载的集装箱个数越多，所以采用优先选取重量轻的集装箱装船。对于已有的集装箱重量数组w[n]，通过sort排序对重量按照从小到大的顺序进行排序，并设置一个
标记数组x[n]
，标记集装箱是否被装入，0表示未被装入，1表示已被装入，船
剩余载重量weight
，
船当前载重maxw
。遍历数组w，当w[i]<weight时，将其装入，设x[i]=1，weight-=w[i]，maxw+=w[i]。直到集装箱被完全装入或剩余集装箱装不进时，退出循环，求解完毕。maxw即为最后轮船上的总重量。

2.3 详细代码

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXV 51

int w[]={0,5,2,4,3};//每个集装箱的重量
int n=5,W=10;		// 5个集装箱，船载重为W
int maxw=0;			//存放最优解重量
int x[MAXV]={0};	//标记物品是否被存放 

bool cmp(int a,int b){
	return a<b;
}

void solve(){
	int resw=W;
	sort(w+1,w+n+1,cmp);//对重量进行排序
	for(int i=1;i<=n&&w[i]<=resw;i++){
		maxw+=w[i];
		x[i]=1;
		resw-=w[i];
	}
}

int main(){
	solve();
	cout<<"最优方案为："<<endl; 
	for(int i=1;i<=n;i++){
		if(x[i]==1) cout<<w[i]<<" ";
	}
	cout<<endl;
	cout<<"最优解重量为："<<maxw<<endl;
	return 0;
}

2.4 时间复杂度分析

快速排序时间复杂度为O(nlogn)，遍历重量时间复杂度为O(n)，故本算法时间复杂度为O(nlogn)。

三、田忌赛马问题

3.1 问题描述

两千多年前的战国时期，齐威王与大将田忌赛马。双方约定每人各出300匹马，并且在上、中、下三个等级中各选一匹进行比赛，由于齐威王每个等级的马都比田忌的马略强，比赛的结果可想而知。现在双方各n匹马，依次派出一匹马进行比赛，每一轮获胜的一方将从输的一方得到200银币，平局则不用出钱，田忌已知所有马的速度值并可以安排出场顺序，问他
如何安排比赛获得的银币最多
。输入描述：输入包含多个测试用例，每个测试用例的第一行正整数n（n≤1000）马的数量，后两行分别是n个整数，表示田忌和齐威王的马的速度值。输入n=0结束。输出描述：每个测试用例输出一行，表示田忌获得的最多银币数。

3.2 求解思路

采用贪心算法。令田忌马的速度数组为t[n]，左右两侧分别为leftt、rightt，齐威王马的速度数组为q[n]，左右两侧分别为leftq,rightq。田忌获得的银币即为monry。田忌赛马问题可以分为以下几种情况：
（1）田忌最快的马比齐威王最快的马快。此时最优解就是两者比赛，田忌赢。此时rightt--，rightq--，money+=200；
（2）田忌最快的马比齐威王最快的马慢。此时最优解是用田忌最慢的马与齐威王最快的马比赛，田忌输。此时leftt++，rightq--，money-=200；
（3）田忌最快的马和齐威王最快的马一样快。此时又分为以下三种情况：
1、田忌最慢的马比齐威王最慢的马快。此时最优解就是两者比赛，田忌赢。此时leftt++，leftq++，money+=200；
2、田忌最慢的马比齐威王最慢的马慢。此时最优解就是用田忌最慢的马与齐威王最快的马比赛，田忌输。此时leftt++，rightq--，money-=200；
3、其他情况。平局。

3.3 详细代码

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXV 1001

int n;			//马总数
int t[MAXV];	//田忌 
int q[MAXV];	//齐威王
int money=0;	//田忌获得的银币总数 

void solve(){
	sort(t,t+n);//将马的速度按从小到大排序 
	sort(q,q+n);
	int leftt=0;
	int leftq=0;
	int rightt=n-1;
	int rightq=n-1;
	while(leftt<=rightt){
		if(t[rightt]>q[rightq]){//田忌最快的马齐威王最快的马快，田忌赢 
			money+=200;
			rightt--;
			rightq--;
		}
		else if(t[rightt]<q[rightq]){//田忌最快的马比齐威王最快的马慢 
			money-=200;
			leftt++;			//最优解为田忌用最慢的马与齐威王比，田忌输 
			rightq--;
		}
		else {					////田忌最快的马与齐威王最快的马速度相同 
			if(t[leftt]>q[leftq]){//田忌最慢的马比齐威王最慢的马快，田忌赢 
				money+=200;
				leftt++;
				leftq++;
			}
			else if(t[leftt]<q[leftq]){//田忌最慢的马比齐威王最慢的马慢 
				money-=200;
				leftt++;		//最优解为田忌最慢的马与齐威王最快的马比，田忌输 
				rightq--;
			}
		}
	}
}

int main(){
	while(true){
		cout<<"请输入马的总数：";
		cin>>n;
		if(n==0) return 0;
		cout<<"请输入田忌各匹马的速度："<<endl;
		for(int i=0;i<n;i++){
			cin>>t[i];
		}
		cout<<"请输入齐威王各匹马的速度："<<endl;
		for(int i=0;i<n;i++){
			cin>>q[i];
		}
		solve();
		cout<<"田忌能获得的银币最多为："<<money;
	}
	return 0;
} 

3.4 时间复杂度分析

算法主要花费在快速排序，因此时间复杂度为O(nlogn)。

四、多机调度问题

4.1 问题描述

设有n个独立的作业{1,2,......,n}，由m台相同的及其{1,2,......,m}进行加工处理，作业i所需的处理时间为ti（1<=i<=n），每个作业均可在任何一台及其上加工处理，但未完工前不允许中断，任何作业也不能拆分成更小的子作业。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

4.2 问题求解

采用贪心法求解。题说要求在尽可能短的时间内完成，因此分为两种情况，当n<=m时，机器比作业多，可以为每个作业分配一台机器。当n>m时，作业比机器多，此时考虑长作业优先（因为短作业优先时，最开始每个机器上都是短作业，最后分配长作业会发现非常耗时），使用结构体NodeType存储每个作业，包括no（作业编号）、t（时间）、mmo（分配的机器编号）。首先对结构体数组A[n]按照时间从大到小进行排序，先把每个机器上分配一个作业，使用小根堆qu（小根堆会自动排序）来存放结构体，分配下一轮作业时，按照上一轮作业完成时间越小越先出队即e=qu.top()，qu.pop()。出队后将机器分配给下一个作业，并加上时间A[i].t，在将其添加到小根堆中，直到作业分配完毕。

4.3 详细代码

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

int n=7;	//n个作业
int m=3;	//m个机器 
struct NodeType{
	int no;//作业序号
	int t;//作业时长
	int mmo;//机器序号
	bool operator < (const NodeType& s) const{//按t从大到小排序 
		return t>s.t;
	} 
};
NodeType A[]={{1,2},{2,14},{3,4},{4,16},{5,6},{6,5},{7,3}}; 

void solve(){
	NodeType e;
	if(n<=m){
		cout<<"为每一个作业分配一台机器"<<endl;
		return ;
	}
	sort(A,A+n);
	priority_queue<NodeType,vector<NodeType>,less<NodeType> > qu;//小根堆，小的元素在上面（自动排序） 
	for(int i=0;i<m;i++){
		A[i].mmo=i+1;
		cout<<"给机器"<<i+1<<"分配作业"<<A[i].no<<"，执行时间为"<<A[i].t<<"，占用时间段[0,"<<A[i].t<<"]"<<endl;
		qu.push(A[i]);
	}
	for(int i=m;i<n;i++){
		e=qu.top();
		qu.pop();
		cout<<"给机器"<<e.mmo<<"分配作业"<<A[i].no<<"，执行时间为"<<A[i].t<<"，占用时间段["<<e.t<<","<<e.t+A[i].t<<"]"<<endl;
		e.t+=A[i].t; 
		qu.push(e);
	}
}

int main(){
	cout<<"多机调度问题："<<endl;
	solve();
	return 0;
}

4.4 时间复杂度分析

算法快速排序时间复杂度O(nlogn)，两次for循环时间复杂度共O(n)，因此本算法时间复杂度为O(nlogn)。

4.5 小根堆（之前对小根堆了解不多下面记录一下堆）

1、大根堆：是完全二叉树，其中根结点大于子节点；小根堆：是完全二叉树，其中根结点小于子节点。
2、c++中，小根堆和大根堆可以使用优先队列实现（priority_queue），优先级高的先出队，自动排序。

#include<queue>
priority_queue<int> qu;//默认是大根堆
priority_queue<int,vector<int>,greater<int> > qu;//小根堆
priority_queue<int,vector<int>,less<int> > qu;//大根堆

在使用结构体时

#include<queue>
struct Node{
  int x,y;
  bool operator < (const Node& a)const{//小的先进堆
    return x<a.x;
  }
};
priority_queue<Node,vector<Node>,less<Node> > qu;//按照重载后的小于规则，从大到小排序，大的优先级高