SQL/MX 3.2.1 Management Manual (H06.26+, J06.15+)

Figure 1 Key-Sequenced B-Tree Structure
Each data block contains a header plus one or more data records, depending on the record size
and data-block size. For each data block, an entry in an index block contains the value of the key
field for the first record in the data block and the address of that data block.
The position of a new record inserted into a key-sequenced file is determined by the value of its
clustering key field. If the data block is determined to be full when NonStop SQL/MX attempts to
insert a new record into it, a block split occurs: the disk process allocates a new data block, moves
part of the data from the old block into the new block if not at the end of the file, and gives the
index block a pointer to the new data block.
Key-sequenced files are also used to store indexes. When an index block fills up, it is split in a
similar manner: a new index block is allocated, and some of the pointers are moved from the old
index block to the new one. The first time a split occurs in a file, the disk process must generate a
new level of indexes. The disk process does this by allocating a higher-level index block containing
the low key and a pointer to the two or more lower-level index blocks, which in turn point to many
data blocks. The disk process must do this again each time the highest-level block is split.
The disk process can perform a three-way block split, when appropriate, creating two new blocks
and distributing the original block’s data and pointers plus the new record or pointer among all
three.
In a key-sequenced file, data blocks are chained together with forward and backward pointers
stored in the header of each block. Data records within each block are stored in key-value sequence.
This storage arrangement enhances the sequential performance for tables stored in key-sequenced
files. Index blocks, however, are not chained.
The Key-Sequenced File Structure 33