contour
Comme il a déjà introduit le contenu relatif TREE-B, de sorte que son architecture ici n'introduit, surtout du point de vue du disque IO, pourquoi nous devrions regarder le B-tree.
concepts associés
Cette structure de données B-arbre est souvent utilisé pour mettre en uvre l'indice de base de données, car il est recherche plus efficace.
1, le disque IO et de pré-lecture
Lecture de disque comptent sur un mouvement mécanique, divisé le temps de recherche, la latence de rotation, le temps de transmission en trois parties, la somme de ces trois parties de temps est un disque de temps IO, environ 9 ms. Le coût est cent mille fois l'accès mémoire ;
Il est à cause du disque IO est une opération très coûteuse, le système d'exploitation informatique optimisé pour ceci: pré-lecture, chaque fois IO, non seulement pour traiter les données de chargement de disque en cours dans la mémoire, mais aussi les données adjacentes est également chargé dans la un tampon de mémoire. Parce que la pré-lecture Justification locale: Lorsque l'accès aux données d'une adresse, les données adjacentes seront rapidement accessibles. Chaque données en temps disque IO lu ce que nous appelons une (page). La taille d'un système d'exploitation, généralement à 4k ou 8k. Cela signifie que la page est lue dans les données, quand il y avait en fait un disque IO.
2 et comparatif B-Tree est un arbre de recherche binaire
La complexité temporelle de requête arbre de recherche binaire est O (logN), pour trouver le plus rapide et moins nombre de comparaisons, puisque la performance a été si bon, mais pourquoi est réalisé à l'aide des index B-Tree au lieu d'un arbre de recherche binaire, le facteur clé est le disque IO fois.
Indice de base de données est sur le disque, lorsqu'une grande quantité de données dans le tableau, la taille de la mémoire d'augmentation de l'indice suivi atteindre plusieurs G ou plus. Lorsque nous utilisons la requête d'index, il est impossible d'indexer tous chargés en mémoire, ne peut charger une d'une page par disque, où la page disque sur l'arbre d'index de noeud correspondant.
Le premier discours suivant sur l'arbre binaire
arbre binaire d'abord,
Regardez d'abord le nombre de disque lorsque lookups arbre binaire IO: considérer la définition d'une hauteur d'arbre binaire est 4 pour trouver une valeur de 10:
Le premier disque IO:
La deuxième disque IO
Le troisième disque IO:
Quatrième disque IO:
processus de recherche d'arbre binaire du point de vue, le nombre de la hauteur des arbres et des IO est 4, Ainsi, le nombre de disque IO pire des cas est déterminé par la hauteur de l'arbre.
Du point de vue de l'analyse ci-dessus, réduire le nombre de disque IO doit être la hauteur de l'arbre comprimé, de sorte que l'arbre longiligne essayer de devenir arbre trapu, donc B-Tree est né dans ce contexte.
Deux, B-Tree
B-tree
m ordre B-Tree répondent aux critères suivants:
1, chaque noeud a la plus grande sous-arborescence m
2, il y a au moins deux sous-arbre racine
3, un noeud de branchement comporte au moins m / 2 unités de sous arbre (sauf le noeud racine et les noeuds de feuille sont des nuds de branchement)
4, tous les noeuds de feuille sont dans la même couche, chaque noeud peut avoir jusqu'à m-1 ième clé, et agencé dans l'ordre croissant
Suit un troisième ordre B-tree, l'élément de processus de recherche 21 a été observé:
Le premier disque IO:
Le second disque IO:
Il y a une correspondance de la mémoire 3 et 12, respectivement, avec le rapport de
Le troisième disque IO:
Il y a une correspondance de la mémoire, respectivement, 14 et 21 que
De la découverte de la découverte, que le nombre binaire B-tree et le nombre de fois que le disque IO avec peu différent, il semble n'y a aucun avantage.
Mais un examen plus attentif constatera que, L'alignement se fait en mémoire, il est pas lié au disque IO, la consommation négligeable. D'autres espèces Node B peuvent être stockés dans un grand nombre de clés (numéro d'ordre déterminé par l'arbre).
Le même nombre de clé générée dans le noeud B-tree beaucoup moins que dans les noeuds de l'arbre binaire, le numéro de noeud de fois la différence de phase est équivalent au disque IO. Après cela, atteint un certain montant, la différence de performance a commencé à se désagréger.
Trois, B arbre nouveau
De nouveaux éléments sur la base de seulement 4, il devrait être compris entre 3 et 9:
Quatrièmement, suppression B-tree
Suppression des éléments 9:
Cinq, arbre B +
Fin arbre B, arbre B + viennent à parler, et le B + structure arborescente est similaire, mais plus sur les performances des requêtes, ayant les caractéristiques suivantes:
- Il y k ème noeud de l'arbre contient k éléments intermédiaires (arbre B est des éléments k-1), chacun des éléments de données ne sont pas enregistrée, l'index utilisé uniquement, toutes les données stockées dans le noeud de feuille;
- noeud feuille contient tous les éléments d'information, en fonction de la taille des mots-clés sorte de gauche à droite;
- Bien que l'élément de noeud intermédiaire existe dans le nud enfant, le nud enfant est le plus grand élément.
La figure LIBÉRATION exemple suivant:
Comme on peut le voir sur la figure, les nuds d'arbre B + et feuilles noeuds déclarations de données en double ici intermédiaires, Enregistrer noeuds intermédiaires uniquement des données d'arbre sous-sous-aiguille, et non pas de données réelles, moins d'espace de stockage noeud intermédiaire.
Pendant ce temps, avec des pointeurs entre les nuds feuilles, en d'autres termes, les noeuds feuilles forment une liste liée , Toutes les données sont stockées dans.
Pourquoi cette conception, par rapport à B-tree à quoi bon?
Tout d'abord, étant donné que le noeud intermédiaire de la borne B + sous-aiguille de l'arbre est seulement la mémorisation de données de maximum et sous-arborescence de sous-arbre, l'espace lui-même est faible, il est possible de loger l'élément plus de noeud, à savoir le même cas de données, l'arbre B + sera plus B-arbres « chunky » et donc l'efficacité plus rapide requête.
En second lieu, trouver une gamme de données, uniquement dans le noeud feuille peut parcourir la liste B + arbre, ne pas comme la séquence traversal B-tree un par un comme la comparaison de la taille. En résumé, B + avantage des arbres est:
résumé
Insérer ou des éléments de suppression provoqueront la réaction de fission du noeud se produit, parfois très gênant, mais à cause de ce juste laisser le B-arbre peut toujours garder l'équilibre multiple, c'est un propres avantages B-arbre: l'auto-équilibrage; B-arbre est principalement utilisé dans le fichier systèmes et une partie de l'indice de base de données, comme MongoDB, donc la plupart index courant de base de données relationnelle est B + implémentés à l'aide d'arbres.
B-tree: + équilibre réseau ordonné plusieurs arbres;
arbre B +: un réseau ordonné d'équilibre à chaînes multiples + arbre;
Devops et plus tard partageront les aspects DBA plus de contenu, des amis intéressés peuvent regarder -
