# Performance analysis of new file organizations based on dynamic hash-coding

Michel Scholl

<figure><img src="image_1.png" /></figure>

## To cite this version:

Michel Scholl. Performance analysis of new file organizations based on dynamic hash-coding. [Research Report] IRIA-RR-347, IRIA. 1979, pp.29. hal-04716610

HAL Id: hal-04716610

https://inria.hal.science/hal-04716610v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
RIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_3.png" /></figure>

PERFORMANCE ANALYSIS
OF NEW FILE ORGANIZATIONS
BASED ON
DYNAMIC HASH-CODING

Michel SCHOLL

RR 347
Rapport de Recherche N° 347

03/79

Mars 1979

29 p.
PERFORMANCE ANALYSIS OF NEW FILE ORGANIZATIONS
BASED ON DYNAMIC HASH-CODING

Michel Scholl
IRIA-LABORIA

Résumé :

De nouvelles méthodes d'organisation de fichiers, basées sur le «hachage» (hash-coding), adaptées aux fichiers dont la taille varie rapidement sont apparues récemment dans la littérature. Dans les trois techniques proposées, le ré-hachage (rehashing) est évité, l'espace en mémoire secondaire est dynamiquement alloué et ajusté au nombre d'articles effectivement rangés dans le fichier et il n'existe pas de débordements. Deux de ces trois techniques utilisent un index. L'accès à un article quelconque du fichier est rapide, cependant le taux de remplissage de l'espace mémoire est relativement bas ($Ln2 \approx .69$).

Dans le but d'accroître ce taux, nous introduisons dans cet article deux nouvelles méthodes basées sur la même idée et analysons leurs performances. Ces deux techniques utilisent un index dont la taille est beaucoup plus petite. Dans les deux cas, on accepte des débordements. Il s'en suit un léger accroissement du temps d'accès à un article. Pour un taux de remplissage de l'espace mémoire égal à .85, le nombre moyen d'accès à la mémoire secondaire, nécessaires pour trouver un article quelconque est inférieur à 2 (si l'on suppose que l'index est disponible en mémoire centrale).

Abstract :

New file organizations based on Hash-Coding recently appeared in the literature, which are suitable for data whose volume may vary rapidly. In the three schemes which have been independently proposed, rehashing is avoided, storage space is dynamically adjusted to the number of records actually stored and there are no overflow records. Two of these techniques employ an index to the data file. Retrieval is fast, however storage utilization is low ($Ln2 \approx .69$).

In order to increase storage utilization, we introduce below two schemes based on a similar idea and analyze their performance. Both techniques use an index of much smaller size. In both schemes, overflow records are accepted. The price which has to be paid for the improvement on storage utilization is a slight access cost degradation. For a storage utilization equal to .85, the expected number of accesses to secondary storage required to find a record (successful search) is less than 2 (provided the index is available in main storage).
# 1 - INTRODUCTION

Conventional Hash-coding used as a file access technique has the advantages of being simple and fast (at least if the distribution of the records over the available storage space is uniform) (see, for example, [1, Section 6, 4]). However, if the file grows by large factors, or if the record's distribution over the available storage space is not uniform, the number of overflow records may be large and therefore retrieval of a record may be significantly slowed down. On the contrary, if the file shrinks, storage space is underutilized. Such situations require the file's rehashing, which is costly, especially in a multi-user environment.

Recently, new file organizations based on Hash-coding appeared in the literature which avoid rehashing or any thorough reorganization of the file when the data volume grows or shrinks by large factors. In the three schemes which have been proposed under the names *Dynamic Hashing* [2], *Extendible Hashing* [3] and *Virtual Hashing* [4], there are no overflow records. Assume the allocated secondary storage space is divided into buckets having a capacity of b records. When a record is to be inserted into a full bucket, the latter is split into two buckets among which the records are distributed<fnref n="1" />. The "hash" function, which locates a given record provided with a unique key, is dynamically modified and the allocated storage space is dynamically adjusted to the number of records actually stored in the file.

Dynamic Hashing [2] and Extendible Hashing [3] employ an index to the data file. By using the dynamic "hash" function, a bucket is associated with the given unique record's key and the bucket's location is identified by searching through the index. Once the bucket's address has been found, retrieval is fast: only one access to secondary storage is required, since there are no overflow records. If the file grows steadily, this index, initially available in core memory, will eventually be partly stored in secondary storage. This will slow down searching and updating. Extendible Hashing's index rapidly becomes prohibitively large, while in the case of Dynamic Hashing, the expected index size grows *linearly* as the number of records increases.

<footnote n="1">1) This splitting policy is used in connection with other file organizations, as IBM's Virtual Storage Access Method (VSAM) [5] and B-trees [1].</footnote>
The Virtual Hashing (VH) schemes proposed in [4], do not employ any index. Retrieval of a record may then require only one access to secondary storage.

The price to be paid for this is a very low storage utilization, compared to the storage utilization provided by Dynamic Hashing and Extendible Hashing, which is in both cases approximatively equal to $Ln2 [2, 3]^2$.

In order to prevent VH' storage utilization degradation, it is suggested in [4] that splitting of a bucket be deferred (i.e. overflow records are accepted). This led to the definition of $VH_1$ [4]. However the lower bound on storage utilization is still low and deletion of a record is a rather complicate operation when the file shrinks (this is not dramatic in applications, where the file tends to grow steadily, e.g. business applications).

This idea has also been independently studied in [2]<sup>3</sup>. The resulting improvement is not significant and leads to more complicated searching and updating algorithms.

In this paper, we pursue the same goal: splitting of a bucket is deferred until a certain number of overflow records have been inserted. Retrieval of a record may then require more than one access to secondary storage. We present below two dynamic hash-coding schemes provided with an index and analyze their performance. Compared to the above schemes [2, 3], these new techniques provide a smaller index size and a higher storage utilization while the access cost degradation is not dramatic and the searching and updating algorithms are kept simple.

The first scheme to be studied is a variant of Larson's Dynamic Hashing [2]. In this technique, splitting of a bucket is deferred until $β \times b$ records have been addressed to this bucket, where b denotes the bucket's capacity

<footnote n="2">2) It is not surprising that both schemes provide the same storage utilization. Only the dynamic "hash" functions and therefore the index structures are different. One may easily show that a variant of $VH_0$ with index would not only give the same performance (Ln2), but also closely ressemble to Extendible Hashing [3, 4].

