Node Storage
This article describes how XML nodes and index structures are stored internally.
Node Table
XML nodes are stored in a flat table, which can be displayed with the INFO STORAGE command:
$ basex -c"CREATE DB db <xml>HiThere</xml>" -c"INFO STORAGE"
PRE DIS SIZ ATS ID NS KIND CONTENT
-----------------------------------------
0 1 3 1 0 0 DOC db.xml
1 1 2 1 1 0 ELEM xml
2 1 1 1 2 0 TEXT HiTherePRE Value
The PRE value of a node is its position in document order. It is not stored, but implied by the position in the table. It changes whenever a node with a smaller PRE value is inserted or deleted.
ID Value
Each node has a persistent ID, which remains valid after updates and is referenced by the value indexes. Initially, PRE and ID values are identical, and they stay identical as long as nodes are only appended. Once nodes are deleted or inserted elsewhere, they diverge:
$ basex -c"CREATE DB db <xml>Hi</xml>" -q"insert node <b/> before /xml" -c"INFO STORAGE"
PRE DIS SIZ ATS ID NS KIND CONTENT
-----------------------------------------
0 1 4 1 0 0 DOC db.xml
1 1 1 1 3 0 ELEM b
2 2 2 1 1 0 ELEM xml
3 1 1 1 2 0 TEXT Hidb:node-pre and db:node-id return the PRE and ID value of a node, and db:get-pre and db:get-id return the node for a value. ID lookups are fast if UPDINDEX is enabled (the default), as an ID-PRE mapping is maintained. Otherwise, they are expensive.
ID-PRE Mapping
Updated: The ID-PRE mapping is persisted incrementally.
The mapping has no entry per node. Instead, it records the structural updates:
- Each insertion or deletion adds an entry with its PRE value, the range of inserted IDs, and the resulting shift of the following PRE values.
- IDs assigned at creation or optimization (base IDs) are resolved by adding the shift of the last preceding update. Inserted IDs are found by a binary search in the inserted ranges.
- Deleted base IDs are stored as sorted ranges.
Its size thus depends on the number of updates, not on the size of the database. OPTIMIZE ALL assigns new IDs and resets it.
The mapping is stored in idp.basex. Each commit appends its operations to a log (idpl.basex), whose committed length is recorded in the metadata: incomplete appends are ignored when the database is reopened. The mapping is only rewritten completely when the database is closed or when the log would exceed it. A commit therefore costs the same, no matter how large the mapping is.
Namespaces
Updated: Namespaces are stored in a compact format.
The NS column references the namespace URI of a name. Elements with namespace declarations are flagged in the table, and INFO STORAGE marks them with a +. The declarations themselves are stored separately and listed after the table:
$ basex -c"CREATE DB db <xml><b xmlns:a='urn:a'/>Hi</xml>" -c"INFO STORAGE"
PRE DIS SIZ ATS ID NS KIND CONTENT
-----------------------------------------
0 1 4 1 0 0 DOC db.xml
1 1 3 1 1 0 ELEM xml
2 1 1 1 2 +0 ELEM b
3 2 1 1 3 0 TEXT Hi
NS PRE DIS PREF URI
-------------------------
1 2 3 a urn:a
Pre[2] xmlns:a="urn:a"Prefixes and URIs are stored in two dictionaries. The declarations form a tree that mirrors the declaring elements, and it is stored in a compact format:
- Sets: Each distinct set of prefix/URI pairs is stored once and referenced by an ID. As documents tend to repeat the same declarations, most databases have only a few sets.
- Inner nodes: Declaring elements with declaring descendants are kept in main memory, with their PRE values, set IDs and parents. They are needed to determine the namespaces in scope.
- Leaves: All other declaring elements are grouped by parent and stored in
nsp.basex, which is read on demand. Entries are delta-encoded and usually take one byte: 4 bits for the PRE distance to the previous entry (up to 15) and 4 bits for the set ID (below 15). Larger values are appended as compressed numbers. - Blocks: Delta-encoded entries can only be decoded from the start. Groups are therefore split into blocks of 256 entries, whose first PRE value and file offset are kept with the inner nodes. Any entry can be found by reading a single block.
Opening a database only reads the dictionaries, sets and inner nodes. The first update of namespaces expands the structure into a mutable tree, which is compressed again when the database is written. Structures with up to 4096 nodes are written in the old format, so older versions of BaseX can still open the database.
Block Storage
The node table is divided into blocks of 4 KB, each with up to 256 records of 16 bytes. Within a block, records are sorted by PRE value, so the PRE value need not be stored. A block directory stores the first PRE value of each block; it is kept in main memory and only written to disk when required. A bitmap marks free blocks, which are reused for new data. In a database that has never been updated, all blocks are full and in order, and the directory is only created with the first update.
Updated: Parallel reading, read-ahead.
Read-only queries access the table with separate readers: up to 16 readers, each with its own buffers and file position, are assigned to threads, so concurrent reads are not serialized. Updates use a single reader with write access. If a reader requests the block after the previous one, it doubles the number of blocks read at once, up to 8.
Index Structures
All files of a database are located in its directory and have the suffix .basex:
| File | Contents |
|---|---|
inf |
Metadata, element and attribute names, path index, namespaces (except for the leaves), resource index |
tbl, tbli |
Node table and block directory |
txt, atv |
Strings of text nodes and attribute values |
nsp |
Leaves of the namespace structure |
idp, idpl |
ID-PRE mapping and its log |
txt…, atv…, tok… |
Text, attribute and token index |
ftx…, swl |
Full-text index and stop words |
inf and the ID-PRE mapping are read completely when a database is opened. All other files are accessed on demand.
Value Indexes
The text, attribute and token indexes have the same structure:
…l: For each key, a sorted list of node IDs (PRE values ifUPDINDEXis disabled), delta-encoded as compressed numbers.…r: Offsets of the lists, sorted by key, for binary search.
Keys are not stored. They are read from the strings of the first node of a list (the anchor).
Full-Text Index
The full-text index consists of three files:
ftxx: For each token length, the offset of the first token with this length.ftxy: Tokens, sorted by length and alphabetically, with the offset and number of their references. A fuzzy search only scans tokens of similar length.ftxz: Node references and token positions, as compressed numbers.
Updatable Indexes
Updated: Updatable value indexes are stored in segments.
With UPDINDEX, the value indexes consist of immutable segments, oldest first, and a buffer in main memory:
- Base: The index built at creation or optimization keeps the layout described above, which older versions can read. If an anchor is deleted or changed, its key is pinned in
txtp,atvportokp. - Segments: Newer segments are stored in numbered files (e.g.
txt1l,txt1r,ftx2x). They reference node IDs, and value index segments store their keys. - Buffer: Changes are collected in a buffer, logged in
txtb,atvb,tokborftxb. Beyond 100,000 references, it is written as a new segment. - Supersede sets: A segment may have a
…sfile with the IDs of the nodes it re-indexes. References in older segments to these nodes are outdated: they are skipped on access, not removed. A reference is valid if its node exists and no newer segment supersedes it. - Merges: If there are more than 8 segments, all segments not larger than an eighth of the total size are merged, and outdated references are dropped.
OPTIMIZEmerges all segments into one.
Index updates are applied once per transaction, at commit time. When a database with up to 100,000 nodes is closed, its indexes are rewritten in the base layout.
Changelog
Version 13.0- Updated: Updatable Indexes: Segmented layout of the value indexes, including the full-text index.
- Updated: Compact storage of namespaces, incremental persistence of the ID-PRE mapping, parallel reading of the node table.