Patent ID: 8108355

Claim:
A method executed in a database system of providing an index for a table, comprising: in an initial phase of building the index, partially sorting, by a processor, the index to form a semi-sorted B-tree index, wherein the semi-sorted B-tree index is separate from the table, wherein the semi-sorted B-tree index contains an arrangement of data values of a key and associated locations in the table, wherein the key includes one or more attributes of the table, and wherein the semi-sorted B-tree index contains data values of the key that are out of order with respect to each other, the semi-sorted B-tree index having leaf nodes containing corresponding portions of the semi-sorted B-tree index, wherein at least some of the portions corresponding to the leaf nodes have key ranges that overlap; and subsequently, in response to accessing portions of the semi-sorted B-tree index to process a first database query that specifies an operation on the table, further sorting, by the processor, the accessed portions of the semi-sorted B-tree index.