It is interesting to note that this value of Ln2 obtained in [2] and [3] by different approaches is precisely the value found in the case of two other file organizations : VSAM [6] and B-trees [7].</footnote>

<footnote n="3">3) A similar idea has been proposed for indexed sequential files [6] which results in an important increase in storage utilization.</footnote>
and $\beta$ is greater than 1. Expected storage utilization and number of accesses to secondary storage required to find a record (successful search), provided the index is available in main storage, are analyzed as a function of $\beta$. Compared to Larson's scheme, the index size is decreased by a factor of $\beta$. In order to get a significant storage utilization increase, $\beta$ must be large enough ($\beta \ge 3$).

A different approach led to the definition of the second scheme proposed below. In this technique, splitting is performed every $\gamma \times b$ insertions, and the bucket to be split is not necessarily the one in which the last insertion occurred. This scheme provides the same advantages as Dynamic Hashing with deferred splitting, i.e. increase in storage utilization without significant increase in the number of accesses to secondary storage.

## 2 - DYNAMIC HASHING WITH DEFERRED SPLITTING

We first outline the main features of Larson's Dynamic Hashing scheme. The reader is referred to [2] where the file organization and the searching and updating algorithms are given in more details. A first modification to Larson's scheme is then presented and analyzed, in terms of storage utilization and number of accesses to secondary storage. Finally another change in the data file structure is suggested, which slightly complicates the file structure but results in a significant improvement of the performance. In both cases, the average index size is decreased by a factor of $\beta$.

The number of records actually stored in the file at a given point in time is denoted by $N$. Each record, identified by a unique key, is associated with a bucket. For the sake of simplicity, records are assumed to be equal in length. This is not crucial (see [2]). Initially, secondary storage space is allocated for $M$ buckets. All buckets are assumed to be equal in size ($b$). Throughout the paper, a storage management system is assumed from which buckets can be requested and to which free buckets can be returned. Such a storage management system is used, for example, in the data base management system INGRES [9].

<footnote n="4">4) A similar splitting policy is proposed in [8].</footnote>
The expected secondary storage utilization, and the expected number of accesses to secondary storage when (successfully) searching a record are respectively denoted by $\alpha$ and $T$.

## 2.1 - Dynamic Hashing [2]

An initial hashing function $H_0$ distributes the records among $M$ initial index entries. Each index entry (node) contains a pointer to a bucket in the file. When trying to insert a record into a bucket which already contains $b$ records, a new bucket is allocated, the $b + 1$ records are distributed among the two buckets, and the index is updated: the initial index entry becomes the root of a tree, two nodes are linked to the root, the left son pointing, say towards the original bucket, the right son pointing towards the new bucket. Sooner or later one or the other of the two buckets will in turn become full and will be split into two buckets, etc... The index grows with time to a forest of $M$ trees. Assume the number of records actually stored decreases. If the sum of the number of records in two brother buckets becomes less than $b$ records, the two brother buckets are merged into one, the other one being freed and the index is updated. A straightforward organization of the index forest [2] is depicted in Figure 1: each index entry is either an internal node (TAG = 0), which contains pointers to its father and sons, or an external node (TAG = 1) which contains, besides the pointer to its father, a pointer to a bucket in the data file (BKT) and the number of records actually stored in this bucket (RCDS).

<table><tr><td>TAG</td><td>FATHER</td></tr><tr><td>LEFT</td><td>RIGHT</td></tr></table>

internal node (TAG=0)

<table><tr><td>TAG</td><td>FATHER</td></tr><tr><td>RCDS</td><td>BKT</td></tr></table>

external node (TAG=1)

<caption>Figure 1 : Index entry</caption>

This simple tree structure leads to heavy storage requirements. Better ways of representing trees are discussed in [1].

To find or insert a record with key $K$, the root of the corresponding search tree is first located by computing $H_0(K)$. Then the tree is scanned down until an external node is reached. (This node contains the pointer to the bucket in which the record is to be stored). The problem now is to associate with each unique key $K$, a unique path when scanning down the tree. This is done, by
using a second function $B(K)$. It is suggested in [2] that $B$ be implemented by
means of a pseudo random number generator `RAND` which returns 0 or 1 with proba-
bility .5 when called. The pseudo-random 0 - 1 sequence obtained by successive
calls of `RAND` uniquely determines the path through the corresponding tree
(whose root is given by $H_0(K)$). More precisely, if the root node has a tag equal
to 1 (external node) then it contains the address of the bucket in which the
record is to be found. Otherwise, compute $H_1(K)$ where $H_1$ is another hashing
function independent of $H_0$. $H_1(K)$ is the seed for the generator `RAND`. A first
call of `RAND` indicates whether the left son or the right son of the root has to
be chosen. The chosen son is either an external node, or an internal node. In
the latter case, call again `RAND`, etc... until an external node is eventually
reached, which node contains a pointer to the bucket in which the record is to be
stored.

2.2 - *Dynamic Hashing with deferred splitting*

Assume now that splitting of any bucket is deferred until $β \times b$ records ($β > 1$) have been addressed to this bucket. First, consider the case $β \le 2$. When trying to insert a record into the "primary" bucket i which already contains $b$ records a new "overflow" bucket is allocated (bucket k) and chained to bucket i. The new record is inserted into this overflow bucket. Any other record candidate to be inserted into bucket i, will be inserted into the overflow bucket, until the latter contains ($β - 1)b$ records (see Figure 2a). This "chaining with separate lists" collision resolution method is used in connection with several applications, among others INGRES [9]. When trying to insert a record into a bucket whose overflow bucket already contains ($β - 1)b$ records, then splitting occurs in exactly the same fashion as in Larson's scheme [2]. A new bucket say j is allocated, the $b$ records are distributed among bucket i and bucket j. Bucket k is freed (Figure 2b) and the index which has exactly the same structure as in [2] is updated. Searching and updating algorithms are omitted since they are much the same as in Dynamic Hashing. For further details, the interested reader is referred to [2].

<figure><img src="image_4.png" /><figcaption>Figure 2 : Dynamic Hashing with deferred Splitting</figcaption></figure>
If $\beta$ is greater than 2, when the first overflow bucket is full, another overflow bucket is allocated and chained to the first one, a.s.o., until $\beta b$ records have been inserted. For all values of $\beta$, when splitting occurs, the index is updated, i.e. the former external node (of level $r$ in the tree) becomes an internal node pointing towards two external nodes (its sons) of level $r+1$ in the tree, each of them pointing towards a chain of one or more buckets containing the records. Then the $\beta b + 1$ records are distributed ((k + 1)st call of RAND) among 1) the original chain of buckets, and 2) a new chain of buckets (one or more new buckets are allocated). Possibly one or more buckets which belonged to the original chain are freed.

