The underlying data structure upon which the whole database system is founded is a compressed and extensible vector type. HPDS makes extensive use of vectors to implement hashtables, string pools and the columns of relations. The bit-lengths of the integers that have to be stored in these structures vary widely, both between structures and over the lifetime of an individual instance. The integers stored may take on values in the millions, necessitating a 32 bit integer representation were conventional arrays used. In many other cases, the values in the arrays will be drawn from small finite sets whose indexes require only a few bits. HPDS provides for both extremes by basing its store on integer vectors that are extensible both in length and in width.
Figure 3.2: Dynamic vectors are allocated store in a number of blocks
with a maximum of 8K bytes per block
The vectors are implemented as object classes with bit-aligned elements, stored in a series of blocks as shown in figure 3.2. This block structure is designed to reduce the costs associated with growing the vectors. Growing a vector involves the following algorithm: