System and methods involving a data structure searchable with O(logN) performance

摘要

One embodiment of the invention involves a data structure that is stored on a computer-readable medium comprising a sorted portion that contains a plurality of entries that are sorted into an order, an unsorted portion that contains a plurality of entries that have not been sorted, and a boundary that separates the sorted portion and the unsorted portion. The sorted portion of the data structure may be searched with O(logN) performance while an entry is added to the unsorted portion.