Following Larson's analysis, we derive below the expected storage utilization $\alpha$ and the expected number of accesses $T$ to secondary storage, required to find a record actually stored in the file (successful search), provided that the index is available in main memory.

Let us consider first the index size. When the number of records $N$ is large, it was shown in [2], because of the close connection with tries [1], that the expected number of internal and external nodes are given by the following excellent asymptotic approximations, in the case of Dynamic Hashing :

$$ (1) \qquad \begin{aligned} E(\text{int. nodes}) &\approx \frac{N}{bLn2} - M \\ E(\text{ext. nodes}) &\approx \frac{N}{bLn2} \end{aligned} $$

Obviously, the same argument applies to Dynamic Hashing with Deferred Splitting and we have :

$$ (2) \qquad \begin{aligned} E(\text{int. nodes}) &\approx \frac{N}{\beta b Ln2} - M \\ E(\text{ext. nodes}) &\approx \frac{N}{\beta b Ln2} \end{aligned} $$

Therefore the index size is approximatively decreased by a factor of $\beta$.
Denote by $E(B)$ and $E(B_{ov})$ respectively the average number of "primary" buckets and the average number of overflow buckets in the file. Then we have :

$$ (3) \qquad \alpha = \frac{N/b}{E(B) + E(B_{ov})} $$

The number of "primary" buckets allocated is equal to the number of external nodes less the number of (non-allocated) empty buckets [2]. The number of empty buckets is negligible when $\beta b \ge 9$ (see [2, Eq. (21)]). Therefore $E(B)$ is given by the following asymptotic approximation :

$$ (4) \qquad E(B) = \frac{N}{\beta b \ln 2} $$

In order to find an asymptotic approximation of $E(B_{ov})$, we assume first that $\beta$ is integer ($\ge 2$). Assume n records hash to tree L, $L = 1, 2, \dots, M$.

The average number of overflow buckets in tree L is given by :

$$ (5) \qquad E(b_{ov}) = \sum_{r>0} 2^r \sum_{j=1}^{\beta-1} \sum_{i=jb+1}^{(j+1)b} q_r(i) $$

where $q_r(i)$ denotes the probability that at least i records went through a given node of level r in tree L (i among the n records produce the same binary sequence of length r, when successively calling RAND r times), given that more than $\beta b$ records went through its father.

$q_r(i)$ is given by [2] :

$$ q_r(i) = \sum_{k=\beta b+1}^{n} \binom{n}{k} (2^{-r+1})^k (1 - 2^{-r+1})^{n-k} \binom{k}{i} 2^{-k} $$

$$ E(b_{ov}) \triangleq \sum_{j=1}^{\beta-1} \sum_{i=jb+1}^{(j+1)b} \sum_{r>0} 2^r \sum_{k=\beta b+1}^{n} \binom{k}{i} \binom{n}{k} (2^{-r+1})^k (1 - 2^{-r+1})^{n-k} $$

$$ (6) \qquad E(b_{ov}) = \sum_{j=1}^{\beta-1} \sum_{i=jb+1}^{(j+1)b} Q_i $$

where

$$ (7) \qquad Q_i \triangleq \sum_{k=\beta b+1}^{n} \binom{k}{i} \binom{n}{k} 2^{-k+1} \sum_{r>0} 2^{-r(k-1)} (1-2^{-r})^{n-k} $$
Applying Euler Mac-Laurin Sum formula to the last sum denoted by $a_k$, we obtain the following very good approximation :

$$a_k = \frac{k-2}{n-k+1} a_{k-1}$$

$$a_k = \frac{(k-2)!}{(n-k+1)(n-k+2)\cdots(n-2)} a_2$$

Applying again Euler Mac Laurin Sum formula to $a_2$ reduces to the following expression :

$$a_2 = 1/(n-1)Ln2$$

Then, we have :

$$Q_i = \frac{n}{Ln2} \sum_{k=\beta b+1}^{n} \binom{k}{i} \frac{2^{-k+1}}{k(k-1)}$$

$$Q_1 = \frac{n}{Ln2} \sum_{k=\beta b}^{n-1} \frac{1}{k^2}$$

$$Q_1 \approx \frac{n}{Ln2} \sum_{k=\beta b}^{\infty} \frac{1}{k^2} < \frac{1}{\beta b^2 \beta b - 1}$$

Therefore, for practical values of $b$, $Q_1$ may be neglected, and for $i \ge 2$ :

$$Q_i = \frac{n}{Ln2} \left[ \frac{2^{-i+1}}{i(i-1)} \sum_{k=0}^{n-i} \binom{k+i-2}{i-2} 2^{-k} - \sum_{k=i}^{\beta b} \frac{2^{-k+1}}{k(k-1)} \binom{k}{i} \right]$$

The first sum into brackets converges very rapidly ($n-i$ is large) to $2^{i-1}$. $Q_i$ is thus reduced to the following expression :

$$(8) \qquad Q_i = \frac{n}{Ln2} \left[ \frac{1}{i(i-1)} - \sum_{k=i}^{\beta b} \frac{2^{-k+1}}{k(k-1)} \binom{k}{i} \right]$$

Substituting Eq. (8) into Eq. (6) and cleaning up reduces to :

$$(9) \qquad E(b_{ov}) = \frac{n}{bLn2} \left[ H_{\beta} - 1 - b \sum_{j=1}^{\beta b-1} \sum_{i=jb+1}^{(j+1)b} \sum_{k=i}^{\beta b} \frac{2^{-k+1}}{k(k-1)} \binom{k}{i} \right]$$

where $H_\beta$ denotes the harmonic series of order $\beta$. . .
Combining Eqs. (3), (4) and (9) gives the following asymptotic approximation for the expected storage utilization ($\beta$ integer $\ge 2$):

$$ 
\begin{array}{l}
\alpha = \frac{\ln 2}{\frac{1}{\beta} + H_{\beta} - 1 - b A(b, \beta)} \\
(10) \\
\text{where} \quad A(b, \beta) \stackrel{\Delta}{=} \sum_{j=1}^{\beta-1} j \cdot \sum_{i=jb+1}^{(j+1)b} \sum_{k=i}^{\beta b} \frac{2^{-k+1}}{k(k-1)} \binom{k}{i}
\end{array}
$$

