A computer filing system includes a data access and allocation mechanism including a directory and a plurality of indexed data files or hash tables. The directory is preferably a radix tree including directory entries which contain pointers to respective ones of the hash tables. Using a plurality of hash tables avoids the whole database ever having to be re-hashed all at once. If a hash table exceeds a preset maximum size as data is added, it is replaced by two hash tables and the directory is updated to include two separate directory entries each containing a pointer to one of the new hash tables. The directory is locally extensible such that new levels are added to the directory only where necessary to distinguish between the hash tables. Local extensibility prevents unnecessary expansion of the size of the directory while also allowing the size of the hash tables to be controlled. This allows optimisation of the data access mechanism such that an optimal combination of directory-look-up and hashing processes is used. Additionally, if the number of keys mapped to an indexed data file is less than a threshold number (corresponding to the number of entries which can be held in a reasonable index), the index for the data file is built with a one-to-one relationship between keys and index entries such that each index entry identifies a data block holding data for only one key. This avoids the overhead of the collision detection of hashing when it ceases to be useful.

Ein Dateisystem schließt eine Datenzugang und -verteilung Einheit einschließlich ein Verzeichnis und eine Mehrzahl der indexierten Dateien oder der Hacktische ein. Das Verzeichnis ist vorzugsweise ein Wurzelbaum einschließlich Einträge in ein Verzeichnis, die Zeiger zu den jeweiligen der Hacktische enthalten. Das Verwenden einer Mehrzahl der Hacktische vermeidet die vollständige Datenbank in einem Zug Re-gehackt werden überhaupt müssende. Wenn eine Durcheinandertabelle übersteigt, stellen Sie maximale Größe, während Daten addiert werden, es wird ersetzt durch zwei Hacktische ein und das Verzeichnis wird aktualisiert, um zwei verschiedene Einträge in ein Verzeichnis jeden einzuschließen, der einen Zeiger bis einen der neuen Hacktische enthält. Das Verzeichnis ist am Ort so ausdehnbar, daß neue Niveaus dem Verzeichnis hinzugefügt werden, nur wo notwendig, zwischen den Hacktischen zu unterscheiden. Lokale Dehnbarkeit verhindert nicht notwendige Expansion der Größe des Verzeichnisses beim auch erlauben, daß die Größe der Hacktische gesteuert wird. Dieses erlaubt Optimierung des Datenzugriffsmechanismus so, daß eine optimale Kombination von Verzeichnis-schauen-oben und Hashingprozesse verwendet wird. Zusätzlich wenn die Zahl den Schlüsseln, die zu einer indexierten Datei abgebildet werden, kleiner als eine Schwelle Zahl ist (entsprechend der Zahl Eintragungen, die in einem angemessenen Index gehalten werden können), wird der Index für die Datei mit einem eins-zu-eins Verhältnis zwischen Schlüsseln und Indexeinträgen so errichtet, daß jeder Indexeintrag einen Datenblock kennzeichnet, der Daten für nur einen Schlüssel hält. Dieses vermeidet die Unkosten der Zusammenstoßabfragung von Hashing, wenn es aufhört, nützlich zu sein.