How does BSON store the array in {"a": 1, "b": [true]}, with 1 as an int32, and how many bytes does the document take?
answer
- arrays have no layout of their own
- keys are decimal strings from zero
- two terminators in a row
- add it up: 4, 7, 12, 1
basics
~20 sBSON stores [true] as an embedded document with key "0" under type byte 0x04, taking 9 bytes. With 1 as an int32, the whole document {"a": 1, "b": [true]} is 24 bytes, so its length prefix is 0x18.
solid answer
~40 sBSON has no array layout of its own: an array is a document whose keys are the decimal strings `"0"`, `"1"`, `"2"`, stored under type byte `0x04` instead of `0x03`. So `[true]` is `09 00 00 00 08 30 00 01 00`: a 4-byte length, the boolean element (type, `"0"`, NUL, value) and a terminator, 9 bytes. The whole document adds up to 24: 4 for the root length, 7 for `a` (type, name, NUL, 4-byte `int32`), 12 for `b` (type, name, NUL, then the 9-byte array) and 1 for the root terminator. The prefix is `18 00 00 00`. The price is that every array element carries a key, and those keys get wider as the index grows.
code
plaintext · 8 lines31 00 00 00
04 42 53 4F 4E 00
26 00 00 00
02 30 00 08 00 00 00 61 77 65 73 6F 6D 65 00
01 31 00 33 33 33 33 33 33 14 40
10 32 00 C2 07 00 00
00
00go deeper
Remember that a BSON array is a document with keys "0", "1", "2", and that only the type byte in the parent says it is an array.
Write out the bytes and recount them aloud: root length, each element's type, name and value, then both terminators. The two final zero bytes are where most counts go wrong.
Show the cost in numbers: key width grows with the index, so large arrays spend many bytes on structure. Distinguish degenerate array keys, which still parse, from a wrong length, which breaks the frame.
The angle worth raising is that a large embedded array pays key bytes on every element and gets no random access. That is a fact to weigh when a team models data as long arrays.
## An array is a document The BSON specification gives arrays no byte layout of their own. Its grammar reads `signed_byte(4) e_name document`, and its notes define an array as a BSON document with integer values for the keys, starting at 0 and continuing sequentially. The example it gives is `['red', 'blue']`, encoded as the document `{'0': 'red', '1': 'blue'}`. Two things follow from that: - The **body** of an array is byte-for-byte what an embedded document with those keys would be. - The only signal that it is an array is the **type byte in the parent element**: `0x04` rather than `0x03`. ## The document, byte by byte Take `{"a": 1, "b": [true]}` with `1` written as an `int32`: ```plaintext offset bytes meaning 0x00 18 00 00 00 root document length: 24 0x04 10 type: int32 0x05 61 00 e_name "a" and its NUL 0x07 01 00 00 00 value: 1 0x0B 04 type: array 0x0C 62 00 e_name "b" and its NUL 0x0E 09 00 00 00 array document length: 9 0x12 08 type: boolean 0x13 30 00 e_name "0" and its NUL 0x15 01 value: true 0x16 00 array document terminator 0x17 00 root document terminator ``` ## Recounting it Every stated size should add up from the layout: 1. The **array document**: 4 (length) + 4 (type, `"0"`, NUL, value) + 1 (terminator) = **9**, which is the value at offset `0x0E`. 2. The **element `a`**: 1 (type) + 2 (name and NUL) + 4 (`int32`) = **7**. 3. The **element `b`**: 1 (type) + 2 (name and NUL) + 9 (array document) = **12**. 4. The **root**: 4 + 7 + 12 + 1 = **24**, or `0x18`, the value at offset `0x00`. The last two bytes are both `0x00`, and they are different things. The first ends the array, and the second ends the root. The array's 9 counts its own terminator and not the root's. Dropping either byte is an easy off-by-one in a hand count. The number also depends on the value's type. Written as a `double`, the `1` takes 8 value bytes, so `a` becomes 11 bytes and the root becomes 28, or `0x1C`. ## What the keys cost Because an array is a document, each element pays for a type byte and a key, and a key's width grows with the index: | Index range | Key bytes, NUL included | |---|---| | 0 to 9 | 2 | | 10 to 99 | 3 | | 100 to 999 | 4 | Work it for an array of 1,000 `int32` values: - Key bytes: 10 x 2 + 90 x 3 + 900 x 4 = 3,890. - Type bytes: 1,000. - Value bytes: 1,000 x 4 = 4,000. - The array's own document: 4 + 3,890 + 1,000 + 4,000 + 1 = **8,895 bytes**. More than half of those bytes are structure rather than data. Going from 10 to 11 elements adds 8 bytes, not 4 or 7: 1 type byte, 3 key bytes (`"10"` and its NUL), 4 value bytes. ## What it does not give you Numeric keys do not make an array randomly addressable. Elements are still walked in order, because the format has no offset table and elements in one array may have different widths. Having the index in the key tells a reader which element it is standing on, and not where element 500 begins. ## When the keys are wrong The specification says the keys start at 0 and continue sequentially. The BSON corpus test vectors treat a violation as **degenerate BSON**: invalid but still parseable. They list an array whose single key is an empty string, one whose key is `"ab"`, and one with duplicate `"0"` keys, each with the correctly renumbered canonical form beside it. So a reader may well accept wrong keys, and that says nothing about whether they are valid. A bad length is different. The same vectors list an array length that is one too long or one too short as a decode error, because it breaks the frame rather than a convention. ## Practical reading habit When you read an array in a hex dump, look at the parent element's type byte first. From the array's length onward, the bytes read exactly as any other document. An empty array is `05 00 00 00 00`, the same five bytes as an empty document.
- What is the total if the array in that BSON document is empty, as in {"a": 1, "b": []}?An empty array is a 5-byte document: 05 00 00 00 00. Element b becomes 1 + 2 + 5 = 8 bytes. The root is 4 + 7 + 8 + 1 = 20 bytes, so its prefix is 0x14.
- A BSON array has keys "0" and "0" instead of "0" and "1". Is that a decode failure?The BSON corpus test vectors class it as degenerate rather than a decode error: invalid against the specification but still parseable. Their canonical form renumbers the keys. A reader accepting it does not make it valid BSON.
- A BSON array stores an element count and then bare values.
- Array keys are implied by position, so they take no bytes.
- The array and the root share one trailing zero byte.
- Every BSON array key costs a fixed two bytes, whatever the index.
- A BSON array's body has a different layout from an embedded document's.
- Numeric keys let a reader jump straight to any array index.