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.
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.
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.
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.
T n’est pas une feuille, alors
appliquer Search à tous les fils de
T tels qu’ils se superposent avec
S.
T est une feuille, on retourne
toutes les entrées qui appartiennent à
S.
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}.
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.
Insert
Soit E un nouveau tuple.
ChooseLeaf pour trouver
le nœud feuille L où E
doit être placé.
L
(pas d’overflow), on ajoute E.
Sinon, on applique SplitNode à L,
qui retournera L et L’
contenant E et tous les éléments de
L déjà présents.
AdjustTree à
L, si l’algorithme SplitNode a été
appliqué, alors appliquer AdjustTree
à L’ aussi.
SplitNode.
ChooseLeaf
Détermine le nœud feuille où placer E.
N est une feuille, la retourner.
N n’est pas une feuille, trouver
le fils Fk de N, pour
lequel le rectangle doit être le moins agrandi
(en terme de surface) pour y inclure E.
Fk
répondent au critère, on choisit le rectangle
le plus petit.
ChooseLeaf au
Fk trouvé jusqu’à atteindre une
feuille.
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. (N’ et L’
respectivement si une coupure a eu lieu).
N est la racine, l’algorithme
est fini.
P, un parent de N.
Mettre à jour P afin qu’il couvre
tous les rectangles de N.
L a été coupé, on ajoute
N’ comme fils de P. Si
P est en overflow, on applique
SplitNode (voir derniers
algorithmes) à celui-ci.
On veut insérer un nouvel étudiant (Q, 10, 65).
ChooseLeaf renvoie R1.R3 est choisi pour être le
rectangle où va être insérée la nouvelle feuille
pointant sur la donnée. Le noeud ne fait pas
d’overflow. Ainsi Q est inséré dans
R3.
AdjustTree met à jour les
noeuds de R3 et R1
afin de prendre en compte la nouvelle feuille.
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.
DeleteFindLeaf pour trouver la
feuille qui contient E.
E du nœud feuille
L.
CondenseTree sur
L pour condenser "under full nodes".
FindLeaf
Trouve le nœud feuille qui contient l’entrée
E. Soit T la racine.
T n’est pas une feuille,
appliquer FindLeaf à tous les
fils dont les rectangles qui contiennent
E.
T est une feuille, comparer
chaque entrée avec E et si une
entrée correspond, retourner T.
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.
N est la racine, aller à la
dernière étape. Sinon, on pose P
le parent de N.
N a moins de M
entrées (underflow), retirer le pointeur de
P vers N et mettre
N dans l’ensemble Q.
N.
N = P et retourne à la
1ère étape.
Q dans l’arbre grâce à Insert.
Les nœuds non-feuilles de Q
doivent être insérés à un niveau supérieur de
l’arbre afin que l’arbre soit balancé.
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
N’. 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.
Exhaustive Splitnode2M-1 combinaisons
possibles, le temps de calcul grandit de manière
exponentielle. Il n’est pas adapté lorsqu’on
manipule de grandes tables et donc de grands
index, c’est à dire lorsque M
doit être supérieur à 50.
Quadratic CostLinear Costi les paires d’entrées
qui sont les plus éloignées. Les entrées
restantes (dans le cas où
i < M/2 -1) sont distribuées de
manière aléatoire. Cet algorithme est le plus
rapide mais est long d’être le moins coûteux
quant aux performances lors des recherches.
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.
ODCIcreate()CREATE INDEX faisant référence au
type d’index ici implantée. Un certain nombre de
paramètres peut être passé en argument d’appel
grâce à la clause
PARAMETERS (...)
ODCIalter()ALTER INDEX. Comme précédemment, la
clause PARAMETERS (...) peut être
utilisée.
ODCItruncate()TRUNCATE lorsqu’elle porte sur une
table dont les colonnes sont indexées.
ODCIdrop()DROP INDEX.
ODCIinsert()ODCIdelete()ODCIupdate()UPDATE. Cette fois-ci, ce sont les
anciennes et nouvelles valeurs qui sont passés
en argument d’appel, ainsi que le rowid du
tuple concerné.
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.
ODCIstart()ODCIfetch()ODCIclose()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);