Spécification d'une structure d'index sous Oracle
Implantation d'un R-Tree

25/03/2005
Pascal Mazars <mazars@enst.fr>
Sébastien Jamon <jamon@enst.fr>
Xavier Lacot <lacot@enst.fr>
Mastère IDL - ENST

Introduction

Comme les méthodes d’indexation traditionnelles ne sont pas adaptées aux données multidimensionnelles, une nouvelle structure était nécessaire pour traiter les données spatiales. Un exemple d’application consiste à rechercher tous les agriculteurs qui possèdent un terrain dans une région particulière, ce qui pourrait se révéler utile dans le cas d’un projet de construction d’autoroute.

Oracle comprend une série de services d’extensibilité qui permettent l’intégration de nouveaux types de données et de nouveaux comportements spécifiés par le développeur afin d’adapter la base de données à un domaine spécifique d’utilisation. Le développeur a donc la possibilité de spécifier ses propres composants, les data cartridges, comme un type d’index R-Tree, une structure adaptée à l’indexation de données spatiales proposée en 1984 par Antonin Guttman.

Contents

  1. Introduction
  2. Plan
  3. Définition d’une Structure en R-Tree
    1. Recherche dans l’index
      1. Algorithme : Search
      2. Un exemple de recherche dans notre cas
    2. Insertion
      1. Algorithme : Insert
      2. Algorithme : ChooseLeaf
      3. Algorithme : AdjustTree
      4. Un exemple d’Insertion
    3. Suppression
      1. Algorithme : Delete
      2. Algorithme : FindLeaf
      3. Algorithme : CondenseTree
      4. Un exemple de Suppression
  4. Création d’un Index sous Oracle
    1. Méthodes de définition d’index
    2. Méthodes de maintenance de l’index
    3. Méthodes de parcours de l’index
  5. Mise en Oeuvre Pratique
  6. Bibliographie

Définition d’une Structure en R-Tree

Un R-Tree est similaire à un B-Tree dans son principe. Il s’agit d’un arbre dont les feuilles sont des pointeurs vers les données. Par contre, la structure de l’arbre et son évolution est conçue pour que la recherche spatiale soit la plus efficace possible, c’est-à-dire nécessite le parcours d’un petit nombre de nœuds de l’index.

Guttman a donné les algorithmes pour les opérations élémentaires sur les R-Tree, ces méthodes découlent de celles utilisées dans les B-Tree. Dans la suite, nous étudierons le cas d’un index bi-dimensionnel. Pour chaque nœud, le nombre d’entrées est compris entre m=2 et m=5.

exemple

Recherche dans l’index

La recherche dans un R-Tree est similaire à celle dans un B-Tree; l’arbre est parcouru depuis la racine mais comme plusieurs rectangles, dans lesquels nous devons chercher, se superposent (voir fig.). Il faudra parcourir tous ces rectangles.

Algorithme : Search

Soit T la racine du R-Tree. On recherche tous les noeuds tels que les rectangles se superposent avec le rectangle S correspondant à la zone de recherche spécifiée.

Un exemple de recherche dans notre cas

Exemple

Dans l’exemple, nous voulons trouver tous les étudiants qui sont dans leur 6ème semestre ou plus et qui ont obtenu 20 et 65 crédits.

R1 se superpose avec le rectangle de requête S, pas R2, donc nous cherchons dans R1. A l’étape suivante, R4 et R5 se superposent avec S; dans ces derniers nous retournons les points qui se trouvent à l’intérieur de S. De R4 nous récupérons C et de R5 nous récupérons E et K, d’où le résultat : {C,E, K}.

Insertion

Lorsqu’un nouveau tuple est inséré dans la base de données, un nouveau pointeur doit être rajouté dans le R-Tree. Si la capacité du nœud feuille est dépassé (node overflow), le nœud devra être coupé. Dans le cas où la redistribution atteint la racine la racine, la hauteur de l’arbre va augmenter.

Algorithme : Insert

Soit E un nouveau tuple.

Algorithme : ChooseLeaf

Détermine le nœud feuille où placer E.

Algorithme : AdjustTree

Remonte d’une feuille L jusqu’à la racine, en ajustant les rectangles et en coupant les nœuds lorsque cela est nécessaire.

Soit N le nœud courant, initialement, N = L. ( et respectivement si une coupure a eu lieu).

Un exemple d’Insertion:

On veut insérer un nouvel étudiant (Q, 10, 65).

Suppression

Si un tuple doit être supprimer de la base, il faut supprimer l’entrée qui pointe dessus dans l’index et modifier ce dernier en conséquence.

Algorithme : Delete

Algorithme : FindLeaf

Trouve le nœud feuille qui contient l’entrée E. Soit T la racine.

Algorithme : CondenseTree

