存储引擎： 负责内存和磁盘上存储、检索和管理数据。

章一

MySQL的存储引擎：InnoDB/MyISAM/RocksDB

选择数据库时，应该从清晰界定的目标开始。在不同数据库系统上模拟这些工作负载、测量对开发重要的性能指标，并比较结果。对于性能或者可伸缩性方面的问题，只有在一段事件后或随着容量的增长才会开始显现。在接近真实生产环境中进行长期测试可以发现潜在问题。

TPC-C基准

该基准关注的是执行的并发事务的性能和正确性。

主要的性能指标：吞吐量（数据库系统每分钟能够处理的事务数）

其需要执行事务具备ACID属性并符合基准本身定义的属性集。

acid属性

原子性（Atomicity）

原子性是指事务是一个不可分割的工作单位，事务中的操作要么都发生，要么都不发生。

一致性（Consistency）

事务必须使数据库从一个一致性状态变换到另外一个一致性状态。

隔离性（Isolation）

事务的隔离性是多个用户并发访问数据库时，数据库为每一个用户开启的事务，不能被其他事务的操作数据所干扰，多个并发事务之间要相互隔离。

持久性（Durability）

持久性是指一个事务一旦被提交，它对数据库中数据的改变就是永久性的，接下来即使数据库发生故障也不应该对其有任何影响。

选择数据库时最好跟踪新版本，了解由于什么原因发生了什么变化。阅读开发者以前处理升级的办法帮助未来进行数据库升级。

设计存储引擎

设计物理数据布局和组织指针、决定序列化格式、了解数据将如何被进行垃圾收集、存储引擎如何适应整个数据库系统的语义、探索如何使其在并发环境中工作，以及最后确保在任何情况下都不会丢失任何数据。

不同的设计决策会适合于不同的情况：有些对低读写延迟进行了优化，有些会最大化存储密度（每个节点存储的数据量），有些专注于运维上的简单性。

章二

b树的平衡

基于磁盘存储的树（不太了解

扇出：每个节点允许拥有的最大子节点数

由于扇出较低，会频繁的执行平衡操作、重新定位节点并更新指针，所以要更换掉二分搜索树这个数据结构存储在磁盘上。

问题

局部性：元素随机顺序添加，可能导致节点子指针跨越多个磁盘页（通过修改树的布局和使用分页二分树，可以改善）

树高：O(log2 N)次查找以定位要搜索的元素，会执行相同数量的磁盘传输。

总结：高扇出与低高度是实现最佳磁盘数据结构所需的特性。

分页二叉树

这是将节点分组到页来设计二分树的布局改善了上述说的数据局部性。要找到下一个节点，在页面中追踪指针即可。同时磁盘上的布局结构进行进一步维护会导致指针更新，增加开销。

B树的特征在于其扇出，存储在每个节点中的键的个数。

描述键和子节点偏移量数目的方法：用自然数k表示最佳页大小，页可以保存k到2k个键，但是可以被部分填充并保存最少k+1，最多2k+1个指向子节点的指针。

（补充b树属性+图）

B树是一种专用的M阶树，可广泛用于磁盘访问。

1.b树中的每个节点最多包含m个子节点。

2.除根节点和叶节点外，b树中的每个节点至少包含m/2个子节点。

3.根节点必须至少有2个节点。

4.所有叶节点必须处于同一级别。

总结

这一章讲采用磁盘存储专用结构，然后由于二分搜索树与b树在扇出等方面的区别，采用b树这个数据结构。

我的理解：由于磁盘访问可以采用建立索引进行一个磁盘预读。预读是根据程序的局部性原理为基础。所以存储空间会局限于某个内存区域，那我们可以提前准备好要用的数据，使磁盘预读，提升I/O效率。

预读的长度一般为页的整数倍。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。然后在设计过程中，我们讲一个节点作为一个页，这样一页代表一次I/O操作。采用b树，非页节点只存有key值，会有更多空间，存更多的key值，减少相应的I/O操作。

