Sorted Order in a B-tree Table
In the diagram in
Structure of a B-tree Table, rows for Huber and Green are not in sorted order on the data page. This happens if Huber’s record was appended before Green’s. They both end up on the same data page, but slightly out of order. This happens in ISAM as well. However, if you tried the following retrieval, you retrieve the rows in sorted order if the employee table was a B-tree. This is because the leaf pages are used to point to the data rows, and the leaf pages maintain a sorted sequence:
select * from employee
where employee.name like 'G%';
The data on the data pages is not guaranteed to be sorted, but the access, which is always through the leaf pages, guarantees that the data is retrieved in sorted order. (This is not true for ISAM.)
Because the leaf entries are in sorted order, the maximum aggregate for a B-tree key does not require a table scan. Instead the index is read backwards.
Last modified date: 08/28/2024