微软复合文档格式 (Compound Document)

今天看到一个FastExcel的开源项目，它能够使用纯Java代码读取Excel文件的文本内容以及写入内容保存为Excel文件。这项目的作者应该是一个中国人，因为项目源代码中包含的JUnit测试代码里居然有中文数据。把项目的源代码导入到Eclipse编译，运行了附带的测试用例。源代码里的package开头是edu.npu。baidu一下，npu好像是西北工业大学。作者在项目的简介里介绍了代码的工作原理是依照Excel的文件格式，直接进行读取。而Excel的文件格式是基于复合文档(Compound Document)的。项目主页上有链接给出复合文档格式和Excel文件格式，都是OpenOffice社区整理的。
复合文档简单的说就是在一个文件里可以内嵌其他各种文档，这些内嵌的文档还具有目录结构，可以说复合文档格式就是在一个文件里面实现一个文件系统。从逻辑上说复合文档包含Storage和Stream。Storge相当于我们熟知的操作系统文件系统里的目录，Stream相当于文件。下图就是复合文档的逻辑示意图。和操作系统的文件系统类似，同一个Storge下的Stream不可以重名，不同Storage下的则可以。

其实这个图的内容，很久之前我就了解了，而且很好理解。当初看MFC书籍讲复合文档的时候就在这个层次上。自己也没深究过要实现这样的逻辑结构，物理上该如何存储。今天特地阅读了这个文档格式，25页，不是很长，边阅读边查看一个Excel文件的物理存储结构，这样更好理解。
物理结构图：

开始是一个文件头（Header），固定长度512字节。然后是一个接一个的扇区（Sector），大小是可变的，一般是512字节。这里的Sector可以类比为磁盘上的扇区，反正就是一块文件空间。一个复合文档，除了文件头就是扇区。因此复合文档的内容数据主要是存放在扇区里的。此外有些扇区得用来存储一些元数据，描述扇区和扇区之间的关系，哪些扇区是用来干嘛的，那几个扇区组成一个Stream。每个扇区有一个标识符，也就是编号，从0开始，依次递增。扇区的编号用有符号的4字节整数来表示，这样在内部就可以引用了。扇区号可以是负数，几个负扇区号的特殊含义是:

就像磁盘文件系统，一个文件有多个块组成，在复合文档里，一个Stream也是由多个Sector组成。那么多个Sector的顺序是怎么样的？一个Stream到底有几个Sector组成呢？这是通过Sector Allocation Table（SAT）来实现的。SAT顾名思义就是跟踪Sector的分配情况。SAT也得需要空间来存储啊！当然也是存储在Sector里的。可以说SAT也是一种特殊的Stream，它描述一个Stream拥有哪些Sector。那么谁描述它自己拥有哪些Sector呢？是MSAT，Master Sector Allocation Table。MSAT描述了哪些Sector是被SAT占用的。那谁描述MSAT存放在哪些Sector？好像无休止了！MSAT是存放在Header里的。这下摆脱溯源的烦恼了。但是Header大小是固定512字节的，因此能存的信息是有限制的。如果SAT占用的Sector很多很多，Header里都描述不下，怎么办？还是有办法的，扩展！当Header里的空间不够用时，就用Sector，在Header里有字段记录哪个Sector是MSAT扩展空间的第一个扇区，在MSAT专用的扇区里的最后4字节给出下一个MSAT专用的Sector，这样一个链表就现成了。因此一个MSAT扇区最多可以记录(512-4)/4=127个AST扇区。

通过MSAT就可以找出所有被SAT占用的Sector。这些SAT的Sector就描述了哪个几个Sector是属于一个Stream的以及Sector之间的顺序。这似乎又需要一个链表。对的。这次的链表结构是这样的：



把SAT看做一个数组，数组的元素就是扇区编号，扇区编号用4个字节来存储。比如SAT[i] = j，表示SAT数组的第i个元素是扇区编号j。如果把数组索引就当做扇区编号，SAT[i] = j，SAT[j] = k ... SAT[x] = -2，那么就有一串扇区编号了，i -> j -> k ...-> -2，扇区号-2表示串的结尾。这样，Stream就可以用这么一串扇区序列来描述的，关键是能有一个元数据描述这个Stream，并记录这个Stream的起始扇区号。知道了起始扇区号，就可以通过SAT找到所有其他Sector了。可见SAT也是一个链表结构。好像学数据结构的时候学过这种结构，具体叫啥忘记了。
那怎么存储Stream元数据呢？毫无疑问，是存放在Sector里。SAT就是存储了一些扇号串，看不出哪一串是用来描述Stream的元数据的。于是复合文档就有另一个概念了，目录（Directory）。Directory包含一个描述Stream和Storge的元数据的数据结构。如下图所示，目录里面有目录项，目录项也有编号，从0开始。
每个目录项就描述该项是Stream还是Storge，或者其他。如果是Stream，那么就记录起始扇区号是多少，如果是Storge，包含记录它有哪些Storge和Stream。一个Storge下可能有很多个Storge和Stream。复合文档是把这些子Stream和Storge组成一棵红黑树。这样Storge就可以只记录这颗红黑树的根节点就达到记录所有子Storge和Stream的目的。当然每个目录项得有字段里维护这么一颗红黑树。显然这种方式下，一个Stream或Storge只能在一棵红黑树里。为啥使用红黑树，有什么优点？慢慢思考中！
此外，复合文档还有其他一些概念，比如Short-Stream。Short-Stream一般存储在Root Storge这个目录项里。