先说点题外，今天看到有人混淆buffer和cache两个概念，在英语世界，二者其实是有严格区分的：

A buffer is something that has yet to be "written" to disk.

A cache is something that has been "read" from disk and stored for latter use.

 

言归正传：

 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝行结构＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

innodb是典型的行存储引擎，它有两种行纪录格式，现在使用的格式叫compact格式，以前（5.0前）还有一种格式叫redundant格式。重点介绍compact格式。

 

存储format：

变长字段长度列表 // 对于固定长度的字段skip，通过表schema推衍，而redundant存的是offset，不区分变长和固长字段

NULL标志位表 // 每个字段一个bit，按字节对齐

记录头 //一些标志位（后面再详述）以及下一条纪录的相对位置，记录间类似链表的方式

列1

列2

…

 

有两个隐藏字段分别为transaction id（6字节）和roll pointer（7字节）。如果没有指定unique key，会自动生成6字节的row id作为 unique key。

NULL字段不占空间，对定长的char类型，如果字符不足则填充空格。

redundant格式因为没有NULL标志位表，所以NULL也是要占空间的。

 

行溢出。

一行最多1023个列，varchar最多65535字节。因为一个页（page）最多为16K，所以无论存放长的varchar还是blob or lob对象，都会导致行溢出，则该页只存储了部分字段内容（768字节前缀），剩余内容村道专门deuncompressed blob page中。varchar的内容是否放入blob page，有专门的算法，如果一页能够存下两行纪录，则不会放入blob page。

正常数据存放在b-tree node页中，溢出内容存放在uncompress blob页种。

 

char的行存储结构。

从mysql4.1开始，chr(n)种n指的是字符长度而不是字节长度，所以对于变长字符集（比如utf-8），内部会把其当成变长字符类型，因为utf-8单个字符字节数从1到3都有可能。

 

 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝页结构＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

因为缺乏可靠官方文档，所以这里的描述不一定正确。

 

所谓数据库其实就是有结构的文件系统，在一般文件系统（单机or分布式）基础上做一些封装便于结构化数据增删改除。其实，普通的文件系统也可以认为是一种特殊的数据库系统，是一种典型的对象（object）存储系统。

或者从数据结构的角度来讲，就是一堆磁盘上的数据结构加上一堆在内存中的数据结构，如果提高效率，就得设计一些相辅相成的精巧数据结构，很有意思的一件事，对不对。

 

数据页是b-tree的基本单位。

通常在定义数据页时，一开始要大致分好区间，至于某个区间内的具体内容（比如page header）刚开始未必能一下子想清楚，不过没关系，一般都是需要什么加什么，但经验会告诉你，一开始应该怎样给数据结构分区，这是关键。

 

file header：

－－check sum;

－－页在表空间中的偏移（序号）；

－－pre page && next page（序号）; B+ tree的特性决定了叶子节点必须时双向链表；

－－LSN（log seqeunce number）；该页最后被修改的日至序列位置 //？

－－页类型；

－－属于哪个表空间；

page header:

－－blablabla；很多，页的身份证信息，跟人一样，纪录注入性别、籍贯、xxx

infimum record: 虚拟行纪录，纪录比页中任意主键值都小的值；

supremum record：比任何业内主键值大的值；

－－注：这是数据库系统的常用做法。比如sstable file。

user record:

free space：占坑，因为page大小固定；需要注意的是，它是个链表结构，一条纪录删除后，会加到空闲链表中；

page directory:纪录的位置索引，多条纪录公用一个directory（slot）——sparse directory，用于在页内快速查找纪录；因为是稀疏的，所以仍需要通过record自身的next指针来作具体的record查找，是不是有点类似跳表的感觉？但这里可以对sparse directory进行二分查找。

－－注：这也是数据库系统的惯用手法，sstable file有类似机制。

file trailer: 用于保证页的完整性；这里有一些技巧性的东西，不详述。一般存储系统在进行数据块读入的时候都会进行数据校验来检测数据是否corrupt。

 

＝＝＝＝＝

后记

我们在了解一个数据库的时候，存储引擎是其核心部分，存储格式虽然不是其关键数据结构，但是其基本数据结构，就像去了解big table或者hbase或者hive，绕不开sstable file, hfile, rcfile，这些存储格式与其系统是匹配的，通过了解不同的存储格式并进行比较，可以学到很多数据结构的模式。