3层的B树（一页1024个字节）可以容纳差不多10亿个数据，如果换成二叉查找树，需要30层，I/O操作次数减了很多。假定操作系统一次读取一个结点，并且根结点保留在内存中，那么B树在10亿个数据中查找目标值，只需小于3次硬盘读取就可以找到目标值

下文应该是对b树进行一个主要设计。

章三 文件格式

非托管内存模型的语言允许我们在需要时分配更多的内存，而不必是否有连续的内存段、分段还是连续的、释放后的问题。

托管和非托管是修饰内存的。

托管的意思，不用直接操作内存，你需要的时候跟我说。我替你申请，然后给你用，你用完可以告诉我，我帮你释放，如果你忙，忘记告诉我了，我也会在定期去帮你释放的。 这就是托管，你打交道的不是直接的内存，而是.net clr。

非托管的意思就是要自己负责管理内存，这里所说的内存管理。实际上只是堆上的内存管理，栈内存和以前的一样，函数退出则释放，heap上的内存，非托管内存需要自己分配，调用构造函数(c需要，c++里用new替代这部操作了)，使用完毕后，需要自己释放这个内存，如果你不小心，把指向内存的指针弄丢了，就造成内存泄露了，这个内存泄露在你程序退出之前是无法弥补的。

大端小端（机组里面的知识）

大端：最高有效字节具有最低的地址。

小端：从最低有效字节开始，从地位到高位依次排列。

设计单元格布局：

键单元格包含一个分割键和一个指针（指向两个相邻键之间的页）。

键值单元格包含键和相关联的数据记录（也就是值）。

两者的区别是键单元格存该单元格指向子页的ID、键值单元格存值的长度和数据记录的数据。

将单元格放进分槽页，单元格追加到右侧，指针放在页左侧。

可用列表是用来对于每次插入新单元格时字节检查，看是否能放下，同时删除记录时，直接将该单元格标记删除，根据被释放内存大小和指针更新可用列表。包括两个分配算法（os中的）首次适配优先和最佳适配优先。

校验和（计网）和CRC。

校验和不能检测多个比特位损坏，用XOR结合奇偶校验或求和计算。

CRC用来检测连读多个比特位的损坏，使用查找表和多项式除法实现。

在数据写入磁盘之前，我们计算其校验和与数据一同写入，当读取数据时，我们再次校验进行比较验算，得到当前数据是否准确。

本章介绍了如何用二进制形式表示键和数据记录，多个值组合成更复杂的结构，以及如何实现可变长度的是数据类型和数组。学习构建单元格、构建层次结构以及使用指针与页进行连接。

章四

页头

页头保存用于页定位、维护和优化信息。

放置魔数表示页，常用于校验和完整性检查。指针包括同级指针与最右指针。有助于定位相邻节点也为后续的分裂合并操作增加复杂度。最右指针会单独存储，子节点拆分后会更新最右指针。

高键：blink树添加kn+1 键，会指明上限，一个设计。

溢出页依次链接，类似与多级索引的一个连接方式进行存储额外的记录。

搜索、分裂合并、平衡、压缩、清扫维护

常用栈来保存路径信息。（由遍历目标叶节点路径可反向跟踪父节点链路）

再平衡是一种有用技术，可以推迟分裂和合并操作。用维护的操作次数来提高节点利用率以及减少树的层数。

有两种压缩方式：按页压缩和仅压缩数据。

由于页上进行维护操作，会导致页中逻辑空间充足而不能满足物理上连续空间的分配，即碎片化。类似于os中内存管理里面的碎片问题。

垃圾收集，一种重写页、将单元格按键顺序排列，并回收被不可寻址单元格占用的空间的过程。

总览本书几乎前三分之一的内容都在介绍 B 树相关内容，包括原理、实现、使用等，对于可变性，重点介绍了节点的分裂与合并、页布局，即如何编码数据、组织数据等。