Où l'index clusterisé et non clusterisé de l'arbre B + sont sauvegardés?

Question

Actuellement, je lis environ B+ Tree bases, et est devenu confus concernant l'allocation d'espace pour l'index cluster et non cluster.

Lorsque nous créons un index clusterisé sur B+ tree, l'index est stocké dans la mémoire principale et les feuilles contiennent les pointeurs de données vers les blocs réels. Les blocs sont stockés dans des disques et les blocs contiennent un enregistrement.

• En général, l'index ordonné en clusters est créé sur la touche
• primaire Il ne peut y avoir qu'un seul index ordonné en clusters

Supposons maintenant que nous avons une table (id, nom, classe) et j'ai créé deux index non clusterisés sur name et class. Mon doute est où sera l'index non clusterisé sera stocké? et comment la recherche sera effectuée pour un query comme

select id, name, class from table where id = 3, name='Leo' and class='10' 

Mon hypothèse:

• Depuis champ id est la clé primaire pour la première utilisation de l'index cluster sera id = 3
• Maintenant, en utilisant l'index non clusterisé sur name et class, nous trouverons les champs restants

Pensez-vous que mon hypothèse est bonne? Pourriez-vous élaborer davantage sur le stockage de l'index clusterisé? Est-ce que l'index (groupé et non groupé forme un arbre n-aire?). Je ne suis pas capable de visualiser à la fois l'index clusterisé et non clusterisé ensemble.

Answer 1

Je parle spécifiquement InnoDB ...

Le PRIMARY KEY est (comme vous dites) avec les données en cluster. Le BTree entier pour cela (données + PK) est stocké dans un ensemble de blocs sur le disque (pas 'mémoire principale'). Les nœuds 'feuille' contiennent toutes les colonnes.

Une clé secondaire est une référence distincte. Structurellement les deux BT sont les mêmes à l'exception de ce qui est dans les nœuds de feuilles. Pour une clé secondaire, une copie du PRIMARY KEY est placée dans les nœuds feuille. Par conséquent, lorsque vous recherchez une ligne ("requête ponctuelle") à l'aide d'un index secondaire, il existe deux niveaux d'exploration BTree - un pour l'index secondaire et un secondaire pour le PK.

Tous les blocs sont 'mis en cache' dans le 'buffer_pool', donc ils sont parfois dans la mémoire principale, mais sont toujours conservés (tôt ou tard) sur le disque. (Le journal des transactions, etc) assure que "plus tard" ne viole pas la règle que les données persistent toujours.)

Vos deux photos sont un bon début. Cependant ...

• Les nœuds non-feuille sont liés ensemble (comme vous le montrez), mais ils ne sont pas nécessairement adjacents sur le disque. Lors de l'insertion d'une nouvelle ligne (ou d'une nouvelle entrée d'index), un bloc peut être "divisé" en raison de sa taille.Cela conduit à la dissémination des blocs autour du disque.
• Les nœuds de feuille sont également liés entre eux, mais pourraient être dispersés.
• Pour unclustered, eh bien, vous suggère de commencer plus, compte tenu de la question PK, etc.

Ce que vous devez savoir à un niveau plus élevé que les images tentent de transmettre:

• une requête ponctuelle fore vers le bas un btree
• une recherche secondaire doit faire 2 bas de forage
• scans « Range » - soit des données, ou d'un indice - sont très efficaces car ils scannent par un bloc et puis passez à la (logiquement) bloc suivant via un lien bidirectionnel entre les blocs au niveau inférieur. Par conséquent, c'est vraiment un arbre B +, pas seulement un BTree.
• (plus sur la gamme) WHERE clustered_key BETWEEN ... est très efficace
• (plus sur la gamme) WHERE secondary_key BETWEEN ... est très efficace pour trouver les PK valeurs dont il a besoin, mais se transforme alors en un tas de (potentiellement) des requêtes ponctuelles aléatoires.
• Tous les blocs sont à peu près équivalents pour la mise en cache. Mais (évidemment?) Les noeuds non-feuilles ont tendance à vivre dans le cache à cause de l'algorithme "moins récemment utilisé". (Je laisse de côté beaucoup de détails.)
• Il ne peut y avoir qu'un seul index cluster. (Sauf si vous êtes prêt à dupliquer toutes les données Ceci a été fait dans un couple de moteurs autres que InnoDB.)
• Un bloc contient autant d''enregistrements' (données ou index ou non-feuille) que possible moment - de 1 à des centaines.
• Par défaut, un bloc est de 16 Ko. (Et pas facile à changer.)
• Avec innodb_file_per_table = ON, tous les BTrees d'une table donnée vivent dans un seul 'tablespace' .ibd. Avec innodb_file_per_table = OFF, tous les BTrees de toutes les tables se trouvent dans un seul 'tablespace' global appelé ibdata1. (Encore une fois, plus simplifié.)

maintenant pour MyISAM:

• Les données pour une vie de table dans un fichier (.MYD).
• Tous les index (y compris la PRIMARY KEY) pour une table résident dans un fichier (.MYI)
• Tous les index sont des BTrees. (Les données ne le sont pas.)
• Les nœuds feuille d'un «point» d'index dans le fichier de données.
• Les blocs d'index sont 1 Ko.
• Le fichier de données est simplement un flux à accès aléatoire.

(Il y a beaucoup plus de détails.)