In computer science, a sorted elastic array (SEA) is a data structure where data items are sorted and stored with open spaces between them. It is contrary to the concept of sparse array where the density of data items in the array is low (much less than 100%). SEA with data density of around 75% (meaning 75% of the array cells have data items) works well in terms of inserting data in the SEA array. If the density is too high (close to 100%), then too many shift operations are needed to insert a new data element. If the density is too low, then too much storage is wasted. When the SEA array needs to grow, it is resized to a larger array with more data cells. At the same time, data elements in the old SEA are dispersed into the new SEA array. The dispersion operation happens at the same time as the array resizing operation, and guarantees open spaces between data elements in the new SEA array. If the SEA is in memory, binary search is performed to find the location of an element to be inserted or searched. If the SEA is stored in a block-based storage medium, a block index is used to locate an element. The advantage of SEA is excellent data locality allowing optimal read-ahead, caching, and almost sequential read and write speed. Compared to , SEA is sequential read on the index scan, while B+ tree needs traversal of individual leaf nodes. Compared to LSM Tree, SEA stores data in only one file, while LSM stores data in multiple SSTable files.
|
