Concurrent processing controlling method and apparatus on B+ tree structure

Claim 1

A concurrency control method for a plurality of processes on a B + tree structure using a supervised program in a computer system, in which the B + tree structure has: (1) one root; (2) a plurality of nodes, each of nodes being coupled to at least one descendant adjacent node and having at least one key and associated pointer for designating one of descendant adjacent nodes; (3) a plurality of leaves, each of the leaves connected to adjacent leaves through dual direction transverse links, each of the leaves having another pointer for designating one of the adjacent leaves; (4) first locks used in respective processes for preventing a node's content from being changed by another process; and (5) second locks used in respective processes for prohibiting said respective processes from referring said another pointer of a leaf to prevent one leaf from being accessed through a transverse link in another process; the method comprising the steps of: (a) placing one of the first locks on a node in each of the processes to be concurrently controlled, in order to ensure the content of the node for each of the processes; (b) selecting one of descendant adjacent nodes according to the pointer of the node by comparing said at least one key of the node with a given key in each of the processes; (c) when the selected descendent adjacent node is not one of the leaves, placing another first lock on the selected descendant adjacent node and releasing the node from the one of the first locks; (d) repeating steps (b) and (c) in order that an access of each of the processes descends in a direction from a root toward a leaf on the tree and until a leaf to be updated is selected in the step (b); (e) holding the second locks in the one of the processes on the adjacent leaves located adjacent the one leaf, in order to prohibit another concurrent process from referring the another pointer of one of the adjacent leaves; and (f) placing a first lock on the one leaf to ensure the content of the one leaf.