La meilleure façon de créer un arbre B basé sur disque à partir d'un fichier donné?

Question

Connaissez-vous un algorithme rapide pour créer un arbre B à partir d'un fichier existant (non trié) contenant des entiers séparés par des espaces. Typiquement, la taille du fichier sera plus grande que la RAM disponible.

Vous pouvez supposer que l'arborescence B ne sera pas modifiée par la suite, c'est-à-dire qu'elle sera uniquement utilisée pour indexer les informations dans le fichier (disons que le fichier contient des chaînes séparées par des virgules). De plus, est-ce qu'un arbre B est la meilleure idée à utiliser pour un index, pouvez-vous suggérer d'autres structures?

Answer 1

Cela dépend de la façon dont vous voulez accéder à vos données. Si vous utilisez une hashtable, vous pouvez uniquement accéder aux éléments par leur clé primaire dans O (1) qui est plus rapide qu'avec un arbre (log (n))

Vous ne pouvez pas sélectionner des plages (toutes les chaînes entre 10 et 20) qui est supporté par les algorithmes de l'arbre dans Log (n) où en tant qu'indice de hachage peut entraîner un balayage complet O (n). les overheads constants des hashs sont généralement plus grands (ce qui n'est pas un facteur de la notation thêta, mais ils existent toujours) alors que les algorithmes d'arborescence sont généralement plus faciles à maintenir, croître avec les données, scale, etc

Utilisez une table de hachage si vous n'avez pas besoin d'un ordre et d'un arbre binaire (équilibré) sinon.