Methods, systems, and apparatus, including encoded computer programs, for using free space set aside in hierarchical data documents, such as multimedia documents containing video and audio data. In one aspect, a method includes obtaining new data to be added to a document having a hierarchical structure, where the document includes stored data and free spaces at different nodes; determining whether a first node in the structure includes a first free space of a size sufficient for the new data; using the first free space in the first node to add the new data to the document when the size is sufficient; and when the size is insufficient: identifying a second node including a second free space in the structure, moving some of the second free space to the first free space, and using the increased first free space in the first node to add the new data to the document.