Method, system, and program for reverse index scanning

A system for performing a reverse scan of an index implemented as a tree of pages, wherein each leaf page includes one or more ordered index keys and previous and next pointers to the previous and next pages, respectively, and wherein the scan is searching for keys in the leaf pages that satisfy the search criteria, comprising:

• means for requesting a conditional shared latch on a previous page prior to the current page if a current index key is a first key on a current page;
• means for releasing the latch on the current page and requesting unconditional latches on the previous page and the current page if the requested conditional shared latch is not granted;
• means for determining whether the current index key is on the current page after receiving the latch on the previous and current pages in response to requesting the unconditional latches and if the current page was modified since the unconditional latch was requested;
• means for locating the current index key on the current page if the current index key is on the current page;
• and
• means for determining whether the located current index key satisfies the search criteria.

A program for performing a reverse scan of an index implemented as a tree of pages, wherein each leaf page includes one or more ordered index keys and previous and next pointers to the previous and next pages, respectively, wherein the scan is searching for keys in the leaf pages that satisfy the search criteria, wherein the program comprises code implemented in a computer readable medium, wherein the program code is capable of causing a processor to perform:

• if a current index key is a first key on a current page, then requesting a conditional shared latch on a previous page prior to the current page;
• if the requested conditional shared latch is not granted, then releasing the latch on the current page and requesting unconditional latches on the previous page and the current page;
• after receiving the latch on the previous and current pages in response to requesting the unconditional latches, then determining whether the current index key is on the current page if the current page was modified since the unconditional latch was requested;
• locating the current index key on the current page if the current index key is on the current page;
• and
• determining whether the located current index key satisfies the search criteria.