Ma connaissance des bases de données et du SQL est basée dans la plupart des cours universitaires. Quoi qu'il en soit, j'ai passé quelques mois (près d'un an) dans une entreprise, où je travaillais avec des bases de données.
J'ai lu quelques livres et j'ai pris part à quelques formations sur les bases de données telles que MySQL, PostgreSQL, SQLite, Oracleet aussi peu nonSQL dbde tels nous MongoDB, Redis, ElasticSearchetc.
Aussi bien que je l'ai dit, je suis débutant, avec beaucoup de manque de connaissances mais aujourd'hui, quelqu'un a dit quelque chose, ce qui est totalement contre les connaissances de mon débutant.
Laissez-moi expliquer. Prenons la base de données SQL et créons une table simple Personavec quelques enregistrements à l'intérieur:
id | name | age
-----------------
1 | Alex | 24
2 | Brad | 34
3 | Chris | 29
4 | David | 28
5 | Eric | 18
6 | Fred | 42
7 | Greg | 65
8 | Hubert | 53
9 | Irvin | 17
10 | John | 19
11 | Karl | 23Maintenant, c'est la partie sur laquelle je voudrais me concentrer - idc'est la INDEX.
Jusqu'à présent, je pensais que cela fonctionnait de cette façon: quand une table est en cours de création, elle INDEXest vide. Lorsque INDEXj'ajoute un nouvel enregistrement à ma table, le est recalculé en fonction de certaines alghortims. Par exemple:
Regroupement un par un:
1 ... N
N+1 ... 2N
...
XN+1 ... (X+1)Ndonc, pour mon exemple avec size = 11 elementset N = 3ce sera comme ça:
id | name | age
-----------------
1 | Alex | 24 // group0
2 | Brad | 34 // group0
3 | Chris | 29 // group0
4 | David | 28 // group1
5 | Eric | 18 // group1
6 | Fred | 42 // group1
7 | Greg | 65 // group2
8 | Hubert | 53 // group2
9 | Irvin | 17 // group2
10 | John | 19 // group3
11 | Karl | 23 // group3Donc, lorsque j'utilise une requête, SELECT * FROM Person WHERE id = 8il fera un calcul simple 8 / 3 = 2, nous devons donc rechercher cet objet dans group2, puis cette ligne sera retournée:
8 | Hubert | 53
Cette approche fonctionne dans le temps O(k)où k << size. Bien sûr, un algorithme pour organiser les lignes en groupes est certainement beaucoup plus compliqué, mais je pense que cet exemple simple montre mon point de vue.
Alors maintenant, je voudrais présenter une autre approche, qui m'a été montrée aujourd'hui.
Reprenons ce tableau:
id | name | age
-----------------
1 | Alex | 24
2 | Brad | 34
3 | Chris | 29
4 | David | 28
5 | Eric | 18
6 | Fred | 42
7 | Greg | 65
8 | Hubert | 53
9 | Irvin | 17
10 | John | 19
11 | Karl | 23Maintenant, nous créons quelque chose de similaire à Hashmap(en fait, c'est littéralement une carte de hachage) qui correspond idà une addressligne avec cet identifiant. Disons:
id | addr
---------
1 | @0001
2 | @0010
3 | @0011
4 | @0100
5 | @0101
6 | @0110
7 | @0111
8 | @1000
9 | @1001
10 | @1010
11 | @1011Alors maintenant, lorsque j'exécute ma requête: SELECT * FROM Person WHERE id = 8
il sera mappé directement id = 8à l'adresse en mémoire et la ligne sera retournée. Bien sûr, la complexité de cela est O(1).
Alors maintenant, j'ai quelques questions.
1. Quelles sont les aventures et les inconvénients des deux solutions?
2. Lequel est le plus populaire dans les implémentations de base de données actuelles? Peut-être que différents dbs utilisent des approches différentes?
3. Existe-t-il dans des dbs nonSQL?
Merci d'avance
COMPARAISON
| B-tree | Hash Table
----------------------------------------------------
---------------- one element -------------------
----------------------------------------------------
SEARCHING | O(log(N)) | O(1) -> O(N)
DELETING | O(log(N)) | O(1) -> O(N)
INSERTING | O(log(N)) | O(1) -> O(N)
SPACE | O(N) | O(N)
----------------------------------------------------
---------------- k elements -------------------
----------------------------------------------------
SEARCHING | k + O(log(N)) | k * O(1) -> k * O(N)
DELETING | k + O(log(N)) | k * O(1) -> k * O(N)
INSERTING | k + O(log(N)) | k * O(1) -> k * O(N)
SPACE | O(N) | O(N)N - nombre d'enregistrements
Ai-je raison? Qu'en est-il du coût de reconstruction de l'arborescence B et de la table de hachage après chaque insertion / suppression ? En cas d' arbre B, nous devons changer certains pointeurs, mais en cas d' arbre B équilibré, il faut plus d'efforts. De plus, dans le cas d'une table de hachage, nous devons faire peu d'opérations, surtout si notre opération génère des conflits .
O(1)vous a bien compris! Dans un premier temps, il semble que vous décriviez un index B-tree mais vous avez un malentendu. Il n'y a pas de calcul (division par 3 ou quoi que ce soit), c'est plus complexe car l'arbre a plus de niveaux (c'est un arbre, il a de grandes, petites, petites branches, ..., et puis laisse :)Of course, an alghoritm to organise rows in groups is for sure much more complicated but I think this simple example shows my point of view.Bien sûr, je sais que c'est beaucoup plus compliqué. Alors enfin, quand je dis dans mon codeINDEXlaquelle de mes solutions ( 1ère ou 2ème ) est plus proche de cette vraie? Et qu'en est-il du temps nécessaire pour accéder à un enregistrement basé surINDEX. C'est vraiment çaO(1)? Avec l'index B-tree, cela ressemble beaucoupO(log2(N)). Ai-je raison?Réponses:
Vous décrivez essentiellement un index B-tree et un index de hachage. Ils ont tous les deux une place, mais les deux conviennent le mieux à des emplois différents.
Avantages et inconvénients
Les index B-tree (et B + -tree) sont généralement équilibrés. Cela signifie que la recherche d'une valeur prendra toujours le même temps, peu importe où elle se trouve dans l'arbre (O (log n)). Généralement, le nombre de niveaux dans l'arborescence est limité, il a donc tendance à devenir "plus large" et non "plus profond". Pour les petits ensembles de données, le coût de la maintenance et de l'utilisation de l'arborescence B peut cependant être plus que la simple lecture de toutes les lignes. Les index B-tree conviennent aux grands ensembles de données, aux ensembles de données à faible sélectivité ou aux ensembles de données où vous avez l'intention de sélectionner une plage d'objets et non un seul objet.
Les tables de hachage sont idéales pour les petits ensembles de données. Les index de hachage ont un nombre prédéfini de compartiments de hachage, selon l'algorithme de hachage utilisé. En effet, un algorithme de hachage donné ne peut produire que autant de hachages uniques, il ne devient donc "plus profond" que "plus large". Une fois que le moteur de base de données a trouvé le bon compartiment, il parcourt ensuite tous les objets de ce compartiment pour trouver celui que vous souhaitez. Avec de petits ensembles de données hautement sélectifs, chaque compartiment contient un très petit nombre d'objets et est résolu assez rapidement. Avec des ensembles de données plus volumineux, les compartiments deviennent beaucoup plus encombrés. Donc, si l'objet dont vous avez besoin se trouve dans un petit seau ou est près du début du seau, il revient assez rapidement. Si c'est au bout d'un grand seau, cela prend plus de temps. L'indice n'est pas équilibré, les performances sont donc comprises entre O (1) et O (n).
Popularité
En général, j'ai rencontré le plus d'arbres B. Les index bitmap sont également une autre option pour les valeurs avec une faible cardinalité (pensez aux booléens ou peut-être au genre). Cela va varier en fonction de votre moteur de base de données quant aux types d'index disponibles.
NoSQL
Les bases de données NoSQL supportent définitivement les index. La plupart prennent en charge B-tree ou une variante de B-tree. La plupart semblent également prendre en charge les index hachés.
la source
Quelles sont les aventures et les inconvénients des deux solutions? La deuxième solution ne peut pas effectuer de balayage de plage. Il est idéal pour sélectionner un seul ID. Mais que se passe-t-il si vous voulez les identifiants 3 à 8? Il doit saisir tous les enregistrements individuels qui, dans le monde réel, ne sont pas uniquement des enregistrements O (1) * 6 à récupérer. Dans une grande base de données de production avec un index HashMap, vous obtiendrez des enregistrements sur différentes pages, vous obligeant à frapper le disque et à lire six pages différentes en mémoire.
Dans une structure B-Tree, comme la façon dont votre première situation serait réellement implémentée, les identifiants seraient séquentiels sur le disque et une seule page contiendrait probablement les identifiants 3 à 8, ce qui augmenterait la vitesse des analyses de plage rendrait l'accès individuel O (log n) .
Lequel est le plus populaire dans les implémentations de bases de données actuelles? Peut-être que différents dbs utilisent des approches différentes? Je n'ai pas une grande expérience dans de nombreuses bases de données différentes. Je sais que Sql Server utilise principalement B-Trees, mais SQl 2014 a de nouveaux index de hachage que vous pouvez utiliser sur certaines tables. J'entends beaucoup de bases de données No Sql et de bases de données de mise en cache basées sur la récupération d'enregistrements individuels utilisent également des index de hachage. Cela est logique pour les caches, car vous voulez l'enregistrement pour l'utilisateur A et n'avez pas besoin d'analyses de plage.
Existe-t-il dans des dbs nonSQL? Oui. En jetant un rapide coup d'œil à la documentation de création d'index pour postgressql, je vois qu'elle prend en charge les index Hash et B-Tree ainsi que quelques autres.
la source