Order preserving code having a search tree
Takashi G. Sato · Systems and Computers in Japan · 1991
Abstract Recently, computers have been used not only for numerical computations but also for various data processing applications. Thus, the ability to store data has become more important. This paper considers external memory which supports a large amount of computer memory and studies its effective utilization and rapid accesses. Tabular data structure having a domain for each column such as a relation table of a relational database or set of records in a file also are considered. The idea is to combine updatable and order‐preserving code and search trees. A compact data structure which supports both functions can be obtained. Cost analysis shows that its space is less than half of that of a table with B‐tree indexing structure and that its speed is as fast as when B‐trees are employed. Moreover, fast coincidental or range search can be possible under the conditions when no B‐tree could be used. This is because the.code obtained from the proposed method has minimum length and order preserving characteristics.