Master 2, Bases de données avancées, année 2021

Cours 3. Les Bases de données orientées documents

Dans le cours précédant, nous avons vu les key-value store et comment la simplicité de ces derniers leur permet d’être distribué efficacement à moindre coût.

Une des limitations de ces systèmes est l’absence d’indexation du contenus. Ainsi, il est impossible de faire une recherche sur toutes les valeurs de la base de données ayant une certaine propriété.

Au vu de la simplicité du modèle de donnée, cette absence s’explique très bien: la plupart des mécanismes de recherches nécessite une forme d’introspections de la valeur et donc un système de typage et des types plus complexes que simplement des suites d’octets.

Redis est donc un cas intermédiaire, puisque les valeurs sont typées, mais pas indexées.

De nombreuse application offre des API sous forme de clef/valeur où les valeurs sont des documents JSON.

Par exemple, si on prend un Tweet

{
  "created_at": "Thu Apr 06 15:24:15 +0000 2017",
  "id_str": "850006245121695744",
  "text": "1\/ Today we\u2019re sharing our vision for the future of the Twitter API platform!\nhttps:\/\/t.co\/XweGngmxlP",
  "user": {
    "id": 2244994945,
    "name": "Twitter Dev",
    "screen_name": "TwitterDev",
    "location": "Internet",
    "url": "https:\/\/dev.twitter.com\/",
    "description": "Your official source for Twitter Platform news, updates & events. Need technical help? Visit https:\/\/twittercommunity.com\/ \u2328\ufe0f #TapIntoTwitter"
  },
  "place": {
  },
  "entities": {
    "hashtags": [
    ],
    "urls": [
      {
        "url": "https:\/\/t.co\/XweGngmxlP",
        "unwound": {
          "url": "https:\/\/cards.twitter.com\/cards\/18ce53wgo4h\/3xo1c",
          "title": "Building the Future of the Twitter API Platform"
        }
      }
    ],
    "user_mentions": [
    ]
  }
}

Le document contient pleins d’information ainsi des dictionnaires imbriqués (avec des listes) et une profondeur non négligeable.

Pour ce type de document, avec des méta-données, parfois profondes, on ne veut pas stocker tous le document comme un texte car il faut alors retravailler dans le middleware le document pour ne retourner que la valeur souhaitée. Ce travail supplémentaire compliqué l’architecture et diminue fortement les performances.

Les bases de données orientées documents sont donc construites pour permettre de stocker des documents (potentiellement profond), de les interroger et de les indexer. Leur paradigme étend ainsi celui des simples key-value store, principalement par la richesse des requêtes et des indexes que l’on peut exécuter sur les documents.

Documents et Vues sur des collections de documents

Dans une application Web, les documents structurées peuvent avoir deux usages:

Un usage d’échange d’information
Un usage de stockage d’information

Les bases de données classiques peuvent tout à fait retourner un document comme réponse d’une requête, ce qui simplifie grandement la communication avec le middleWare et avec le front-end.

On a vu que les bases de données orientées documents les utilisent également comme unité de donnée stockée. On a donc des collections de documents que l’on souhaite interroger.

Un exemple simple

Le gouvernement fourni un API simple pour interrogé des information géographique. Cette API stock des documents

La commande curl 'https://geo.api.gouv.fr/communes/59350' retourne le document

{
  "nom": "Lille",
  "code": "59350",
  "codeDepartement": "59",
  "codeRegion": "32",
  "codesPostaux": [
    "59800",
    "59000",
    "59260",
    "59777",
    "59160"
  ],
  "population": 232440
}

Ils proposent des mécanismes de recherche de communes selon différents paramètres:

Par exemple, la recherche par nom en triant par population:

curl 'https://geo.api.gouv.fr/communes?nom=Lille&boost=population&limit=2'

