第一章

讲了数据库的基本组件.行存与列存区别.数据文件和索引文件(文件分页的页大小 一般是磁盘块大小的整数倍,这样一次io我们就可以拿出正好完整的一些数据).数据文件分为堆文件(顺序插入),哈希文件(先定位桶,再定位桶中的具体数据).索引组织文件(就是常见的根据索引组织数据的方式,叶子节点有完整的数据,而不是数据的引用or指针).这一章还说了一下间接索引的事,说白了就是一,二级索引(二级索引保存主键id,之后再走一边主键索引找到数据,也叫回表).这里也有一个常问的问题,有点憨批,所以直接说结论,主键索引不一定聚簇,聚簇索引一定是主键索引.其实也没有那么绝对,所以问这个问题挺憨憨的,换一种文件组织方式就又不一样了.软件没有绝对的,我们常聊的无非是一类问题最常见的那一个解决方案.最后讲了缓冲(写入不够一个磁盘块,就先在内存攒着,减少io次数)不可变性(修改时是原位置修改还是按照写log在文件尾部插入)和有序性(是否按照键顺序存储).

第二章

讲了b树相关,基本数据结构,查找,分裂,合并.但是分裂合并讲的有点唠叨,应该是翻译的问题,这里推荐看一下极客时间的那个数据结构的专栏讲的比较清晰.

第三章

第三章讲的文件系统设计和文件格式的一些事,如何用最少位表示数据,二进制的序列化和反序列化,设计寻址方式.是否需要将文件差分成页,页是否由多个块组成.页在内存中被写满了,就刷入磁盘里面去.

schema(表结构)的好处是有助于减少磁盘上存储的数据量,,需要使用位置标识符而不用让每条记录都带上字段名. 其实就是把一些元信息的起始偏移量存下来,从而加速某些查找.

原始b树论文描述了一种,简单的用来记录定长数据的格式,由p(子页指针),k(键),v(值)三元组构成页.具体来看就是个数组,所以尾部追加没有问题,其他位置的插入和修改代价就比较大,需要移动元素.

已经删除的空间需要回收,我们可以把新的数据存进去.双方大小相等,刚好不浪费空间,回收小于新数据,在找一块空间用来存储剩余的新数据,回收大于新数据就会造成空间浪费,这时候就应该个找一个新空间存储新数据,而不是复用回收旧空间.

分槽页的组成:head,指针,cell(槽 or 单元格).head记录一些元信息,指针指向cell,cell存储具体数据.

分槽页为什么是一种好的页格式?
1.已最小开销存储变长记录:分槽页唯一的开销就是维护指针数组,用于保存记录实际所在的位置.
2.通过对页进行碎片整理和重写 ,就可以回收空间.
3.动态布局:从页外部,只能通过槽id来引用槽,而确切的位置是由页内部决定的(可以说是做了一层解耦吧)

单元格分为两种其实也就是叶子节点和非叶子节点的区别.单元格类型和键,键长是都有的数据,叶子节点村具体的记录和其长度,非叶子节点存储页id.由于每个页都是固定大小,所以可以通过schema查找真正的文件偏移量.

单元格插入分槽页:首先是头部元信息(老三样了).后门跟着的是偏移量数组(从左往右),中间是剩余空间,最后是实际的单元格数据,单元格的插入是从右往左.这样做保证了插入的逻辑顺序(只需要维护偏移量指针顺序即可,不需要移动单元格的位置).

可用列表用来记录一个页里面被标记的删除的单元格,存储可用段的偏移量和大小.碎片整理就是读出所有的单元格重新写入,这样就将可用的单元格做了聚合.如果碎片整理之后还无法存下,那么就创建一个溢出页.

当存储引擎存在多个二进制文件的格式时,可用版本前缀来区分.

最后提了一下crc.感觉上类似md5,这种吧,但不是防人的,使用验证 软硬件故障 导致的文件变更,一般放在的页的head里

第四章

页头的元信息里会存储本页的记录总数,所以在现在本版的mysql里用count(*)应该也不慢了,获取列信息的时候顺便获取纪录数.

魔数也是元信息用来代表页,附带版本信息,可以用来做完整性校验.

同级指针将b树统一层的字节点连成链表,方便了同层节点的定位,

最右指针一般单独存储,因为它并没有与任何键相匹配.一般存储在头部.

由于b树算法规定,每个节点都持有特定数量的元素,当存储变长值的时候就会出现这种状况,元素没存够但是页满了,这时候就允许创建一个以4k(一般是这个大小)为增量的页,然后将还未存储的元素存在这个页里,并将这个页链接在原始上.这个也就叫做溢出页.

b树页总会保留max_payload_size(节点大小除以扇出)个字节,用于存储载荷数据.当插入的数据大于这个值时,就看看这个原始页是不是已经有溢出页了,有的话看一下空间够不够,够就存在这个溢出页里,不够的话就创建一个新的溢出页.

当有多个溢出页时,可以把溢出页的id存储在主页的头里,并用链接起来(意思应该就是存个链表)

导航信息(访问过的节点和单元格索引)就是进行一次插入或者删除时,将节点遍历(从根到叶的引用),用于在传播分裂或合并时进行反向回溯.最自然的结构是栈

一些b树的实现方案试图推迟分裂和合并操作，以便通过在层内再平衡各元素来摊平代价，或将元素从占用较多的节点转移到占用较少的节点中，通过这一方式尽可能推迟分裂或合并．这样做可能维护成本大一些，但是有助于提高节点利用率和减少树的层数．比如说在插入的时候将一下元素转换到同级的另一个节点中，并为插入腾出空间，删除的过程中，我们可以从相邻的节点中移动一些元素，而不是合并同级节点，以确定节点至少是半满的．在平衡改变了同级节点的最小最大不变量，我们必须相应地更新父节点键和指针．