Using B+ Trees For Sorting

If the table that must be sorted already has a B+ Tree index on the sort attributes, then we can use that to accelerate sorting

Retrieve tuples in desired sort order by simply traversing the leaf pages of the tree

Cases to consider: