Interval tree is a block containing an AVL tree of intervals. Each interval represents a data block, or another interval tree block at lower level. Every record in interval tree “level N” points to a block at “level N - 1”. A record in interval tree at level 1 points to a data block. An interval tree contains at least three nodes.
When the first block of file is allocated, it's a See Data block. If the free space in a data block has been exhausted, the first and the last records of the data block are moved to two newly allocated data blocks, above them there is allocated a block containing the first level of interval tree which contains three nodes corresponding to the new data block with the first record, the former data block ( the second record in the former block ) and the new data block with the last record. When an interval tree block is out of space and is at “top level”, the next level of interval tree is created and the former interval block is splited, and so on See Block/Record length. The height of interval tree grows as needed but is never reduced.
The intervals in interval tree are similar to math's intervals, the value carried by a node is the left edge of an interval, the value carried by the node's right neighbor is the right edge of interval. In each interval tree block there are two interval nodes having special semantics add-on: flags -INF and +INF.
Consider the following example : there are interval nodes 1,2,7,
thus intervals 1-1, 2-6, 7-INF. Next record to insert is 0, ?
but no interval matches record 0.
The purpose of flags is “if a record doesn't match any other interval and while traversing interval tree an interval with the flag set was hit, it belongs there i.e. to the interval with flag”.
Record R matches interval I if :