The structure of the Reiser file system
Given a key n (whose position in the block is 24 + n * 16 bytes) and a total number of k keys in the block, the left pointer that corresponds to key n can be found at byte 24 + k * 16 + n * 8. The free space starts at byte blocksize - free space, where free space is the value from the block header.
Example:
00000000 02 00 a0 00 e0 00 00 00 00 00 00 00 00 00 00 00 .. .à...........
00000010 00 00 00 00 00 00 00 00 02 00 00 00 0e 00 00 00 ................
00000020 00 00 00 00 00 00 00 00 03 00 00 00 04 00 00 00 ................
00000030 01 00 00 00 f4 01 00 00 03 00 00 00 9e 04 00 00 ....ô...........
00000040 00 00 00 00 00 00 00 00 04 00 00 00 05 00 00 00 ................
...
00000a10 01 10 00 00 00 00 00 20 e0 20 00 00 04 0b b4 cc ....... à ....´Ì
00000a20 03 21 00 00 94 0d 54 c5 0b 21 00 00 e0 0f 2f c5 .!....TÅ.!..à./Å
00000a30 5e 23 00 00 b4 0f f4 ff 60 23 00 00 38 07 a9 ff ^#..´.ôÿ`#..8.©ÿ
...
Level: 2
Nr. items: 160
Free space: 224 bytes
Key 0: {2, 14, 0, 0}
Key 1: {3, 4, 1, 500}
Key 2: {3, 1182, 0, 0}
...
Ptr 0: {8416, 2820}
Ptr 1: {8451, 3479}
Ptr 2: {8459, 4064}
Ptr 3: {9054, 4020}
...
This example shows parts of block 8482, which is also depicted in the diagram describing the S+-tree above. Key 0 starts at byte 24 (0x18), and since there are 160 items in the block, Ptr 0 starts at byte 2584 (0xa18). Note that the reserved parts of the pointers actually contain junk data. The free space starts at byte 3872 (0xf20) and it may also contain junk data.
Leaf nodes Leaf nodes are found at the lowest level of the S+-tree. Except for indirect items all the data is contained within the leaf nodes. Leaf nodes are made up of the block header, item headers, and items:
Note that the free space in the block is located between the last item header and item, and that items are in reverse order. This way, new item headers and items can simply be added without having to rearrange existing items. New headers go after the last header, and new items before the first on-disk item. Also note that items are of variable length.
Item Headers The item header describes the item it refers to. It contains the key for the item as well as the item's location and size within the leaf node. The type of the item is determined by its key.
| Name |
Size |
Description |
| Key |
16 |
The key that belongs to the item |
| Count |
2 |
The free space in the last unformatted node for an indirect item if this is an indirect item
0xffff for stat and direct items
the number of directory entries for a directory item |
| Length |
2 |
total size of the item |
| Location |
2 |
offset to the item body within the block |
| Version |
2 |
0 for all old items (keys), 1 for new ones | Note that the comments in the structure definition indicate that new items have a version of 2. However, the KEY_FORMAT_3_6 constant is defined as 1 and this is used to set the version.
Example:
The following is the item header for the stat item described by key {2, 14, 0, 0}, which was used earlier as an example of type 2 (version 3.6). It shows that the version is indeed the new version, even though the heuristic above would indicate an old key.
|