Cet algorithme prend un nœud feuille L pour lequel une entré a été supprimé et modifie l’arbre si le nœud contient moins de M entrées. L’algorithme remonte l’intégralité de l’arbre et ajuste les rectangles lorsque cela est nécessaire..

On pose N = L et Q un ensemble vide de nœuds supprimés.

Un exemple de Suppression

On veut supprimer l’étudiant K de notre base. En appliquant FindLeaf , on obtient le noeud R5, on enlève l’entrée K de R5 et on s’aperçoit que R5 fait un underflow. On applique alors CondenseTree à R5, qui est enlevé du R-Tree, E est ajouté à R4 par Insert, enfin le rectangle de R1 n’a pas besoin d’être mis à jour.

Trois algorithmes SplitNode ont été propose par Guttman, afin de séparer M+1 entrées d’un nœud N en deux nœuds N et . Lorsqu’on sépare en deux un nœud, le but est de minimiser la taille des deux rectangles résultants car, plus ils sont petits, plus il y a de chance que l‘algorithme de recherche ne parcours que peu de nœuds. En effet, plus les rectangles sont petits, plus faible est la possibilité de recouvrements des rectangles.

Création d’un Index sous Oracle

Comme les base de données actuelles permettent le stockage de type de données divers ( texte, image, données spatiales, vidéos), il est devenu nécessaire de faire une indexation particulière pour effectuer des recherches spécifiques. Par exemple, on peut envisager de vouloir faire de la recherche de mot-clés dans une base de données de textes. La solution proposée par Oracle est de fournir au développeur une infrastructure grâce à laquelle il peut définir de nouveaux types d’objets, de nouveaux opérateurs ou encore de nouveaux types d’index. Le développeur crée alors pour son utilisation spécifique un Data Cartridge. Pour définir un nouveau type d’index, il lui faut :

Ceci passe par l’implémentation de l’interface ODCIIndex.

Méthodes de définition d’index

Méthodes de maintenance de l’index

Méthodes de parcours de l’index

Ces trois méthodes sont employées pour évaluer les prédicats comme dans le cas de la requête suivante qui correspond à la requête vue précédemment :

SELECT name
	FROM students
	WHERE students.semesterLB_mcredits_Mcredits(6,20,65);

Elles permettent l’initialisation, la recherche des rowid satisfaisant le prédicat et la finalisation de la requête.

Mise en Oeuvre Pratique

Tout d’abord, il faut définir un opérateur spécifique auquel on associera l’index que l’on veut créer. En effet, si on formule une requête de la manière suivante :

SELECT * FROM Cities
WHERE lat > 10 AND lat <15 AND long > 45 AND long < 60;

Pour trouver les villes qui se trouvent dans le périmètre compris entre les latitudes 10° à 15° et les longitudes 45° à 60°. Dans ce cas, il sera fait appel à l’index sur l’attribut lat et à l’index sur l’attribut long, si tant est qu’ils existent. Pour utiliser notre index R-Tree, il faut définir un opérateur spécifique tel que celui-ci :

SELECT * FROM Cities
WHERE isBetween(10,15,45,60);

Il faut aussi définir l’implémentation de cet opérateur par l’intermédiaire de la définition d’une fonction :

CREATE FUNCTION Between (latmin IN FLOAT, latmax IN FLOAT,
longmin IN FLOAT, longmin IN FLOAT) RETURN BOOLEAN IS
	BEGIN
		...
	END Between ;

Puis lier l’opérateur à la fonction de la manière suivante :

CREATE OPERATOR isBetween (FLOAT, FLOAT, FLOAT, FLOAT)
RETURN BOOLEAN USING Between ;

Enfin, on définit un type qui implante l’interface ODCIIindex. Ceci implique l’implantation des méthodes de définition d’index, de maintenance et de parcours de l’index. C’est à cette dernière famille (les méthodes start, fetch() et close()) que fera appel la fonction Between et à qui elle passera ses arguments afin que ces trois routines parcourent l’index et retournent les tuples satisfaisant la contrainte.

La déclaration du type se fait de la manière suivante :

CREATE TYPE RTreeMethods (
	PROCEDURE ODCIcreate(...)
	...
);

CREATE TYPE BODY RTreeMethods (
	...
);

Supposons maintenant que le type d’index présenté précédemment a été correctement défini dans ce système. L’utilisateur peut a présent définir des tables contenant des coordonnées spatiales, créer un index sur celles-ci et faire des requêtes à l’aide de l’opérateur isBetween.

CREATE TABLE Cities (id INTEGER, owner VARCHAR2(64),
lat FLOAT, long FLOAT);
CREATE INDEX CityIndex ON City(lat,long) INDEXTYPE IS RtreeIndex;
SELECT * FROM Cities WHERE isBetween(10,15,45,60);  

Bibliographie