Séquentiellement Construction complète B-Arbres

Question

Si j'ai un ensemble trié de données, que je veux stocker sur le disque d'une manière qui est optimale pour la lecture séquentielle et de faire des recherches au hasard sur, il semble que B-Tree (ou l'une des variantes est un bon choix ... en supposant que ces données-set ne tiennent pas tous dans la RAM).

La question est peut B-Tree complet être construit à partir d'un ensemble de données triées sans faire de fractionnements? Alors que les données triées peuvent être écrites séquentiellement sur le disque.

Answer 1

La construction d'un "arbre B +" à ces spécifications est simple.

1. Choisissez votre facteur de branchement k.
2. Écrivez les données triées dans un fichier. C'est le niveau des feuilles.
3. Pour construire le plus haut niveau suivant, scannez le niveau actuel et d'écrire tous les k ^{e élément} .
4. Arrêter lorsque le niveau actuel comporte des éléments de k ou moins.

Exemple avec k = 2:

0 1|2 3|4 5|6 7|8 9
0   2  |4   6  |8
0       4      |8
0               8

Maintenant, regardons pour 5. Utilisez la recherche binaire pour trouver le dernier numéro inférieur ou égal à 5 au niveau supérieur, ou 0. Regardez l'intervalle dans le prochain niveau le plus bas correspondant à 0:

0       4

4:

        4   6

4 à nouveau:

        4 5

Je l'ai trouvé. En général, le j ^{e élément} correspond à des éléments jk si (j + 1) k-1 au niveau suivant. Vous pouvez également analyser le niveau de la feuille linéaire.

Answer 2

Nous pouvons faire un B-arbre en un seul passage, mais il ne peut pas être la méthode de stockage optimale. En fonction de la fréquence que vous faites des requêtes séquentielles contre les accès aléatoire, il peut être préférable de le stocker dans l'ordre et utiliser la recherche binaire pour desservir une requête d'accès aléatoire.

Cela dit: supposons que chaque enregistrement dans votre b-tree détient (m - 1) touches ( m > 2, le cas binaire est un peu différent). Nous voulons que toutes les feuilles sur le même niveau et tous les noeuds internes d'avoir au moins (m - 1) / 2 touches . Nous savons qu'un b-arbre plein de hauteur k a (m ^ k - 1) clés. Supposons que nous avons n clés au total à stocker. Laissez k être le plus petit entier tel que m ^ k - 1> n . Maintenant, si 2 m ^ (k - 1) - 1 nous pouvons remplir complètement les nœuds internes et distribuer le reste des clés uniformément sur les nœuds feuilles, chaque nœud de feuille se soit le sol ou le plafond de (n + 1 - m ^ (k - 1)) / m ^ (k - 1) des touches . Si nous ne pouvons pas faire cela, alors nous savons que nous avons assez pour remplir tous les nœuds en profondeur k - 1 au moins à mi-chemin et stocker une clé dans chacune des feuilles.

Une fois que nous avons décidé de la forme de notre arbre, il suffit de faire un parcours infixe des touches laissant tomber successivement des arbres en position que nous allons.

Answer 3

Optimal sens qu'un parcours infixe des données sera toujours à la recherche vers l'avant dans le fichier (ou région mmaped), et se fait une recherche aléatoire dans un nombre minimal de positionnements.