Comment les bases de données stockent-elles les valeurs de clé d'index (sur disque) pour les champs de longueur variable?

Le contexte

Cette question concerne les détails d'implémentation de bas niveau des index dans les systèmes de base de données SQL et NoSQL. La structure réelle de l'index (arbre B +, hachage, SSTable, etc.) n'est pas pertinente car la question concerne spécifiquement les clés stockées à l'intérieur d'un seul nœud de l'une de ces implémentations.

Contexte

Dans les bases de données SQL (par exemple MySQL) et NoSQL (CouchDB, MongoDB, etc.), lorsque vous créez un index sur une colonne ou un champ de données de document JSON, ce que vous faites réellement faire à la base de données est de créer essentiellement une liste triée de tous ces valeurs ainsi qu'un fichier décalé dans le fichier de données principal où réside l'enregistrement correspondant à cette valeur.

(Par souci de simplicité, je peux être en train de balayer à la main d'autres détails ésotériques d'impliques spécifiques)

Exemple SQL classique simple

Considérons une table SQL standard qui a une clé primaire int 32 bits simple sur laquelle nous créons un index, nous nous retrouverons avec un index sur disque des clés entières triées et associées à un décalage 64 bits dans le fichier de données où l'enregistrement vit, par exemple:

id   | offset
--------------
1    | 1375
2    | 1413
3    | 1786

La représentation sur disque des clés de l'index ressemble à ceci:

[4-bytes][8-bytes] --> 12 bytes for each indexed value

En respectant les règles de base standard sur l'optimisation des E / S de disque avec les systèmes de fichiers et les systèmes de base de données, disons que vous stockez les clés dans des blocs de 4 Ko sur le disque, ce qui signifie:

4096 bytes / 12 bytes per key = 341 keys per block

En ignorant la structure globale de l'index (arborescence B +, hachage, liste triée, etc.), nous lisons et écrivons des blocs de 341 clés à la fois dans la mémoire et revenons sur le disque si nécessaire.

Exemple de requête

En utilisant les informations de la section précédente, supposons qu'une requête arrive pour "id = 2", la recherche d'index DB classique se déroule comme suit:

1. Lire la racine de l'index (dans ce cas, 1 bloc)
2. Recherche binaire dans le bloc trié pour trouver la clé
3. Obtenez le décalage du fichier de données par rapport à la valeur
4. Recherchez l'enregistrement dans le fichier de données en utilisant le décalage
5. Renvoyer les données à l'appelant

Configuration de la question ...

Ok, c'est ici que la question se pose ...

L'étape n ° 2 est la partie la plus importante qui permet à ces requêtes de s'exécuter en temps O (logn) ... les informations doivent être triées, MAIS vous devez être capable de parcourir la liste de manière rapide ... plus en particulier, vous devez être capable de passer à volonté à des décalages bien définis pour lire la valeur de la clé d'index à cette position.

Après avoir lu dans le bloc, vous devez pouvoir sauter immédiatement à la 170e position, lire la valeur de clé et voir si ce que vous recherchez est GT ou LT cette position (et ainsi de suite et ainsi de suite ...)

La seule façon de pouvoir sauter les données dans le bloc comme cela est si les tailles des valeurs de clé étaient toutes bien définies, comme notre exemple ci-dessus (4 octets puis 8 octets par clé).

QUESTION

Ok, voici donc où je suis coincé avec une conception d'index efficace ... pour les colonnes varchar dans les bases de données SQL ou plus spécifiquement, les champs de forme totalement libre dans les bases de données de documents comme CouchDB ou NoSQL, où tout champ que vous souhaitez indexer peut être n'importe lequel longueur comment avez - vous mettre en œuvre les valeurs clés qui sont à l' intérieur des blocs de la structure d'index que vous construisez vos indices sur?

Par exemple, supposons que vous utilisez un compteur séquentiel pour un ID dans CouchDB et que vous indexez les tweets ... vous aurez des valeurs qui vont de "1" à "100 000 000 000" après quelques mois.

Supposons que vous construisiez l'index sur la base de données le jour 1, lorsqu'il n'y a que 4 tweets dans la base de données, CouchDB pourrait être tenté d'utiliser la construction suivante pour les valeurs de clé à l'intérieur des blocs d'index:

[1-byte][8-bytes] <-- 9 bytes
4096 / 9 = 455 keys per block

À un moment donné, cela se casse et vous avez besoin d'un nombre variable d'octets pour stocker votre valeur de clé dans les index.

Le point est encore plus flagrant si vous décidez d'indexer un champ de longueur vraiment variable comme un "tweet_message" ou quelque chose.