The sum $A$ has been slumped. Numerical calculations showed that for $\beta \ge 3$, as $b$ increases, $bA(b, \beta)$ is very rapidly independent of $b$ ($b \ge 10$).

If $\beta \le 2$, Eq. (6) is replaced by:

$$ (11) \qquad E(b_{ov}) = \sum_{i=b+1}^{\beta b} Q_i \qquad E(b_{ov}) = \frac{n}{b \ln 2} \left[ 1 - \frac{1}{\beta} - b \sum_{i=b+1}^{\beta b} \sum_{k=i}^{\beta b} \frac{2^{-k+1}}{k(k-1)} \binom{k}{i} \right] $$

Combining Eqs. (3), (4) and (11) gives the following expression:

$$ 
\begin{array}{l}
\alpha = \frac{\ln 2}{1 - b B(b, \beta)} \\
(12) \\
\text{where} \quad B(b, \beta) \stackrel{\Delta}{=} \sum_{i=b+1}^{\beta b} \sum_{k=i}^{\beta b} \frac{2^{-k+1}}{k(k-1)} \binom{k}{i}
\end{array}
$$

Observe that Eqs. (10) and (12) give the same expression for $\beta = 2$. Table 1 illustrates the behavior of $\alpha$ as $\beta$ increases up to 2. Clearly, the improvement due to deferred splitting is not dramatic, especially if $b$ is large.

<table><thead><tr><th>β</th><th>α</th></tr></thead><tbody><tr><td>1</td><td>.693</td></tr><tr><td>1.3</td><td>.696</td></tr><tr><td>1.5</td><td>.702</td></tr><tr><td>1.8</td><td>.730</td></tr><tr><td>1.9</td><td>.744</td></tr><tr><td>2</td><td>.762</td></tr></tbody></table>

$b = 10$

<table><thead><tr><th>β</th><th>α</th></tr></thead><tbody><tr><td>1</td><td>.693</td></tr><tr><td>1.3</td><td>.693</td></tr><tr><td>1.5</td><td>.695</td></tr><tr><td>1.8</td><td>.711</td></tr><tr><td>1.9</td><td>.723</td></tr><tr><td>2</td><td>.740</td></tr></tbody></table>

$b = 20$

<table><thead><tr><th>β</th><th>α</th></tr></thead><tbody><tr><td>1</td><td>.693</td></tr><tr><td>1.3</td><td>.693</td></tr><tr><td>1.5</td><td>.693</td></tr><tr><td>1.8</td><td>.699</td></tr><tr><td>1.9</td><td>.706</td></tr><tr><td>2</td><td>.722</td></tr></tbody></table>

$b = 50$

<caption>**Table 1** : Dynamic Hashing with deferred splitting : Expected storage utilization ($\beta \le 2$).</caption>
<figure><img src="image_5.png" /><figcaption>Figure 3 : Dynamic Hashing with deferred splitting : α vs β.</figcaption></figure>
However, if $\beta$ is large ($\beta \ge 3$), the increase in storage utilization is significant ($\beta = 3$, $\alpha = .836$; $\beta = 5$, $\alpha = .886$). This is illustrated in Figure 3 where $\alpha$ is plotted versus $\beta$.

Our last task is to find the expected number of accesses to secondary storage, $T$, required to find a record. Consider first, the case of $\beta$ integer $\ge 2$. Assume $n$ records hash to tree $L$.

$$T = 1 + \frac{1}{n} \sum_{r>0} 2^r \sum_{j=1}^{\beta-1} \sum_{i=jb+1}^{(j+1)b} [b + 2b + \dots + (j-1)b + j(i - jb)] q_r(i)$$

$$(13) \qquad T = 1 + \frac{1}{n} \sum_{r>0} 2^r \sum_{j=1}^{\beta-1} \sum_{i=jb+1}^{(j+1)b} \left[ i - \frac{(j+1)b}{2} \right] q_r(i)$$

$$(14) \qquad T = 1 + \frac{1}{n} \sum_{j=1}^{\beta-1} \sum_{i=jb+1}^{(j+1)b} Q_i \left[ i - \frac{(j+1)b}{2} \right]$$

where $Q_i$ is defined in Eq. (7).

Substituting Eq. (8) into Eq. (14), we get:

$$T = 1 + \frac{1}{Ln2} \left[ \sum_{j=1}^{\beta-1} \sum_{i=jb+1}^{(j+1)b} \frac{i-(j+1)b/2}{i(i-1)} - E(b, \beta) \right]$$

where

$$(15) \qquad E(b, \beta) \triangleq \sum_{j=1}^{\beta-1} \sum_{i=jb+1}^{(j+1)b} \left[ i - \frac{(j+1)b/2}{k} \right] \sum_{k=i}^{\beta b} \frac{2^{-k+1}}{k(k-1)} \binom{k}{i}$$

We finally obtain the following expression for $T$:

$$(16) \qquad T = 1 + \frac{1}{Ln2} \left\{ \sum_{j=1}^{\beta-1} \sum_{i=jb+1}^{(j+1)b} \frac{1}{i-1} - \frac{\beta-1}{2} - E(b, \beta) \right\}$$

where $E(b, \beta)$ is given by Eq. (15). As $\beta$ increases the first sum into brackets converges to $\beta - 2$ ($\beta \ge 9$). No significantly simpler expression of $E(b, \beta)$ has been found. Numerical calculations of the latter expression for various values of $b$ showed, as for $bA(b, \beta)$ (see Eq. (10)), the independence of $E(b, \beta)$ with respect to $b$.

If $\beta \le 2$, $T$ is given by:
$$T = 1 + \frac{1}{n} \sum_{r>0} 2^r \sum_{i=b+1}^{\beta b} (i-b)q_r(i)$$

$$(17) \qquad T = 1 + \frac{1}{n} \sum_{i=b+1}^{\beta b} (i - b)Q_i$$

Substituting Eq. (8) into Eq. (17) gives :

$$(18) \qquad T = 1 + \frac{1}{\ln 2} \left\{ \sum_{i=b+1}^{\beta b} \frac{i-b}{i(i-1)} - \sum_{i=b+1}^{\beta b} (i-b) \sum_{k=i}^{\beta b} \frac{2^{-k+1}}{k(k-1)} \right\}_{i=1}^{k}$$

