Memory space saving method of storing data which must be found quickly

摘要

A memory space saving method of storing data blocks which must be found quickly, and to each of which linearly pre-sorted keys are assigned, is given. The keys are arranged in the lowest node level of a t-ary B*-tree. If the maximum number of keys in a node is exceeded, it is not divided as is otherwise usual, but the greatest key is transferred to the adjacent node which contains the next greatest key. If no adjacent node exists, a new node is created. By using the method, creation of only partly occupied nodes is avoided. The B*-tree is densely stored. <IMAGE>