Next: The Large Stores, Up: The B-trees [Contents][Index]
Nodes have a fixed size navigational part and a variable size keys and data part. The first is organized in a fixed number of slots of fixed size, of which half are always used. It is the node internal index, organized as a critical bit tree (i.e. blind binary trie).
For their variable storage part, nonblonde b-tree nodes have a variable total size, both on disk and in memory.
User keys and data reside only in the external nodes – the nodes on the lowest level of the tree.
Internal nodes store no user data. They are less frequently modified than the external nodes and for the same navigational part size, they may be smaller than the former. The keys they carry are derived from the user stored keys, without necessarily matching any of the latter.
Prefix stripping is applied for external nodes, i.e. the leading, common part of the node stored keys is removed.
For each table, the navigational part size of the two node classes is set independently. It is a power of two, in the 2^8 2^19 range.
A key slot takes 16 bytes in the b-tree node navigational part, thus the number of keys a node may store is its navigational part size divided by 16.
Large and very large node sizes favor certain operations and access patterns and hurt others. Large sizes suit better the internal nodes, as they are infrequently modified and their key associated data (addresses of lower levels nodes) is small in size. Large internal node sizes decrease tree heights and may help keep the internal nodes in cache longer.
See Performance.
The navigational part of nodes may be stored on disk in a compacted form or may be not stored at all.
Next: The Large Stores, Up: The B-trees [Contents][Index]