Cleaning up Eq. (18) reduces to the following expression :

$$(19) \qquad T = 1 + \frac{1}{\ln 2} \left\{ 1 - \frac{1}{\beta} - \sum_{i=0}^{b-1} (b-i) \sum_{k=b+1}^{\beta b} \frac{2^{-k+1}}{k(k-1)} \right\}_{i=0}^{k}$$

One may easily verify that Eq. (16) is reduced to Eq. (19), if $\beta = 2$.

<table><caption>Table 2 : Deferred Splitting : Expected Number of Accesses to Secondary Storage T</caption><tr><td>β</td><td>1.3</td><td>1.5</td><td>1.6</td><td>1.8</td><td>2</td><td>3</td><td>4</td><td>5</td><td>7</td><td>10</td><td>20</td></tr><tr><td>T</td><td>1.06</td><td>1.13</td><td>1.16</td><td>1.23</td><td>1.30</td><td>1.64</td><td>1.99</td><td>2.34</td><td>3.06</td><td>4.12</td><td>8.21</td></tr></table>

The access cost degradation is not large for small values of $\beta$, i.e. $\beta \le 5$ (see Table 2).

In conclusion, Deferred Splitting significantly increases storage utilization if $\beta \ge 3$, i.e. if we let any bucket overflow 2 times its capacity before splitting it. Even though $\beta$ is large, the value of T is reasonably low e.g. if $\beta = 3$, then $T = 1.64$. Figure 4 illustrates more precisely the trade-off between fast retrieval and high storage utilization. Each point of the curve is labelled by the corresponding value of $\beta$.

From Figure 4, it is clear that Deferred Splitting definitively improves Dynamic Hashing global performance. Indeed if $\beta = 4$, for example, the index size is divided by 4, the expected storage utilization is equal to .865, while on the average only 2 accesses to secondary storage are required to find a record (once the corresponding buckets chain has been located).
<figure><img src="image_6.png" /><figcaption>Figure 4 : Dynamic Hashing with Deferred Splitting : T vs α</figcaption></figure>
## 2.3 - A Variant in which overflow buckets are shared among several primary buckets

In order to give an idea of how the scheme works, the following example is taken. We choose the combination $b = 10, \beta = 1.5$, and assume as in Section 2.2, that splitting occurs when 15 records have been inserted (10 in the primary bucket i, and 5 in its overflow bucket). Assume, meanwhile, another primary bucket j has overflowed. Instead of allocating a separate overflow bucket to bucket j, we allocate the second half of bucket k, as an overflow area for bucket j (see Figure 5a). Eventually, either bucket i or bucket j will first be split say bucket i, and 15 records will be distributed among the initial bucket (i) and a new allocated bucket m. One half of the overflow bucket k is thus freed. Now one of the two following events may happen : 1) either (Figure 5b), bucket j is split, before any other primary bucket in the file needs the overflow space available in bucket k, and then (after the split of j) bucket k is freed, 2) or (Figure 5c) before j's split, bucket l needs overflow space and is thus linked to the first half of bucket k.

<figure><img src="image_7.png" /><figcaption>(a) before splitting bucket i</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>(b) after the split of bucket j,
k is freed</figcaption></figure>

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /><figcaption>(c) k is not freed</figcaption></figure>

**Figure 5** : Dynamic Hashing with Deferred Splitting : one overflow bucket is shared by two primary buckets.
Up to $1/(\beta - 1)$ primary buckets may share the same overflow bucket<fnref n="5" />, e.g. if $\beta = 1.25$, one overflow bucket may be shared among up to 4 primary buckets, and 2 bits more are needed to identify (in the primary bucket), which part of the overflow bucket "belongs" to the given primary bucket. Following Section 2.2's analysis, we show below for $\beta \le 2$, that storage utilization is considerably improved to the expense of increased complexity in buckets management.

The index size and the number of primary buckets are unchanged by the above modification, while the average number of overflow buckets is reduced by a factor of $\beta - 1$. Then from Eqs. (11) and (12), we obtain:

$$E(b_{ov}) = \left[ (\beta - 1) \frac{n}{b \ln 2} \left[ 1 - \frac{1}{\beta} - bB(b, \beta) \right] \right]$$

The expected storage utilization is then given by the following asymptotic approximation:

$$(20) \qquad \alpha = \frac{\beta \ln 2}{1 + (\beta - 1)^2 - \beta b(\beta - 1) B(b, \beta)}$$

In the range $1 \le \beta \le 1.6$, $\beta b(\beta - 1) B(b, \beta)$ is very small as shown in Figure 6. As $b$ increases, the expression of $\alpha$ converges to the following (lower bound) expression (represented by the dotted curve in Figure 6):

$$(21) \qquad \alpha = \frac{\beta \ln 2}{1 + (\beta - 1)^2}$$

The maximum value of $\alpha$ occurs at $\beta = \sqrt{2}$:

$$(22) \qquad \alpha_{\max} = \frac{(\sqrt{2} + 1)}{2} \ln 2 = .837$$

<footnote n="5">5) If $\beta = 5/3$, then three primary buckets share two overflow buckets, i.e. one primary will have its overflow records split among two separate overflow buckets. This slows down retrieval and renders the algorithms more complex. Therefore $\beta$ should be chosen less or equal to 1.5.</footnote>
<figure><img src="image_11.png" /><figcaption>Figure 6 : Dynamic Hashing with Deferred Splitting
(shared overflow buckets) : α vs β</figcaption></figure>
For practical reasons $\beta$ must be less or equal to 1.5 (see footnote 5) and such that $1/(\beta-1)$ is an integer. If we choose $\beta = 1.5$, then $\alpha = .83$ which is pretty close to the maximum value (see Figure 6 and Eq. (22)).

Observe that the expected number of accesses to secondary storage is the same as in Section 2.2 (Eq. (19), Table 2). Provided the index is available in main memory, one or at most two accesses are needed to find any record in the file. As a matter of fact, if $\beta = 1.5$ (i.e. for $\alpha = .83$), then $T = 1.13$, while in Section 2.2, if $\alpha = .83$, then $T = 1.64$ (see Figure 4), and in the worst case the number of accesses is equal to 3. However, the scheme studied in Section 2.2 is simpler to implement than the present one.

## 3 - LINEAR SPLITTING

