Est-ce que b + et arbre binaire arbres seulement stocker des données dans les feuilles?

Question

Les arbres peuvent b et b + seulement stocker des données arbres à leurs feuilles? Je suppose qu'ils utilisent leurs noeuds internes pour rechercher les données requises.

Est-ce le cas ou ils ne stockent des données dans chaque nœud?

Answer 1

noeuds non-feuilles "enregistrements" contiennent

• un pointeur (un noeud « adresse » de toutes sortes) à un nœud du niveau bas de l'arbre
• la valeur de la clé du premier (ou le dernier, en fonction de la mise en œuvre) enregistrement dans ce noeud

Ces non-feuilles « dossiers » sont classés par ordre clé de telle sorte que par balayage (ou recherche binaire à l'intérieur) d'un noeud non-feuille, on sait quel nœud dans le niveau suivant peut contenir la valeur recherchée.

Feuille noeuds dossiers contiennent des enregistrements de données complets:. La valeur de clé et tout le reste

Par conséquent données « réelles » n'est contenue dans les nœuds feuilles, les noeuds non-feuilles ne contiennent que [une copie] les valeurs clés. pour une très faible proportion des données (cette proportion dépend du nombre moyen d'enregistrements de données dans un nœud fons de la feuille).

Ceci est illustré dans l'image suivante de la article de Wikipedia sur B + arbres

Le nœud non-feuille, dans la partie supérieure, (la seule dans cet arbre simpliste) ne contient que deux disques de noeuds non-feuille, chacune avec une copie d'une valeur de clé (couleur bleue) et un pointeur vers le noeud correspondant (couleur grise). Cet arbre arrive à avoir que deux niveaux, donc les « enregistrements » au point de nœud racine aux nœuds feuilles. On peut imaginer qu'il ya des niveaux supplémentaires (au-dessus du plus élevé arbre illustré ci-dessous, appelez le « 3-5 nœud »); le nœud serait ci-dessus contient, si tel était le cas (ainsi que d'autres dossiers similaires), un record avec une valeur clé 3 avec un pointeur vers le noeud « 3-5 ».
Notez également que seules les valeurs clés 3 et 5 sont contenus dans les noeuds non-feuilles (par exemple même pas tous Les valeurs clés sont reproduites dans les non-feuille nœuds).
 BTW dans cet exemple, les noeuds non-feuilles contiennent la clé de la dernier enregistrement dans le nœud suivant (fonctionne également si le premier enregistrement ont été utilisés à la place, une légère différence dans la manière la logique de recherche est alors mis en œuvre).

Les noeuds feuilles contiennent la valeur de clé (couleur bleue aussi) et l'enregistrement de données correspondant (d1, d2 ... représenté en gris). Le pointeur rouge-ish représenté à la fin de chaque point de noeud feuille au noeud suivant de la feuille, à savoir celle contenant le même enregistrement de données suivant dans l'ordre des clés; ces pointeurs sont utiles pour « scan » une gamme d'enregistrements de données.

Answer 2

Toutes les données sont dans les feuilles.

Wiki sur B + .

Answer 3

Il y a une certaine confusion sur les arbres et un arbre binaire B +. B + arbres Seuls les stocker des données sur les nœuds feuilles comme des pointeurs. Cela signifie que les données doivent être stockées ailleurs. Peuvent stocker des données arbre binaire sur chaque nœud. Il ya des avantages et des inconvénients pour chacun. J'ai remarqué que certains sites montrent exactement les mêmes arbre binaire que les arbres B +. En général, sont mieux à un arbre binaire contenant les données réelles et les arbres B + sont beaucoup plus efficaces que les indices.