# HDF5 specs unclear: B-tree v2 and fractal heap **URL:** \ **Category:** HDF5 Library\ **Created:** [July 12, 2021, 1:12pm UTC](https://forum.hdfgroup.org/t/hdf5-specs-unclear-b-tree-v2-and-fractal-heap/8723 "2021-07-12T13:12:03Z")\ **Posts on this page:** 9\ **Page:** 1
**Author:** ![wout.de\_nolf](https://forum.hdfgroup.org/letter_avatar_proxy/v4/letter/w/3bc359/32.png) [@wout.de\_nolf](https://forum.hdfgroup.org/u/wout.de_nolf)\ **Post date:** [July 12, 2021, 1:12pm UTC](https://forum.hdfgroup.org/t/hdf5-specs-unclear-b-tree-v2-and-fractal-heap/8723/1 "2021-07-12T13:12:03Z")
I’m working on covering more parts of the HDF5 specification in the pure python reader [https://github.com/jjhelmus/pyfive](https://github.com/jjhelmus/pyfive) (which we plan to use for recovering data from corrupt files). Files that store groups while tracking the order (indexed groups) use a b-tree v2 with fractal heap. The specs are unclear about what a “heap ID” is (or at least I don’t get it): ```auto Version 2 B-tree, Type 5 Record Layout - Link Name for Indexed Group ID | This is a 7-byte sequence of bytes and is the heap ID for the link record in the group’s fractal heap. ``` Then when looking at the fractal heap ```auto Fields: Fractal Heap Direct Block Object Data | This section of the direct block stores the actual data for objects in the heap. The size of this section is determined by the direct block’s size minus the size of the other fields stored in the direct block (for example, the Signature, Version, and others including the Checksum if it is present). ``` How is the “heap ID” from the b-tree record related to the direct block data of the fractal heap? How do I know which direct block it is and what the offset+size is of the data in the block’s data? As a more general question about fractal heaps: how is the “object data” from a direct block structured? Can data be extracted from this binary blob without knowing anything else? ---
**Author:** ![nfortne2](https://forum.hdfgroup.org/user_avatar/forum.hdfgroup.org/nfortne2/32/1543_2.png) [@nfortne2](https://forum.hdfgroup.org/u/nfortne2)\ **Post date:** [July 12, 2021, 7:23pm UTC](https://forum.hdfgroup.org/t/hdf5-specs-unclear-b-tree-v2-and-fractal-heap/8723/2 "2021-07-12T19:23:35Z")
The definition of the fractal heap ID can be found in the file format document after the definition of the fractal heap indirect block. As an overview, the ID can refer to a “tiny”, “huge”, or “managed” object. If it’s tiny, the ID contains the actual data and the heap itself does not need to be read from. If it’s huge, the ID contains the address on disk of the data or a b-tree key that can be used to find this address. If it’s managed, then it contains the offset and length within the virtual fractal heap address space (i.e. inside a direct block, possibly indexed by one or more indirect blocks). You can compute which direct and indirect blocks contains the data, and the offset within the direct block mathematically using the various parameters and algorithms described at the start of the fractal heap section - it describes an array of blocks of increasing size within a linear address space. I hope that also answers your question about the data structure in general. It should be possible to extract data from a fractal heap using only a heap ID (and the sizeof offsets and sizeof lengths). Without a heap ID you could still walk through the heap and reconstruct a linear blob of bytes for managed data that information could potentially be extracted from, and individual huge objects could be pulled from the huge object b-tree if huge objects are indirectly accessed. Tiny objects and directly accessed huge objects would be lost though. The fractal heap stuff is a bit dense so let me know if you have further questions. ---
**Author:** ![wout.de\_nolf](https://forum.hdfgroup.org/letter_avatar_proxy/v4/letter/w/3bc359/32.png) [@wout.de\_nolf](https://forum.hdfgroup.org/u/wout.de_nolf)\ **Post date:** [July 12, 2021, 7:35pm UTC](https://forum.hdfgroup.org/t/hdf5-specs-unclear-b-tree-v2-and-fractal-heap/8723/3 "2021-07-12T19:35:57Z")
So if I understand (correct me if I’m wrong): 1. The “heap ID” from the records in a B-tree v2 are actually the tiny, huge or managed heap ID’s from _III.G. Disk Format: Level 1G - Fractal Heap_. The mixing of words “object ID” and “heap ID” got me confused. I thought the fractal heap was a store for object ID’s. So I was totally on the wrong track. 2. If you concatenate all direct blocks from a fractal heap (including their header) then the offset in the heap ID of a manage object is the offset in this concatenate sequence (virtual linear address space). 3. The data referenced by a heap ID from Type 5 and Type 6 B-tree v2 records is actually a link message (_IV.A.2.g. The Link Message_). So “objects” are actually “messages”. None of these things were clear to me after reading the specs. Maybe it was just me or maybe this can help you improve the specs. Thanks for your fast reply @nfortne2! ---
**Author:** ![nfortne2](https://forum.hdfgroup.org/user_avatar/forum.hdfgroup.org/nfortne2/32/1543_2.png) [@nfortne2](https://forum.hdfgroup.org/u/nfortne2)\ **Post date:** [July 13, 2021, 12:58pm UTC](https://forum.hdfgroup.org/t/hdf5-specs-unclear-b-tree-v2-and-fractal-heap/8723/4 "2021-07-13T12:58:32Z")
1. Correct 2. Correct. I’m not certain if all direct blocks are always allocated in order or not (if not there may be unallocated blocks you would have to fill in with zeroes), if it’s important I can look at the code and figure it out. 3. Correct in the case of the fractal heap used to store link messages. Fractal heaps are used for other things which is why the fractal heap file format spec references uses the term “objects”. A “heap” in HDF5 is just a bucket for storing opaque packets of bytes, having no knowledge of their contents. There are certainly places where the wording could be clearer. We’ll take your feedback into account when we get a chance to work on the spec. Thanks! ---
**Author:** ![wout.de\_nolf](https://forum.hdfgroup.org/letter_avatar_proxy/v4/letter/w/3bc359/32.png) [@wout.de\_nolf](https://forum.hdfgroup.org/u/wout.de_nolf)\ **Post date:** [July 13, 2021, 1:08pm UTC](https://forum.hdfgroup.org/t/hdf5-specs-unclear-b-tree-v2-and-fractal-heap/8723/5 "2021-07-13T13:08:42Z")
1. Yes it is important as I’m currently assuming that the offset in the “heap ID” is the offset in the concatenated sequence of direct blocks (including headers) in the order I get them from the indirect block(s). ---
**Author:** ![nfortne2](https://forum.hdfgroup.org/user_avatar/forum.hdfgroup.org/nfortne2/32/1543_2.png) [@nfortne2](https://forum.hdfgroup.org/u/nfortne2)\ **Post date:** [July 13, 2021, 2:51pm UTC](https://forum.hdfgroup.org/t/hdf5-specs-unclear-b-tree-v2-and-fractal-heap/8723/6 "2021-07-13T14:51:24Z")
That shouldn’t affect things as you can assume the unallocated direct blocks take up as much space as they would if they were alocated. If you’re actually building up the serialized heap in memory you can just allocate enough space to include them. You shouldn’t even need to clear these sections because heap IDs should never point to unallocated blocks. ---
**Author:** ![nfortne2](https://forum.hdfgroup.org/user_avatar/forum.hdfgroup.org/nfortne2/32/1543_2.png) [@nfortne2](https://forum.hdfgroup.org/u/nfortne2)\ **Post date:** [July 13, 2021, 2:54pm UTC](https://forum.hdfgroup.org/t/hdf5-specs-unclear-b-tree-v2-and-fractal-heap/8723/7 "2021-07-13T14:54:19Z")
An unallocated direct block, if it is possible, would be represented by HADDR\_UNDEF in the parent indirect block’s “Child Direct Block Address” field. ---
**Author:** ![wout.de\_nolf](https://forum.hdfgroup.org/letter_avatar_proxy/v4/letter/w/3bc359/32.png) [@wout.de\_nolf](https://forum.hdfgroup.org/u/wout.de_nolf)\ **Post date:** [July 13, 2021, 4:01pm UTC](https://forum.hdfgroup.org/t/hdf5-specs-unclear-b-tree-v2-and-fractal-heap/8723/8 "2021-07-13T16:01:04Z")
Ok that should answer all my questions. Thanks again @nfortne2! ---
**Author:** ![brian.maranville](https://forum.hdfgroup.org/letter_avatar_proxy/v4/letter/b/a698b9/32.png) [@brian.maranville](https://forum.hdfgroup.org/u/brian.maranville)\ **Post date:** [July 19, 2021, 9:27am UTC](https://forum.hdfgroup.org/t/hdf5-specs-unclear-b-tree-v2-and-fractal-heap/8723/9 "2021-07-19T09:27:18Z")
Will data ever span direct blocks? I’m wondering if I would need to stitch together the virtual linear address space, or if I just need to be able to index an offset within it (which is easier)?