This technique too, necessitates maintenance of an index, each index entry pointing to a bucket of capacity $b$ records. The tree structure of Dynamic Hashing's index may lead to heavy storage requirements (see Section 2). An attempt to improve the index performance (less storage, easier search through the index) led to the following file structure.

### 3.1 - File structure

An initial function $H_0$ associates to the record's key $K$, one among $M$ sequential tables, say $L$. Another hash function $H_r$, independent of $H_0$, associates to $K$ a unique entry in the $L$th table (see Figure 7). This entry contains a pointer BKT to the secondary storage bucket where the record is to be stored : $BKT=L(H_r(K))$. $H_r$ is dynamically changing according to the subfile size, i.e. according to the number of records which hash to list $L$ ($L = H_0(K)$).

<figure><img src="image_12.png" /><figcaption>**Figure 7** : Linear Splitting : Index Structure</figcaption></figure>
<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /></figure>

<figure><img src="image_16.png" /><figcaption>**Figure 8** : Linear splitting, Bucket's allocation in subfile L, L=1,...,M, (γ > 1)</figcaption></figure>
First starting from an empty file, let us see how to insert N records. The initial index is composed of M cells (each list has only one cell), M buckets being initially allocated to the file. After γb records have been inserted in the Lth bucket denoted by $L_1$ (γb records hashed to cell L) bucket $L_1$ is split into two buckets, the records being distributed among $L_1$ and a new bucket $L_2$ (see Figure 8b), whose address is contained in a new cell L(2) appended to the Lth list (initially composed of one cell : L(1)). The index list L contains now 2 cells. After b new insertions, $L_1$ is split once more into two buckets, $L_1$ and $L_3$. Bucket $L_3$'s address is contained in L(3) appended to the Lth index list. After b new insertions, $L_2$ is in turn split into two buckets, $L_2$ and $L_4$. The next buckets to be split are then $L_1$, $L_2$, $L_3$, $L_4$, $L_1$, $L_2$, $L_3$, $L_4$, ..., $L_8$, $L_1$ etc... (Figure 8c). Eventually, as the file grows, any bucket may overflow before it is in turn split. Then, overflow records are stored into one or more overflow buckets as in Section 2.2. When splitting occurs, one or more new buckets are allocated, while one or more buckets (in the initial chain) are possibly freed.

When the Lth list reaches $2^r$ cells ($2^r$ buckets have been allocated for the records hashing to the Lth subfile), the next bucket to be split is $L_1$; when the Lth list has $2^r + I - 1$ cells, the next bucket to be split is $L_I$, $I = 1, \dots, 2^r$, etc...; when $I = 2^r$, the Lth list contains $2^{r+1}$ cells (Figure 9). Two supplementary cells are needed for each list, one containing the value of I, the other one indicating the "level" r of the list. Each time, a split occurs, the pointer I is incremented by 1 (as well as r if $I > 2^r$).

Suppose the file steadily shrinks. After b deletions in the Lth subfile, two buckets are merged, respectively $L_{I-1}$ and $L_{2^r + I - 1}$ (the latter is the most recently allocated bucket), the records being gathered into bucket $L_{I-1}$ (and possibly into one or more overflow buckets). $L_{2^r + I - 1}$ and its overflow buckets are freed, the last index cell $L(2^r + I - 1)$ is deleted and I is decremented by 1. A third supplementary cell is needed for each list, which contains an integer n in the range [0, γb]. Each time an insertion (deletion) occurs n is incremented (decremented) by 1. When n = γb (n = 0), a split (merge) occurs. The insertion and deletion algorithms are summarized below.

<figure><img src="image_17.png" /><figcaption>**Figure 9 :** Linear Splitting : Index Structure, $I=1, \dots, 2^r$ : List L has $2^r + I - 1$ cells.</figcaption></figure>
## INSERTION

1) $n = n + 1$

2) if $n < \gamma b$ go to 6

3) otherwise ($n = \gamma b$) split bucket $L_I$

4) $n = 0$, $I = I + 1$

5) if $I > 2^r$, then $I = 1$, $r = r + 1$

6) end

## DELETION

1) $n = n - 1$

2) if $n \ge 0$ go to 6

3) otherwise ($n = -1$), merge buckets $L_{I-1}$ and $L_{2r+I-1}$

4) $n = \gamma b - 1$, $I = I - 1$

5) If $I = 0$, then $r = r-1$, $I = 2^r$

6) end

It remains to define the hash function $H_r$ which, given $r$ and $I$, associates to a given key $K$, a unique entry in table $L$. From above, $H_r$ must satisfy the following condition :

$$ (a) \quad H_{r+1}(K) = \begin{cases} \text{either } H_r(K) \\ \text{or } H_r(K) + 2^r \end{cases} $$

After a bucket's chain has split, all its records, previously accessed by means of $H_r(K)$ (the buckets which contained those records were located by accessing the table entry $L[H_r(K)]$) are now accessed by computing $H_{r+1}(K)$. The latter calculation must, for each record, uniquely determine whether the $H_r(K)$th index entry or the $(H_r(K) + 2^r)$th entry has to be chosen.

Function $H_r$ is expected to be such that when the split occurs, approximatively half of the records stay in the same bucket, and approximatively half of the records are relocated into the new bucket. The ideal function is that which, given the key distribution, satisfies the following condition :

$$ (b) \text{ for all } K, \quad H_{r+1}(K) = \begin{cases} H_r(K) & \text{with probability } 1/2 \\ H_r(K) + 2^r & \text{with probability } 1/2 \end{cases} $$
It is suggested that the following hash function, employed in
Virtual Hashing [4], be chosen :

$$
(23) \quad H_r(K) \equiv K \bmod 2^r + 1
$$

Condition (b) will be assumed in the subsequent analysis.

We may now outline the search algorithm :

1) $L = H_0(K)$

2) $R = H_r(K)$

if $R \ge I(L)$, go to 4

3) otherwise $R = H_{r+1}(K)$