[
  {
    "nom": "Lille",
    "code": "59350",
    "codeDepartement": "59",
    "codeRegion": "32",
    "codesPostaux": [
      "59800",
      "59000",
      "59260",
      "59777",
      "59160"
    ],
    "population": 232440,
    "_score": 1.7772017384094794
  },
  {
    "nom": "Lillers",
    "code": "62516",
    "codeDepartement": "62",
    "codeRegion": "32",
    "codesPostaux": [
      "62190"
    ],
    "population": 10058,
    "_score": 0.5923008593838054
  }

Ou de faire une recherche multi-critère:

curl 'https://geo.api.gouv.fr/communes?nom=Lille&boost=population&limit=2'

[
  {
    "nom": "Lille",
    "code": "59350",
    "codeDepartement": "59",
    "codeRegion": "32",
    "codesPostaux": [
      "59800",
      "59000",
      "59260",
      "59777",
      "59160"
    ],
    "population": 232440,
    "_score": 1.7772017384094794
  },
  {
    "nom": "Lillers",
    "code": "62516",
    "codeDepartement": "62",
    "codeRegion": "32",
    "codesPostaux": [
      "62190"
    ],
    "population": 10058,
    "_score": 0.5923008593838054
  }
]

Ou faire une recherche par position géographique (ici le bâtiment M5):

curl 'https://geo.api.gouv.fr/communes?lat=50.63158972205492&lon=3.0752506776080466'

{
  "nom": "Villeneuve-d'Ascq",
  "code": "59009",
  "codeDepartement": "59",
  "codeRegion": "32",
  "codesPostaux": [
    "59650",
    "59491",
    "59493"
  ],
  "population": 62358
}

Une présentation de `CouchDB`

Une base de données orienté Documents Json
ACID
Distribuée avec un mécanisme qui favorise la disponibilité sur la cohérence

Les requêtes prennent la forme de vues sur les documents après une application d’une fonction sur chaque document de la collection.

Structure de données pour la recherche

Les tables de hachages sont très efficaces pour des mécanismes de clef-valeurs mais ne permettent pas des mécanismes de recherches plus riches.

Le mécanisme d’indexation principal est l’arbre équilibré et ses variantes. Il permet de répondre à des requêtes plus complexes.

Un peu de lecture.

Recherche dans un tableau ordonnées

On suppose qu’on a une collection d’éléments possiblement infinie \(E\), et un ordre total sur ces éléments, fourni par une fonction extérieur dont on suppose l’évaluation peu couteuse (en \(\mathcal{O}(1)\)).

Un tableau ordonnée permet de retrouver rapidement si un élément est-il présent dans le tableau (dichotomie, \(\mathcal{O}(\log n)\)) et si c’est le cas de retourner son indice ou l’indice de la plus petite valeur plus grande.

Grâce à cette information, et parce que le tableau est ordonné il est possible de récupérer l’information de tous les éléments plus grands qu’une valeur donnée.

En base de donnée, on s’intéresse à retrouver ce type d’information dans un contexte d’ajout et suppression de données. La problématique devient donc: Comment maintenir un tableau ordonné. Pour stocker un tableau, il existe essentiellement de type de mécanismes:

Les listes chainées (et les variantes, doublement chainée, ect)
Une allocation de mémoire contigüe

La première solution permet facilement d’ajouter et supprimer des données, par un jeu de modification de pointeurs simple mais ne permet pas un accès à n’importe quelle cellule en en temps constant. La seconde solution permet un accès à n’importe quelle cellule en temps constant, mais ne permet pas une insertion de donnée en temps constant.

Pour contourner ces problématiques, on présente usuellement les arbres binaires de recherches comme une solution on stock les données dans un arbres de recherches:

Les nœuds internes contiennent des éléments
Un nœud fils gauche est plus petit
Un nœud fils droite est plus grand.

La recherche d’information dans un nœud binaire est au pire cas la profondeur de l’arbre. Des stratégies d’auto-équilibrage de l’arbre, pour que sa profondeur soit en \(O(\log n)\) permettent de garantir ainsi une complexité en insertion et en recherche de \(O(\log n)\).

Quelques exemples de stratégies d’équilibrages:

Localité de données

Lorsqu’on réalise un arbre binaire de recherche auto-équilibré, on ajoute de nouveaux éléments par des mécanismes de pointeurs au fur à mesure de leur arrivé. Cela signifie que l’ordre des éléments dans l’arbre et dans la mémoire ne sont pas reliés. On dit que alors que la structure de donnée ne respecte pas la localité des données.

En base de données, si la structure de données est écrite sur disque, la non localité est très problématique.

Pour les disques dures rotatifs elle entraine un surcout immédiat très gros: chaque accès à l’arbre nécessite des opérations mécaniques pour ajuster la tête de lecture et donc une latence particulière. Au contraire, les accès séquentiels sont très efficaces. Il est donc intéressant d’adapter les arbres de recherche pour tirer partie autant que possible de la rapidité des accès séquentiel.
Même pour les disques dure SSD (non rotatif), les accès aléatoire sont peu couteux mais l’unité d’accès n’est pas le pointeur. C’est la page système. Récupérer toute une page système (4ko) pour un pointeur (8octets) n’est pas optimal en terme de bande passante du disque.

Les structures de données arborescente vont ainsi être désigné pour tirer partie au maximum de la localité des données et des accès aux disques dure physique sous forme de pages systèmes.

Les \(B\)-tree

Les B-tree sont un type d’arbre de recherche équilibré non binaire. Chaque nœud contient un tableau contigüe. La taille de ce tableau, plus les métas information nécessaires tiennent exactement dans une page système. Ainsi, pour un système classique, il est possible de stocker 64 valeurs de manière contigüe dans une seul page. Article wikipedia sur le sujet.

Recherche d’un élément \(O(\log n)\), dichotomie classique
Insertion d’un élément \(O\log n)\), insertion de l’élément dans la feuille adéquate. Si la feuille est rempli, on la scinde en deux et insère la médiane dans la feuille du dessus.
Suppression en \(O(\log n)\), on supprime l’élément et on s’arrange pour maintenir l’arbre équilibré via des mécanismes de modification structurelle de l’arbre.

Les \(B^+\)-tree

Si on ajoute une information de frères sur les feuilles, afin d’accélérer les range query (trouver toutes les valeurs entre deux valeurs).

Compiled the: dim. 07 janv. 2024 23:19:18 CET