Les clés étant elles-mêmes de longueur totalement variable et la base de données n'ayant aucun moyen de deviner intelligemment une certaine "taille de clé maximale" lors de la création et de la mise à jour de l'index, comment ces clés sont-elles réellement stockées à l'intérieur des blocs représentant les segments des index dans ces bases de données ?

Évidemment , si vos clés sont de taille variable et que vous lisez dans un bloc de clés, non seulement vous ne savez pas combien de clés sont en fait dans le bloc, mais vous ne savez pas comment sauter au milieu de la liste pour faire un fichier binaire chercher sur eux.

C'est là que je suis tout déclenché.

Avec les champs de type statique dans les bases de données SQL classiques (comme bool, int, char, etc.), je comprends que l'index peut simplement prédéfinir la longueur de clé et s'y tenir ... mais dans ce monde de magasins de données de documents, je suis perplexe sur la façon dont ils modélisent efficacement ces données sur disque de telle sorte qu'elles puissent encore être analysées en temps O (logn) et apprécieraient toute clarification ici.

Veuillez me faire savoir si des clarifications sont nécessaires!

Mise à jour (réponse de Greg)

Veuillez voir mes commentaires joints à la réponse de Greg. Après une semaine de recherches supplémentaires, je pense qu'il est vraiment tombé sur une suggestion merveilleusement simple et performante selon laquelle la pratique est très facile à mettre en œuvre et à utiliser tout en offrant de grandes performances en évitant la désérialisation des valeurs clés qui ne vous intéressent pas.

J'ai examiné 3 implémentations de SGBD distinctes (CouchDB, kivaloo et InnoDB) et toutes gèrent ce problème en désérialisant le bloc entier dans la structure de données interne avant de rechercher les valeurs dans leur environnement d'exécution (erlang / C).

C'est ce que je trouve si brillant dans la suggestion de Greg; une taille de bloc normale de 2048 aurait normalement 50 décalages ou moins, résultant en un très petit bloc de chiffres qui devrait être lu.

Mise à jour (inconvénients potentiels de la suggestion de Greg)

Afin de continuer au mieux ce dialogue avec moi-même, j'ai réalisé les inconvénients suivants à cela ...

1. Si chaque "bloc" contient des données de décalage, vous ne pouvez pas permettre que la taille du bloc soit ajustée dans la configuration plus tard, car vous pourriez finir par lire des données qui ne commencent pas correctement par un en-tête ou un bloc qui contenait plusieurs en-têtes.

2. Si vous indexez d'énormes valeurs de clé (disons que quelqu'un essaie d'indexer une colonne de char (8192) ou blob (8192)), il est possible que les clés ne tiennent pas dans un seul bloc et doivent être débordées sur deux blocs côte à côte. . Cela signifie que votre premier bloc aurait un en-tête de décalage et que le deuxième bloc commencerait immédiatement avec les données clés.

La solution à tout cela est d'avoir une taille de bloc de base de données fixe qui n'est pas réglable et de développer des structures de données de bloc d'en-tête autour d'elle ... par exemple, vous fixez toutes les tailles de bloc à 4 Ko (généralement la plus optimale de toute façon) et écrivez une très petite en-tête de bloc qui inclut le "type de bloc" au début. Si c'est un bloc normal, alors immédiatement après l'en-tête du bloc devrait être l'en-tête des décalages. S'il s'agit d'un type de «débordement», alors immédiatement après l'en-tête du bloc se trouvent les données de clé brutes.

Mise à jour (potentiel génial)

Après le bloc est lu comme une série d'octets et les décalages décodés; techniquement, vous pouvez simplement coder la clé que vous recherchez en octets bruts, puis faire des comparaisons directes sur le flux d'octets.

Une fois la clé que vous recherchez trouvée, le pointeur peut être décodé et suivi.

Un autre effet secondaire impressionnant de l'idée de Greg! Le potentiel d'optimisation du temps CPU ici est suffisamment grand pour que la définition d'une taille de bloc fixe en vaille la peine juste pour gagner tout cela.

Vous pouvez stocker votre index sous forme de liste de décalages de taille fixe dans le bloc contenant vos données clés. Par exemple:

+--------------+
| 3            | number of entries
+--------------+
| 16           | offset of first key data
+--------------+
| 24           | offset of second key data
+--------------+
| 39           | offset of third key data
+--------------+
| key one |
+----------------+
| key number two |
+-----------------------+
| this is the third key |
+-----------------------+

(eh bien, les données clés seraient triées dans un exemple réel, mais vous avez l'idée).

Notez que cela ne reflète pas nécessairement la façon dont les blocs d'index sont réellement construits dans une base de données. Il s'agit simplement d'un exemple de la façon dont vous pourriez organiser un bloc de données d'index où les données clés sont de longueur variable.