4) END (the Rth entry of the Lth table contains a bucket's address).

Before going into the performance analysis of this scheme, let us sketch the
following variant : choose M = 1, suppress step 1 in the search algorithm ( we have
only one index list and we do not need anymore function H₀) and replace function
Hₜ defined in Eq. (23) by the following one :

$$
H_r(K) = K \mod M \times 2^r + 1
$$

This variant is not considered below since it clearly leads to a
severe performance degradation if the distribution of the records over the available
buckets happens to be not uniform.

3.2 - Performance analysis

The index obviously has approximatively N/γb cells. 3M supplementary
cells are needed which are much smaller in size.

We now evaluate the expected secondary storage utilization. Consider
subfile L (L = 1,...,M). Let αᵢ be the expected storage utilization when subfile L
contains exactly Nᵢ = (1 + 2 + ... + 2ᵣ⁻¹ + ... + 1) records, i.e., when a split or
a merge occurs, the subfile level being r, the next bucket to be split being
I (I = 1,...,2ᵣ), (see Figure 9).
The number of primary buckets allocated to subfile L before the split (merge) is performed is equal to $2^r + I - 1$ (see Figure 9). $2(I - 1)$ buckets are accessed by employing the hash function $H_{r+1}$, while $(2^r - I + 1)$ buckets are accessed by means of $H_r$. Each of these buckets possibly has one or more overflow buckets linked to it. Denote by $OV_r$, the expected number of overflow buckets linked to a primary bucket accessed by means of $H_r$. Then $\alpha_I$ is given by the following expression :

$$ (24) \qquad \alpha_I = \frac{N_I/b}{2^r + I - 1 + 2(I - 1) OV_{r+1} + (2^r - I + 1) OV_r} $$

Assuming the distribution of the $N_I$ records is uniform over the $2^r$ buckets, the probability $p_I(k)$ that bucket $L_j$ ($j = I, I + 1, \dots, 2^r$) and its overflow buckets contains k records is given by$^6$

$$ p_I(k) = \left( \binom{N_I}{k} \left(\frac{1}{2^r}\right)^k \left(1 - \frac{1}{2^r}\right)^{N_I-k} \right) . $$

$p_I(k)$ is given by the following asymptotic approximation :

$$ (25) \qquad p_I(k) \sim \beta_I^k e^{-\beta_I/k!} $$

$$ \text{where} \qquad \beta_I = \frac{N_I}{2^r} \approx \gamma b \left[ 1 + \frac{I-1}{2^r} \right] $$

$$ \text{Then} \qquad (26) \qquad OV_r = \sum_{j \ge 1} \sum_{k=jb+1}^{(j+1)b} p_I(k) $$

$$ \text{and} \qquad (27) \qquad OV_{r+1} = \sum_{j \ge 1} \sum_{k=jb+1}^{(j+1)b} q_I(k) $$

$$ \text{where} \qquad (28) \qquad q_I(k) = \left( \binom{N}{k} \left( \frac{1}{2^{r+1}} \right)^k \left( 1 - \frac{1}{2^{r+1}} \right)^{N-k} \right) \approx \left( \frac{\beta_I}{2} \right)^k e^{-\beta_I/2/k!} $$

<footnote n="6">6) An analysis of Hash-Coding with Separate Chaining due to Van der Pool [10] is reported in [1, p. 537]. It is implied in [1] that all buckets share a common overflow area, while in the present paper, each bucket owns a separate overflow area.</footnote>
Combining Eqs. (24) to (28) reduces to the following expression :

(29)

$$ \alpha_I = \frac{\gamma}{1 + \frac{1}{2^{r+I-1}} \left[ 2(I-1) \sum_{j>0} j \sum_{k=jb+1} \frac{(j+1)b (\beta_I/2)^k e^{-\beta_I/2}}{k!} + (2^{r-I+1}) \sum_{j>0} j \sum_{k=jb+1} \frac{(j+1)b (\beta_I)^k e^{-\beta_I}}{k!} \right]} $$

As the file steadily grows, $\alpha_I$ will eventually converge to a value independent of I. Steady state is rather rapidly reached as shown in Table 3 : the difference between the minimum value and the maximum value of $\alpha_I$ is less than 2 %, if the subfile contains more than 10 000 records (if $\gamma = 1$, $b = r = 10$, then $N_I > 10 240$). If $\gamma = 1$, $\alpha_I$ is, on the average, only slightly greater than Ln2, but if $\gamma \ge 2$, storage utilization is high (> .81).

<table><caption>**Table 3** : Linear Splitting : Expected Storage Utilization as a function of I, b = 10, r = 10.</caption><thead><tr><th>I / γ</th><th>1</th><th>200</th><th>400</th><th>600</th><th>800</th><th>1024</th></tr></thead><tbody><tr><th>1</th><td>.705</td><td>.686</td><td>.698</td><td>.713</td><td>.715</td><td>.705</td></tr><tr><th>2</th><td>.818</td><td>.814</td><td>.812</td><td>.814</td><td>.818</td><td>.819</td></tr><tr><th>3</th><td>.8698</td><td>.8701</td><td>.8701</td><td>.8690</td><td>.8694</td><td>.8699</td></tr></tbody></table>
As far as the number of accesses to secondary storage is concerned, this scheme is rather *unfair*, since some records (stored in $L_I$, where I is small) are accessed very fast, while other records (I large) may require a large number of accesses. Indeed, just after the split of bucket $L_I$ ($I = 1$), on the average $\beta_1/2 = \frac{\gamma b}{2}$ records are stored in it, while just after the split of bucket $L_{2r}$ ($I = 2^r$) on the average $\beta_{2r}/2 = \gamma b$ records are stored in it (and $\beta_{2r} = 2\gamma b$ records before it is split !).

If we take the average over the $2^r$ buckets, we get the following performance measure (when the file contains $N_I$ records):

$$ (30) \qquad T_I = \frac{1}{N_I} \left[ 2(1-1) T_{r+1} + (2^r - 1 + 1) T_r \right] $$

where $T_r$ is the expected number of accesses required to find *all* the records stored in a bucket's chain, given this chain is accessed by means of $H_r$. $T_r$ is given by the following expression:

$$ T_r = \beta_I + \sum_{k=b+1}^{2b} (k-b)p_I(k) + \sum_{k=2b+1}^{3b} [b+2(k-2b)]p_I(k) + \sum_{k=3b+1}^{4b} [b+2b+3(k-3b)]p_I(k) + \dots $$

$$ (31) \qquad T_r = \beta_I + \sum_{j \ge 1} \sum_{k=jb+1}^{(j+1)b} \left[ k - \frac{(j+1)b}{2} \right] p_I(k) $$

Similarly,

$$ (32) \qquad T_{r+1} = \frac{\beta_I}{2} + \sum_{j \ge 1} \sum_{k=jb+1}^{(j+1)b} \left[ k - \frac{(j+1)b}{2} \right] q_I(k) $$

