作为一名应用系统开发人员，为什么要关注数据库内部的存储和检索呢？首先，你不太可能从头开始实现一套自己的存储引擎，往往需要从众多现有的存储引擎中选择一个适合自己应用的存储引擎。因此，为了针对你特定的工作负载而对数据库调优时，最好对存储引擎的底层机制有一个大概的了解。
索引
索引是基于原始数据派生来的额外数据结构，很多数据库允许单独添加或删除索引，从而不影响数据库的内容，它只会影响查询性能。它们背后的基本想法是保留一些额外的元数据，这些数据作为路标，帮助定位想要的数据。索引作为额外引入的结构，在维护时势必会引入开销，特别是在新数据写入时。对于写入，它很难超过简单地追加文件方式的性能。对于每次写入数据时，需要更新索引，因此任何类型的索引通常都会降低写的速度。
这里涉及存储系统中重要的权衡设计：适当的索引可以加速读取查询，但每个索引都会减慢写速度。为此，默认情况下，数据库通常不会对所有内容进行索引，它需要应用开发人员或数据库管理员，基于对应用程序典型查询模式的了解，来手动选择索引。目的是为应用程序提供最有利加速的同时，避免引入过多不必要的开销。
哈希索引
首先我们以key-value数据的索引开始，key-value类型数据并不是唯一可以索引的数据，但是它随处可见，而且是其他复杂索引的基础构造模块。
key-valuy存储与大多数编程语言所内置的字典结构非常相似，通常采用hash map来实现，那么既然已经有了内存数据结构的hash map，为什么不用它们在磁盘上直接索引数据呢。
假设数据存储全部采用追加式文件组成，那么最简单的索引策略就是：保存内存中的hash map，把每个键意义映射到数据文件中特定的字节偏移量，这就就可以找到每个值的位置。
如果所有的key可以放进内存，只需要进行一次磁盘寻址，就可以将value从磁盘加载到内存。如果那部分的数据文件已经在文件系统的缓存中，则读取根本不需要任何的磁盘I/O。
但是，如果数据只追加到一个文件，那么如果避免最终用尽磁盘空间？一个好的解决方法是将日志分解成一定大小的段，当文件达到一定大小时就关闭它，并将后续写入到新的段文件中。同时，对于已经关闭的段文件，可以在每个段文件内部执行压缩操作，丢弃重复的键，只保留每个键在在段文件中最新的值，一个段文件压缩之后通常会使得段文件变得更小。在多个已经关闭的段文件直接可以执行合并操作，将多个压缩过的段文件合并成一个段文件。
这些冻结段的合并和压缩过程可以在后台线程中完成，而且运行时，仍可以使用未合并和压缩的段文件继续正常的读取。当合并过程完成后，再将读取请求切换到新的压缩合并完成的段文件上，旧的段文件则可以安全的删除。
每个段文件都有自己的内存hash map，用于将键映射到段文件中的偏移量。为了找到键的值，需要将所有段文件的hash表加载进内存，然后首先检查最新段的hash map，如果键不存在，检查第二新的段，以此类推。由于合并后可以维持较少的段数量，因此查询通常不需要检查很多的hash map。
还有很多的细节方面的考虑才能使得这个简单的想法在实际中行之有效。简而言之，在真正地实现中有以下重要问题：
* 如果要删除键和它关联地值，则必须在数据文件中追加一个特殊的删除记录。当合并日志段时，一旦发现删除记录，则会丢弃这个已删除键的所有值。
* 由于写入以严格的先后顺序追加到文件中，通常的实现方式是只有一个写线程。由于数据文件段是追加的，而且已经写入的数据是不可变的，所以它们可以被多个线程同时读取。
一个追加式的存储看起来似乎很浪费空间：为什么不原地更新文件，用新值覆盖旧值？但是，事实上，追加式的设计是一个不错的设计，原因有以下几点：
* 追加主要是顺序写，它通常比随机写快很多，特别是在旋转式磁性硬盘上。在某种程度上，属性写入在基于闪存的固态硬盘上也是合适的。
* 如果段文件是追加或不可变的，则并发和崩溃恢复要简单得多。里如果不必担心在重写值时发生崩溃的情况，留下一个包含部分旧值和部分新值混杂在一起的文件。
* 合并旧段可以避免随着时间推移数据文件出现碎片化的问题。
但是，哈希表索引也有其局限性：
* hash map必须全部放入内存，如果有大量的键，那么很可能超内存。原则上，可以在磁盘上维护hash map，但是，很难使磁盘上的hash map表现良好。它需要大量的随机访问I/O，并且哈希冲突时需要复杂的处理逻辑
## SSTable
对于单纯的将key-value按顺序添加到文件尾部的方式，如果在写入时对key进行排序，索引结构还是hash map。这样的存储形式就被成为SSTable（排序字符串表）。SSTable相对于单纯顺序添加的形式有以下几个优点：
1、在合并冻结段时更高效，由于每个段中的key都是有序的，合并时方法类似与归并排序merge sort的方式
2、不需要把段文件中每个key的偏移量都存进内存的hash map中，例如，如果当前查找的键handiwork，且不知道该键在段文件中的确切偏移量，但是如果知道键handbag和键handsome的偏移量，由于键在段文件中时有序的，可以跳到handbag的偏移，从那里开始顺序扫描，直到找到handiwork。所以，虽然仍然需要内存的hash map做索引，但是它可以是稀疏的，而且由于顺序扫描可以很快的扫描几千个字节，所以通常对于一个段文件，只需要每隔几千个字节选一个key添加到内存中的hash map做索引即可。
但是，如何保证在写入段文件的key-value保持有序呢。虽然在磁盘上维护排序结构是可行的，例如B-trees，但是在内存中做排序更容易和高效，内存排序有很多广为人知的树状数据结构，例如红黑树或AVL树，可以在插入键时完成排序。
所以SSTable结构的基本构建流程如下：
1、写入key-value键值对时，将其添加到内存中的平衡树数据结构中
2、当内存中的平衡树结构大于某个阈值时（通常为几M字节），将其作为段文件写入到磁盘，由于平衡树已经维护了排序过的键值对，所以写磁盘也很高效。在将平衡树写入磁盘的时候，后续的写入则添加到到另外一个新的内存中的平衡树中
3、在处理读请求时，首先从内存的平衡树中查找，接着是最新的段文件，然后是此新的段文件，以此类推（相对于之前增加了一个内存查找的过程）
4、后台进程周期性地执行段合并与压缩地过程。
但是，如果内存中的平衡树还未写入到段文件时，此时系统崩溃了，怎么办呢，内存中的数据无法再恢复。所以，通常SSTable还需要配置日志使用，每个写内存平衡树的记录同时也要写到一个顺序添加的日志文件中。如果系统崩溃，已经写入段文件的可以直接读磁盘恢复，内存中的数据则从日志文件恢复。当内存中的平衡树写入到段文件后，该日志文件就可以丢弃了。
LSM-Tree
像SSTable这样类似日志不断在文件末尾进行添加的索引结构称为日志结构的合并树——LSM-Tree（Log-Structured Merge-Tree）
B-trees
B-tree是一种常见和被广泛使用的索引类型，它几乎时所有关心数据库中的标准索引实现。
B-tree本质上也是一种排序的树形数据结构，它在数据库系统中的使用形式一般如下：
将数据库划分为固定大小的块或页，传统上大小为4KB，页是内存读/写的最小单元。这种设计更接近底层硬件
每个页都可以使用地址或者位置进行标记，这样可以让一个页面引用另一个页面，类似指针，只不过是指向磁盘地址，而不是内存，这样可以使用这些页面引用来构造一个树状页面
每一个页包含若干个键和对子页的引用。某一页被指定为B-tree的根，每当查找索引中的一个键时，总是从这里开始。B-tree中一个页包所包含的子页引用数量成为分支因子。在实际中，分支因子取决于存储页面引用和范围边界所需的空间总量，通常为几百个。
如果要更新B-tree中现有键的值，首先搜索包含该键的叶子页，更改该页的值，并将页写回到磁盘（B-tree中对该页的引用仍有效）。如果要添加键，则需要找到其范围包含新键的页，并将其添加到该页。如果页中没有足够的可用空间来容纳新键，则将其分裂为两个半满的页，并且父页也需要更新以包含分裂之后新的键的范围。
B-tree底层的基本写操作时使用新数据覆盖磁盘上的旧页。它假设覆盖不会改变页的磁盘存储位置，也就是说，当页被覆盖时，对该页的所有引用保持不变。这与LSM-Tree引形成鲜明对比，LSM-Tree仅追加更新文件。
但是，覆盖操作是危险的，在硬件层面，意味着磁头首先移动到正确的位置，然后旋转盘面，对于SSD，由于SSD必须一次擦除并重写非常大的存储芯片块，情况会更复杂。此外，某些操作需要覆盖多个不同的页，例如，如果插入导致页溢出，因而需要对页进行分裂，那么需要修改三个页（分裂后的两个页和父页），这是个比较危险的操作，因为如果数据库在完成部分页写入之后发生崩溃，最终会导致索引破坏，例如分裂后新形成的页的引用未更新到父页中，成为一个孤儿页。
为了使数据库能从崩溃中恢复，常见B-tree的实现需要支持磁盘上的额外的数据结构：预写日志（write-ahead log，WAL），也成为重做日志。这是一个仅支持追加修改的文件，每个B-tree的修改必须先更新WAL然后再修改树本身的页。当数据库在崩溃后需要恢复时，该日志用于将B-tree恢复到最近一致的状态。对比B-tree和LSM-tree
尽管B-Tree的实现比LSM-tree的实现更为成熟，然而由于LSM-tree的性能特点，LSM-tree目前仍很有吸引力。根据经验，LSM-tree通常对于写入更快，而B-tree被认为对于读取更快。读取通常在LSM-tree上较慢，因为它们必须在不同的压缩阶段检查多个不同的数据结构和SSTable
LSM-tree相对于B-tree的优点
B-tree索引必须至少写两次数据：一次写入预写日志，一次写入树的页本身（还可能发生页分裂）。即使该页中只有几个字节更改，也必须承受写整个页的开销。一些存储引擎甚至覆盖相同的页两次，以避免在电影故障的情况下最终出现部分更新的页。像这种由于一次数据库写入请求导致多次磁盘写的情况成为写放大，对于SSD来说，由于只能承受有限次地擦除覆盖，因此尤为关注写放大指标。
对于大量写密集地应用程序，性能瓶颈很可能在于数据库写入磁盘地速率。在这种情况下，写放大具有直接地的性能成本。LSM-tree通常能够承受比B-tree更高的写入吞吐量，部分是因为它们具有较低的写放大，还有部分原因是因为它们以顺序方式写入紧凑的文件，而不必重写多个页（这种差异对于磁盘驱动器尤为重要，原因是磁盘的顺序写比随机写得要快得多）。
由于B-tree以页为单位，每个页中很有可能有不能利用的磁盘空间，即磁盘碎片，而LSM-tree不是面向页的，而且定期对数据进行合并，所以它们具有较低的存储开销。
在许多SSD上，硬件底层使用日志结构化算法会将随机写入转换为底层存储芯片上的顺序写入，所以对SSD来说，顺序写和随机写的影响差异不那么明显。然而，更低的写放大和更少的磁盘碎片在SSD上仍然有益，以更紧凑的方式表示数据，从而在可用的I/O带宽中支持更多的读写请求。 **LMS-tree相对于B-tree的缺点** LMS-tree的缺点就是压缩过程有时会干扰正在进行的读写操作，压缩和合并操作在后台进程中进行，由于磁盘的并发资源有限，所以当磁盘执行昂贵的压缩操作时，很容易发生读写请求等待的情况（B-tree的响应延迟更具有确定性）。随着数据库数据的增长，合并和压缩操作消耗磁盘的带宽会越来越多。 另外B-tree的一个优点就是每个键都恰好唯一对应与索引中的某个位置，而日志结构的存储引擎可能在不同的段中具有相同键的多个副本。如果数据库希望提供强大的事务语义，这方面B-tree显得更具有吸引力：在许多关系数据库中，事务隔离是通过键范围上的锁来实现的，并且在B-tree索引中 ，这些锁还可以直接定义到树中。总结
不考虑使用场景，空谈那种存储引擎更适合是没有意义的，实地测试总是需要的。其他索引结构
之前讨论的key-value索引，它们就像关系模型中的主键索引。主键唯一标识关系表中的一行或文档数据库中的一个文档或图形数据库中的一个顶点。数据库中的一行/文档/顶点通过主键来引用。
在索引中存储值（聚集索引）
索引中的key是需要查询的对象，索引中的value可以是以下两类之一：第一种，是实际行数据（或者文档，顶点），也可以是对其他地方存储的行的引用。在后一种情况下，存储行数据的具体位置被成为堆文件，而且它不以特定的顺序存储数据（它可以是追加的，也可以是覆盖的）。堆文件方式比较常见，这样当存在多个二级索引时，它可以避免复制数据，即每个索引只引用堆文件中的位置信息，实际数据仍保存在一个位置。
当更新值而不更新键时，堆文件方式会非常高效：只要新值的字节数不大于旧值，记录就可以直接覆盖，如果新值比较大，则情况比较复杂，它可能需要移动数据到一个最够大的新位置。在这种情况下，所有索引都需要更新以指向记录的新的堆位置，或者在旧堆位置保留一个间接指针。
在某些情况下，从索引到堆文件的额外跳转对于读取来说意味着太多的性能损失，因此可能希望将行数据直接存储在索引中，这被称为聚集索引。例如，在mysql的InnoDB存储引擎中，表的主键始终是聚集索引，二级索引引用主键（而不是堆文件位置）。 在聚集索引（在索引中直接保存行数据）和非聚集索引（索引仅存储数据的引用）之间有一种折中设计称为覆盖索引或包含列的索引，它在索引中包含部分列值。它支持通过索引来回答某些简单查询。 与任何类型的数据冗余一样，聚集和覆盖索引可以加快读取速度，但是它们需要额外的存储，并且会增加写入的开销。此外，数据库还需要更多的工作来保证事务性，这样应用程序不会因为数据冗余而得到不一致的结果。多列索引
到目前为止，讨论的索引都只有一个key，如果需要对多个key进行查询，就需要多列索引。但是多列索引是高维的，标准的B-tree和LSM-tree索引无法高效地应对这种查询，它们只能针对一个维度进行排序和查询。一种处理方式是将高维数据转换为一维度数据，但是，更常见的做法是使用专门的空间索引，如R树。
在内存中保存所有的内容
到目前位置，讨论的索引都是为了适应磁盘限制。与内存相比，磁盘更难处理。使用磁盘SSD，如果要获得良好的读写性能，需要精心地安排磁盘上地数据布局。然而这些工作是值得的，因为磁盘有两个显著的优点：数据持久化和低成本。
随着内存变得更便宜，而许多数据集不是那么大的情况下，可以将它们全部保存在内存中，或者分布在多台机器上。这推动了内存数据库的发展。
与直觉相反，内存数据库的性能优势并不是因为它们不需要从磁盘中读取。如果有足够的内存，即使是基于磁盘的存储引擎，也可能不需要从磁盘读取，因为操作系统将最近使用的磁盘块缓存在内存中。相反，内存数据库可以更快，是因为它们避免了使用写磁盘的格式对内存数据结构编码的开销。
另外，内存数据库提供了基于磁盘索引难以实现的某些数据模型。而且，内存数据库架构可以扩展到支持远大于可用内存的数据集，即当没有足够的内存时，通过将最近最少使用的数据从内存写到磁盘，并在将来再次访问时将其加载到内存。这与操作系统对虚拟内存和交换文件的操作类似，但数据库可以在记录级别而不是内存页的级别上工作。不过这种方法仍需要索引完全放入到内存。
如果将来非易失性存储（non-volaitle memory，NVM）技术得到更广泛的普及，可能还会颠覆目前的存储引擎设计，目前这还是一个新的研究领域，但值得密切关注。 # 事务处理与分析处理 数据库中的数据一般会用于两种用途，一种是用于在线事务处理（OLTP，online transaction processing），例如用户数据的增删改查，这种情况下一般只需要查找少量记录。另外一种是用于在线数据分析，例如获取一个月每个店铺的总收入是多少，这种情况一般会查找大量数据，这种叫做OLAP（online analytic processing）。 ## # 数据仓库 一个企业可能有十几种不同的交易系统，例如面向客户网站提供支持的系统、供应商管理系统、员工管理系统等。这些系统中的每一个都足够复杂，往往需要一个专门团队来维护，最终导致这些系统彼此独立运行。 由于这些OLTP系统对于业务的运行至关重要，所以往往期望它们高度可用，处理事务时延迟足够低，并且数据库管理员要密切关注OLTP数据库的运行状态。数据库管理员通常不愿意让业务分析人员在OLTP数据库上直接运行临时分析查询，这些查询通常代价很高，要扫描大量数据集，这可能会损害并发执行事务的能力。相比之下，数据仓库则是单独的数据库，分析人员可以在不影响OLTP操作的情况下尽情地使用。数据仓库包含公司所有各种OLTP系统的只读副本。从OLTP数据库（使用周期性数据转储或连续更新流）中提取数据，转换为分析友好的模式，执行必要的清理，然后加载到数据仓库中。
几乎所有的大型企业都有数据仓库，但是在小型企业中却几乎闻所未闻。这可能是因为大多数小公司没有那么多不同的OLTP系统，大多数小公司只拥有少量的数据，完全可以在传统的SQL数据库中直接进行查询分析。
另外使用单独的数据仓库而不是i直接查询OLTP系统来进行分析，很大的优势在于数据仓库可以针对分析访问模式进行优化。事实证明，前半部分讨论的索引算法适合OLTP，但不擅长应对分析查询。接下来将会讨论一些针对分析型而优化的存储引擎。
星型与雪花型分析模式
在事务处理领域有多种不同的数据模型（文档模型，关系模型，图模型），但是在分析型业务中，用到的数据模型则比较少，其中最主要的数据模型就是星型模型。该模型的中心是一个事实表，事实表的每一个行表示在特定时间发生的事件（例如代表客户购买了某个商品），在事实表周围，是许多个维度表，维度表通常记录时间发生的对象、时间、地点、原定等信息。事实表中通过外键指向这些维度表。
通常，事实被捕获为单独的事件，这样之后的分析具有很大的灵活性，但同时这意味着事实表会变得非常庞大，在大公司中，其数据仓库可能有数十PB的交易历史，其中大多数都保存在事实表中。
星型模型中如果对维度表进行进一步细分，将部分数据使用另外一个表格进行存储，然后再维度表中使用外键执行这些表格，这种变体就称为雪花模型。雪花模型比星型模型更规范，但是星型模型通常是首选，主要是对于分析人员，星型模型使用起来更简单。 在典型的数据仓库中，表通常非常宽：事实表通常超过100列，有时候有几百列。维度表也可能非常宽。列式存储
如果事实表有数万亿行，则高效地存储和查询这些数据将成为一个具有挑战性的问题。虽然维度表通常超过100列，但典型得数据仓库查询往往一次只访问其中的几列（select * 查询很少用于分析）。
在大多数OLTP数据库中，存储以面向行的方式布局：来自表的一行的所有值彼此相邻存储，文档数据库也是类似，整个文档通常被存储为一个连续的序列。为了处理数据仓库中在超过100列的数据中查询其中的几列的这种查询，如果仍使用面向行的存储引擎，则需要将所有一行中用不到的列数据从磁盘中加载到内存中。而面向列的存储，不需要将一行中的所有值存储在一起，而是将每列中的所有数据存储在连续的空间中，这很适合数据仓库中的查询场景。如果每个列存储在一个单独的文件中，查询只需要读取和解析在该查询中使用的那些列即可，这可以节省大量磁盘数据的加载。
面向列的存储布局依赖一组列文件，每个文件以相同的顺序保存着数据行，因此，如果需要重新组装整行，可以从每个单独的列文件中获取对应的条目，然后将它们放在一起构成表的一行。
列压缩
除了仅从磁盘中加载查询所需的列之外，还可以通过压缩数据来进一步降低磁盘数据的加载。幸运的是，面向列的存储恰好非常适合压缩，因为通常列中不同值的数量会小于行数（例如，零售商可能拥有数十亿个销售交易，但只有十万个不同的商品）。
一种常见的列压缩方法是使用位图编码+游程编码：一个列中有n个不同的值，则可以创建一个长度位n的位图，位图中的每一位对应一个不同的值，每一行都会有一个位图。但是，如果n很大，那边位图中就会有很多0，这时就可以使用游程编码对位图进一步压缩。
内存带宽和矢量化处理
对于需要扫描数百行的数据仓库查询，将数据从磁盘磁盘加载到内存的带宽是一个瓶颈，然而，这不是唯一的瓶颈。分析数据库的开发人员还要关心如何高效节省CPU访问内存的带宽，甚至是尽量减少CPU分支预测错误和CPU指令处理流水线中的气泡，并利用现代CPU中的单指令多数据（SIMD）指令。
面向列的存储布局也有利于高效利用CPU的缓存，例如，查询引擎可以将一大块压缩后的列数据放入CPU的L1缓存中，并以紧凑循环（即循环中没有函数调用和条件判断分支）进行迭代，这种技术被成为矢量化处理。
列存储中的排序
列存储中的排序并不是简单的单独对某列进行排序，这种排序是没有意义的，因为这样的话就无法知道列中的某一项实际属于哪一行。即使数据是按列存储的，也需要以行位单位进行排序。
数据库管理员可以基于经常查询的列来进行排序，例如，假如查询经常以日期范围作为目标，那么就可以对数据按照日期这一列作为第一个排序的key对数据进行排序。然后可以对第二经常访问的列作为第二排序key进行排序，以此类推。
排序的另外一个优点就是它可以帮助进一步压缩列，排序之后该列值相同的行会挨在一起，这时候一个简单的游程编码就可以表示多行。通常来说，第一个排序键的压缩效果最好，后面的排序键对压缩的提升效果就没有那么明显了。
列多存储排序
由于不同的查询会从不同的排序中获益，同时数据需要被复制到多台机器上防止单台机器出现故障时不会丢失数据，不妨存储不同方式排序的冗余数据到不同的机器上，在查询时可以选择最适合的排序版本进行查询。
面向列的存储具有多个排列顺序，有点类似面向行的存储中有多个不同的二级索引，但最大的区别是，面向行的存储将每一行都保存在一个位置（在堆文件或者聚集索引中），而二级索引只包含指向对应行的指针。而对于列存储，通常没有指向别处数据的指针，只有包含列的值。
列存储的写操作
面向列的存储、压缩和排序都非常有助于加速读取操作，但是，它们的缺点是让写入更加困难。
像B-tree使用原地更新的方式，对于压缩的列是不可能的，如果在排序表的中间插入一行，那么很可能不得不重写所有的列文件。
幸运的是，LSM-Tree可以比较好地解决这个问题：所有的写入首先写入内存，并在内存中进行排序，内存中的存储是面向行还是面向列的都无关紧要，当积累了足够的写入时，将它们和磁盘中的列文件合并，并批量写入新文件。执行查询时，就需要检测磁盘上的数据和内存中最近的写入。
聚合：数据立方体于物化视图
基本思想是由于数据仓库的查询通常涉及聚合函数，例如计算总量、平均值，最大值，最小值，每次都处理原始数据将非常浪费，可以缓存查询最常使用的一些计数信息。具体细节不进行讲解。