上一节我们了解到了矩阵
通常情况下，一个向量既含有在C(A)中的分量p，也含有垂直于C(A)的分量e，投影后e消失，只剩下p。
将b投影到A的左零空间的投影矩阵就是I-P：
这里还是以一个最小二乘法的问题为例，解决点(1,1), (2,2),
(3,2)的最佳拟合问题。我们想要找到这样的一条直线
最佳意味着这些点到拟合直线上的距离之和最小，即最小化
但因为方程组无解，必然不存在这样的直线使得
最小二乘有两种理解方式：
上一章已经利用公式求解得C=2/3, D=1/2。
当然也可以利用微积分的方法去求解：
分别对C和D求导并令求导函数等于0，即可得到答案。
如果A的列都是独立的，那么
因为A的列都是独立的，因此只有x=0才有
这一章主要讲述子空间的投影情况，以一个二维的图为例（这里不画图了）。如果我们有一个向量b和一个向量a（2x1的向量）。假设b在a上的投影为p，这个p就位于与一条经过b并且与向量a正交的位置上，如果我们将
p 视为 b 的近似值，则
e = b − p的长度就是该近似值的误差。
由于p位于通过a的直线上，因此有
p = xa，这里x是一个常数；并且由于a垂直于e，就有
这里x的等式中，分子和分母都是标量，并且
由此可见，p跟b有着相关的关系，b的变化会影响p，而a则不会影响p。
此时可以将p进一步改写，写成这样一个形式
这说明向量b的在a上的投影p是一个矩阵作用在b上得到的，这个矩阵就是投影矩阵，这里分子就是一个2x2的矩阵。并由此得出两个性质：
后者的的几何意义是，对一个向量投影两次和投影一次相同。
向量投影的意义需要从方程Ax=b讲起，以Ax=b为例，这个方程并不是任何时候都有解，向量Ax总是在A的列空间中，而b则很可能不在该列空间中。因此可以将b投影到 A 的列空间中的向量p上并求解Ax= p。
以
假设向量
从高维空间来看，这里的a就是矩阵，而x则是向量，投影
误差向量e就属于
通过矩阵等式可以进一步化简：
因为A不一定是方阵，因此不能进一步化简，但可以看到的是，多维空间的投影矩阵同样满足
最小二乘法就是投影矩阵的应用之一，假设存在数据(1,1),(2,2),(3.2)，我们需要找到拟合b = C+Dt，这就等价于：
显然并不存在于一条线可以同时连接三个点，因此等式不可解，等我们可以求
本章主要讲向量、基和子空间正交的相关内容，核心内容是矩阵的行空间与其零空间正交，其列空间与其左零空间正交。
正交是垂直的另一种说法，如果两个向量之间的角度为90度，则它们是正交的。如果两个向量正交，则它们形成直角三角形，其斜边是向量之和。
因此可以使用毕达哥拉斯定理来证明，当x和y正交时，点积
子空间S与子空间T正交的定义：S中的每个向量都与T中的每个向量正交。
矩阵的行空间与零空间正交，因为Ax = 0就意味着x与A的每一行的点积为0，x与A的任意行组合的乘积也必须为0。
同理，列空间与A的左零空间正交，因为
实际上，矩阵的行空间和零空间将一个
零空间不仅与行空间正交，而且它们的维度加起来就是整个空间的维度，因此另一个说法就是零空间和行空间是
因为测量误差的存在，
只有在A的列都是不相关时（
举个例子：
这个例子就是可逆的。
这一章主要讲述任意允许加法和标量乘法的向量组成的向量空间。
首先来看3x3的矩阵M，从这种矩阵可以得到三种子空间，分别是对称矩阵S，上三角矩阵S以及这两种矩阵的交集——对角矩阵的空间。M的维度是9，因为必须要选择9个数字来表示矩阵的9个位置，这就非常类似
S的维度是6，S的元素主要是需要决定对角线的三个位置和右上角的三个位置。至于基的选择也是6个矩阵：
U的维度也是6，原因和基的选择与S类似，并且着恰好是M的基的子集。
D是S跟U的交集，因为它们基的交集恰好是3个，因此其维度也是3。
然而S跟U的并集却不是一个子空间，我们必须要对此进行填充，得到我们所说的和S + U。这是 M 的子空间。事实上，S + U = M。
现在考虑5 × 17的矩阵空间M，即使包含零矩阵，但包含所有4阶矩阵的M子集也不是子空间，因为两个 4 阶矩阵的和可能不具有 4 阶。
对于
列空间A为R1，左零空间仅包含零向量，维度为零，其基是空集。 A的行空间的维度也为 1。
矩阵的秩是其列（或行）空间的维数。矩阵
每个1阶矩阵A都可以写成
本章还介绍了一些微分方程或者图论看作向量空间去考虑的内容，这里就不细说了。
本章主要介绍一个矩阵A相关的四大子空间：
所有3×3矩阵的集合形成一个向量空间，称之为 M。我们可以将矩阵相加并将它们乘以标量，就得到了一个零矩阵（加法恒等式）。如果我们忽略矩阵相互相乘时，它们的行为就像向量一样。M的子空间包括了：
这一章主要讲了一些概念。
假设A是一个m x n的矩阵（m < n，Ax = b有着比等式更多未知数）。如果A至少有一个free variable，那么就会存在非零解使得Ax=0。那么A的列就是dependent。
如果两个向量不在同一条直线上，则它们是dependent。如果三向量不在同一平面上，则它们也是dependent。将Ax视为A列向量的线性组合，如果A的nullspace仅仅包含零向量，那么A的列向量independent。
如果A的列是independent，则所有列都是pivot列，A的rank为n，没有自由变量。如果A的列是dependent，则rank(A) < n。
向量v1,v2,..,vn span成一个空间的意思就是，这个空间由这几个向量的任意线性组合组成。例如A的列向量组成了A的列空间。
一个向量空间的基(basic)就是一组符合如下特性的向量序列：
举个例子，
然而矩阵
假设存在矩阵
根据定义，A的四个列向量span A的列空间，其中第三和第四个列向量依赖于第一和第二列向量，前两列是独立的。因此，前两个列向量是主元列，它们构成列空间C(A)的basic。该矩阵的秩为 2。事实上，对于任何矩阵A都存在：
1 | rank(A) = number of pivot columns of A = dimension of C(A). |
这里矩阵A的列向量不是独立的，因此N(A)不仅仅包含零向量，所以存在
1 | dimension of N(A) = number of free variables = n − r, |
这一节主要是解
我们还是用这个矩阵作为例子：
确定
通过前面的学习，我们知道当b在列空间C(A) 中时，Ax = b就是可解的。事实上，这两种求可解性是等价的。
为了找到
找到方程
因此
矩阵的秩就是矩阵pivots的个数，如果A是秩为 r 的 m × n
矩阵，那么一定存在 r ≤ m 且 r ≤ n。此时
如果 r = n，那么从前面知道零空间的维度为n − r =
0并且仅包含零向量，不存在自由变量或特殊解。如果
如果 r=m，RREF就是
如果 r = m = n，则 A
是可逆方阵，RREF是单位矩阵。零空间的维度为零，并且
随着LSM在NoSQL的应用越来越广泛，关于LSM的研究也变得越来越多。本文是一篇综述，主要目的是提供一些关于LSM存储技术的最优选择和前沿研究，并详细地介绍了相关技术对LSM系统的提高和权衡。
这一章主要是回顾了LSM树的背景，并深入讨论了LSM的基本结构。
存储引擎主要分为两类结构：一是原地更新，如B+树等；另一个就是LSM树。前者对读和空间利用更友好，但牺牲了写的性能，至于后者则是对写更友好，但牺牲了读。非原地更新的结构在70年代就提出了，那时的做法就是将所有的写顺序地写到log文件里，但这种append-only logs的结构其读性能太差了，而且需要设计一个良好的逻辑去回收数据，做数据重组织。到了90年代，当下流行的LSM基本结构才逐渐成型，引入了多层结构，写memtable，实现了tiering merge策略等。
这一章主要介绍了基本的LSM结构，现在的LSM实现仍然是非原地更新的方式从而尽量减少随机IO，所有的写入都会append到memory component中。disk components则是进行定期的合并然后生成新的component，而不会去修改现有。
通常来说会使用跳表或者B树去组织memory component，而disk component则是由B树或者sstable组成，一个sstable包含了多个data blocks和一个index block。对于LSM的查询来说，点查会从最新的component找到最旧的component，找到即返回，至于范围查询则需要所有层次的component都遍历一遍，丢到优先队列去归并。
最后则是介绍了下图所示的merge策略，主要分为两种：第一种是Leveling merge，每层只有一个component，然后下一层是当前层的T倍大小；另一种则是Tiering merge，每层最多T个components。前者对于查询更友好，后者则有利于写入。
目前大多数LSM-tree实现都使用了两种比较流行的优化方法：一是bloom filter，它可以以非常节省空间的方式来判断集合成员的存在与否，它通常构建在磁盘组件之上，放在内存中，以极大地提高点查性能。
另一种则是Partitioning，LSM树的磁盘通常会被划分为多个小分区，对应到LevelDB就是sstable。这种划分方法可以限制每个合并操作的处理时间以及创建新sstable所需的临时磁盘空间，另一方面也可以避免因为顺序更新或者热点更新带来的负载，前者几乎不需要合并，而后者则不需要合并那些不涉及的小分区。如下图所示，leveldb的L0多个分区一般是具备重叠键范围的，这是因为这些分区是由memtable直接flush的。
接下来主要讨论当今 LSM-tree 实现所使用的并发控制和恢复技术。对于并发控制，LSM-tree需要处理并发读取和写入并处理并发刷新和合并操作，这里确保并发读写的正确性是数据库系统中访问方法的基本要求。根据事务隔离要求，现在的 LSM-tree实现要么使用锁方案，要么使用多版本方案。后者天然适用于LSM树，因为在合并期间可以自然地对key的过时版本进行垃圾收集。对于恢复，则是使用WAL的方法，即先写日志再写memtable。
尽管LSM tree在NoSQL领域很受欢迎，但基本的设计仍然存在各种缺点和不足。一是写放大，包括leveldb、RocksDB等采用了水平合并策略，仍然会产生相对较高的写入放大。二是合并操作会对系统产生负面影响，包括合并后的缓冲区cache miss和大规模合并期间可能产生的写入停顿。三是如何充分利用硬件，早期的LSM-tree是为硬盘设计的。四是如何调整和定制基本的LSM树实现，以更好地应对特殊的工作负载。五则是Auto-Tuning，由于LSM-trees具备非常多可以调整的参数，需要对应不同的场景以实现最佳选择。六是二级索引，基本的LSM-tree只提供了简单的kv接口，如何在写入性能开销很小的情况下有效地维护一组相关的二级索引是非常值得探讨的。
本节主要讲述为减少LSM树写入放大的改进。
优化写入放大的一种方法是tiering的应用，因为它的写入放大比leveling低得多。文中提到了四种基于tiering进行的结构：
这四种结构都具有类似的基于partitioned tiering和垂直分组的高级设计，本质上都是用查询换取更低的写放大，它们的主要区别在于如何应付SSTable组的工作负载平衡。
skip-tree提出了一种合并跳过的想法来提高写入性能，如果可以实现将item跳过一些级别去合并，那么总的写入成本就会降低。如下图所示，在级别L的合并期间，skip-tree直接将一些key推送到可变的Level L+K的缓冲区，以便可以跳过一些逐级合并的层级。同时，可变缓冲区中跳过的item将在后续合并期间与Level L+K的SSTable合并。为确保正确性，只有当该key未出现在任何中间层才可以，这通过检查中间层级的布隆过滤器来满足条件是否成立。
TRIAD的做法是在memtable中将热键与冷键分开，以便只有冷键被刷新到磁盘，因此当热键更新时，可以直接丢弃旧版本，而无需将它们写入磁盘。这个设计减少了一些热key频繁更新的倾斜更新工作负载带来的写入放大。热key是定期复制到新的事务日志中，以便回收旧的事务日志。另外TRIAD还通过延迟level 0的合并来减少写入放大，直到level 0包含多个 SSTable。最后还提出了一种优化，可避免在刷新后创建新的磁盘组件，相反直接在事务日志本身构建索引结构以提高查找性能。
Tiering已被广泛用于提高LSM树的写入性能，但这会降低查询性能和空间利用率。现有的基于Tiering的改进主要在 SSTable的管理方式上有所不同，通过垂直分组或水平分组来满足写入需求，另外skip-tree和TRIAD也提出了几个新的想法来提高写入性能。虽然这些改进都声称极大地提高LSM-tree的写入性能，但往往没有考虑LSM-tree的可调能力，因为他们都是与默认配置的LevelDB 或 RocksDB比较评估的。
在merge性能提升方面很多研究都提出了相应的设计方法，VT-tree提出了一种stitching的操作来提高性能，其基本思想是，在合并多个SSTable时，如果输入的SSTable中某个页面的key范围不与其他SSTable中的任何页面的key范围重叠，则该页面可以简单地被生成的SSTable指向，而无需读取和复制一遍。缺点是可能导致页面碎片和无法生成布隆过滤器。
还有一种思路如下图所示就是利用流水线优化，以更好地利用CPU和I/O并行性来提高合并性能，完整的合并操作包括了合并操作包含多个阶段，读取阶段、合并排序阶段和写入阶段。通过将其组合成流水线执行可以进一步加速合并。
这一章主要是讲了由于sstable合并导致旧sstable删除引起的cache miss优化，文中提到的一个做法是用缓存预热的方法，将来自对旧sstable的查询平滑地重定向到新sstable。还有一种做法是将level L的就sstable，附加到与level L+1关联的缓冲区中，而不是立即删除，这些旧sstable也会被查询搜索以减少缓冲区缓存未命中，并根据访问频率逐渐删除它们。
这一章主要提出了一些关于优化合并操作的实现，包括写入性能、buffer cache命中率和write stall等。
本章主要介绍了一些关于自动调整LSM参数的技术研究。
有一些研究提出了一个分析模型，通过统计key的分布来改进LSM操作的成本估计，关键目标是如果能在合并早期就发现某个key被删除或者被更新，它就可以避免前面的合并，减少写放大。
还有一些研究是关于如何调整memtable与bloom filter之间的内存分配情况，以便找到特定工作负载最佳LSM设计，这里的一个关键是尽可能将Bloom filter的bit分配给低级别的sst table，最小化所有Bloom filter的误报率，从而最大化吞吐。
这一篇论文主要是一个综述文章，把最近的关于改进LSM tree的研究工作分别简单地介绍了下，如果有必要的话，最好是详细阅读其中的论文。
这一章主要讲的是如何计算矩阵的nullspace
假设要计算
得到U之后，就可以通过代入找到x的解了，这里第一和第三列包含了主元，我们将其定义为pivot
columns，其他的就是free columns。我们令
继续使用消除法可以将U转换为简化reduced row echelon form (rref
form)的矩阵R，其中主元都等于1，而主元上方和下方均为零。
这一章主要介绍矩阵的 column space 和 nullspace。
向量空间是在线性组合下的向量集合，简单来说，对于向量空间中的任意两个向量v和w以及任意两个实数c和d，其线性组合cv+dw也在向量中。子空间就是指一个包含在另一个向量空间的向量空间。
一个包含了
A的列空间，顾名思义就是矩阵A的所有列向量的线性组合。
给一个矩阵A和什么样的向量b才能使得
对于上面矩阵A这个例子，不同列之间并不是独立的，比如第三列就是前面两列的和，因此A的列空间其实就是
A的nullspace其实就是满足
以这个为例：
并不是任意等式的答案集都是一个子空间，因为零向量的存在无法使其满足条件。