Patent ID: 8843472

Claim:
A method, in a data processing system, for efficiently searching a database for data associated with a key value that is unidentifiable in a set of nodes of the database, the method comprising: receiving a request to retrieve data from the database, wherein the request specifies a searched-for key value; identifying the data associated with the searched-for key value in a lowest level node of the database between a current leftmost node and a current rightmost node, wherein identifying the data associated with the searched-for key value in the lowest level node of the database comprises: navigating to a current page of the database; applying logic to determine a biggest key value in a sub-page lowest level node resulting in a resulted key value; responsive to receiving the resulted key value, determining whether the resulted key value is bigger than the searched-for key value; responsive to the resulted key value being bigger than the searched-for key value, marking a current node as the current rightmost node; determining whether there is a set of nodes existing between the current leftmost node and the current rightmost node; responsive to the set of nodes existing between the current leftmost node and the current rightmost node, navigating to a n/2 node in the current page; re-applying the logic to determine a biggest key value in a different sub-page lowest level node; responsive to no other node existing between the current leftmost node and the current rightmost node, determining whether the current node has any child nodes; responsive to the current node failing to have any child nodes, recognizing the current node as comprising the searched-for key value; updating the key index in the current node of the database with the key index value identified from the sub-page lowest level node thereby making the searched-for key value identifiable within the current node; and returning the data associated with the searched-for key value; updating a key index in at least one node of the database with the key index value associated with the data and identified from the lowest level node thereby making the searched-for key value identifiable within the at least one node; and returning the data associated with the searched-for key value to a user.