Combining Eqs. (30), (31) and (32) reduces to the following expression:

$$ (33) \qquad T_I = 1 + \frac{1}{\beta_I} \left\{ 2(1-1) \sum_{j \ge 1} \sum_{k=j0+1}^{(j+1)b} \left[ k - \frac{(j+1)b}{2} \right] p_I(k) + (2^r - 1 + 1) \sum_{j \ge 1} \sum_{k=jb+1}^{(j+1)b} \left[ k - \frac{(j+1)b}{2} \right] q_I(k) \right\} $$

where $p_I(k)$ and $q_I(k)$ are respectively given by Eqs. (25) and (28).
$T_I$ oscillates more significantly (as a function of $I$) than $\alpha_I$ does (Table 4). Note that the extrema of $T_I$ do not correspond to those of $\alpha_I$ (see Table 3). From Table 4, it is clear that the access performance degradation is not important since for a storage utilization approximately equal to .81 (i.e. $\gamma = 2$, see Table 3). $T_I \le 1.71$.

<table><caption>Table 4 : Linear Splitting : Expected number of accesses to secondary storage as a function of $I$, $b = 10$, $r = 10$.</caption><thead><tr><th>I / γ</th><th>1</th><th>200</th><th>400</th><th>600</th><th>800</th><th>1024</th></tr></thead><tbody><tr><th>1</th><td>1.125</td><td>1.174</td><td>1.197</td><td>1.194</td><td>1.171</td><td>1.125</td></tr><tr><th>2</th><td>1.591</td><td>1.669</td><td>1.711</td><td>1.714</td><td>1.677</td><td>1.595</td></tr><tr><th>3</th><td>2.077</td><td>2.195</td><td>2.256</td><td>2.259</td><td>2.206</td><td>2.083</td></tr></tbody></table>

Figure 10 illustrates more precisely the trade-off between fast retrieval and high utilization. The curve is labelled by the corresponding values of $\gamma$. The performance of Dynamic Hashing (Figure 4) is plotted on the same figure. Clearly, Linear Splitting performs almost as well as Dynamic Hashing with Deferred Splitting.

Moreover, the number of index nodes is asymptotically smaller in the former case than in the latter one, for a given ($T, \alpha$) performance : e.g. if $\gamma = 2, \beta = 3$, then the index size of the scheme studied in Section 2.2 is, from Eq. (2) $2N/\beta b \ln 2 - M = N/1.04b - M$, while in the present scheme, the index size is equal to $N/2b + 3M$.
<figure><img src="image_18.png" /><figcaption>**Figure 10 :** *T vs α : Comparison between Dynamic Hashing with Deferred Splitting and Linear Splitting*</figcaption></figure>

## 4 - CONCLUSION

In this paper, we have proposed two new access techniques based on hash-coding, for files whose size may vary by large factors. The goal pursued was to increase storage utilization which is approximatively equal to $O(n^2)$ only, in the file organizations previously proposed [2, 3].

The first scheme studied, a variant of Larson's Dynamic Hashing scheme [2] in which splitting of any bucket is deferred until a certain number of overflow records have been inserted, definitively improves the file performance.
Indeed if we allow any bucket to overflow twice its capacity, the index size is three times smaller than in Larson's scheme, an .83 expected storage utilization is reached, while the expected number of accesses to secondary storage required to find a record (successful search) is equal to 1.64, provided the index is available in main storage (Figure 4 : β = 3) and in the worst case, at most three accesses are needed. Another variant is suggested (Section 2.3) which provides an even better performance. However this results in a more complex storage management.

If the file steadily grows on, the index will eventually be partly stored in secondary storage. Retrieval of a record may then be considerably slowed down. The index node size of Dynamic Hashing with Deferred Splitting is larger (see Fig. 1) than the index node size of the second scheme studied in this paper and nicknamed Linear Splitting. Indeed in the latter, the index node contains only one pointer, if we assume, that the index includes M sequential tables. But then we are faced with the problem of table overflowing. When any of the M tables overflows, we must either repack the whole space available for the index in core memory or create an overflow area on secondary storage. An alternative would be to have a linked allocation, each index node including two pointers, one pointing towards a secondary storage bucket, the other pointing towards the next node in sequence. The latter index organization results in heavier storage requirements and in time consuming operations (searching thru a linked list).

Provided the index is available in main storage, Dynamic Hashing with linear splitting performs quite as well as the first scheme (Figure 10).

Finally, it is worth noting that both schemes keep the searching and updating algorithms simple.

## ACKNOWLEDGEMENT

The author wishes to thank W. LITWIN for his useful suggestions.
REFERENCES

[ 1 ] D.E. Knuth - *The art of computer programming, Vol. 3 - Sorting and Searching* - Addison-Wesley - Reading - Mass. - 1973.

[ 2 ] P.A. Larson - "Dynamic Hashing", BIT, vol. 18, 1978, pp. 184-201,

[ 3 ] R. Fagin, J. Nievergelt, N. Pippenger, H.R. Strong - "Extendible Hashing - A Fast Access Method For Dynamic Files", IBM Research Report RJ2305, San Jose, California, July 31, 1978.

[ 4 ] W. Litwin - "Virtual Hashing : a dynamically changing hashing", Proceedings of the 4th Conference on very large data bases, West-Berlin, September 13-15, 1978, pp. 517-523.

[ 5 ] D.G. Keehn, J.O. Lacy - "VSAM data set design parameters", IBM Syst. J., N° 3, 1974, pp. 186-212.

[ 6 ] T. Nakamura, T. Mizoguchi - "An analysis of storage utilization factor in block split data structuring scheme", Proceedings of the 4th Conference on very large data bases, West-Berlin, September 13-15, 1978, pp. 489-495.

[ 7 ] A.C. Yao - "On random 2-3 Trees", Acta Informatica, N° 9, 1978, pp. 159-170.

[ 8 ] W. Litwin - "Linear Virtual Hashing : a new tool for files and tables implementation", invited to IFIP TC-2 Working Conference on data base architecture, Venice, June 26-29, 1979.

[ 9 ] M. Stonebracker, E. Wong, P. Kreps, G. Held - "The Design and Implementation of INGRES", ACM Transactions on Database Systems, vol. 1, N° 3, September 1976, pp. 189-222.

[10] J.A. Van der Pool - "Optimum Storage Allocation for Initial Loading of a File", IBM J. Res. Develop., November 1972, pp. 579-586.