Où sont stockées les valeurs des clés B-Tree?

J'ai étudié B-Trees pour stocker environ 10k chaînes de base de données chaque chaîne ayant un identifiant unique qui, je pense, peut agir comme ma clé. Mais chaque implémentation que j'ai vue ne montre que les clés d'un B-Tree et non les valeurs. Je suis sûr que B-Tree en tant que carte doit lier des valeurs à des clés mais je ne peux pas comprendre si elles sont stockées dans le nœud de l'arbre avec une clé. Par exemple.Où sont stockées les valeurs des clés B-Tree?

 ||key3| |key6|| 
    /  |   \ 
    / ||key4| |key5|| \ 
/      \ 
||key1| |key2||   ||key7| |key8||

 ||k3,v3| |k6,v6|| 
    /  |   \ 
    / ||k4,v4||k5,v5|| \ 
/      \ 
||k1,v1| |k2,v2||   ||k7,v7| |k8,v8||

Je ne sais pas comment et où les valeurs sont stockées.

Source

2017-10-02 djay

Dans chaque noeud, interne et feuille, avec les clés.

Dans un B + -Tree, toutes les clés sont disponibles dans les nœuds feuille. Ainsi, dans le cas de la division d'un nœud feuille, vous pouvez seulement envoyer des clés à votre parent et conserver des valeurs pour vous-même. Dans un arbre B, les clés ne se répètent pas, vous devrez donc avoir des valeurs dans les nœuds internes.

Vous pouvez utiliser une carte Key-Value et parcourir sa fonction pour les fonctions spécifiques à l'arbre. Puisque vous devez garder vos clés triées, vous devez utiliser une carte triée, comme TreeMap dans java ou simple std :: map pour C++. (Python n'a rien de tel dans la bibliothèque standard.) Ils aident également à diviser facilement un nœud et à pousser les choses vers un nouveau nœud.

Source

2017-10-02 14:21:19

Donc, si je veux stocker 10K ensembles de chaînes, chaque ensemble a environ 10 mots et l'un des mots est ID unique, la 2ème représentation est correcte pour construire un B-Tree? Oui, je suis impatient de faire une mise en œuvre triée, Puis-je utiliser un noeud à l'intérieur SortedHashMap pour stocker les clés? Pouvez-vous indiquer n'importe quelle visualisation pour comprendre le bâtiment B-Tree pour des informations stockées dans une mémoire externe comme un fichier, pas la mémoire principale? – djay

OMI, la deuxième représentation est correcte. Vous n'avez pas entendu parler de SortedHashMap, de quelle langue parlez-vous? pour autant que je sache, il est impossible de trier les cartes de hachage. pour la visualisation, https://www.cs.usfca.edu/~galles/visualization/BTree.html. On nous a appris à l'utiliser. –

par SortedHashMap, je signale à un doute que je peux avoir le noeud de B-Tree stockant des clés dans l'ordre trié, c.-à-d. ordre croissant mais les clés sont nécessaires pour passer par le hachage car ce sont de longs entiers de longueur supérieure à 20. Un autre je regardais TreeMap, il semble que tout se passe bien. Je l'ai déjà dit sauf le hachage. – djay

Où sont stockées les valeurs des clés B-Tree?

Répondre

Questions connexes