Comme les méthodes dindexation traditionnelles ne sont pas adaptées aux données multidimensionnelles, une nouvelle structure était nécessaire pour traiter les données spatiales. Un exemple dapplication 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 dun projet de construction dautoroute.
Oracle comprend une série de services dextensibilité qui permettent lintégration de nouveaux types de données et de nouveaux comportements spécifiés par le développeur afin dadapter la base de données à un domaine spécifique dutilisation. Le développeur a donc la possibilité de spécifier ses propres composants, les data cartridges, comme un type dindex R-Tree, une structure adaptée à lindexation de données spatiales proposée en 1984 par Antonin Guttman.
Un R-Tree est similaire à un B-Tree dans son principe. Il sagit dun arbre dont les feuilles sont des pointeurs vers les données. Par contre, la structure de larbre et son évolution est conçue pour que la recherche spatiale soit la plus efficace possible, cest-à-dire nécessite le parcours dun petit nombre de nuds de lindex.
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 dun index bi-dimensionnel. Pour chaque nud, le nombre dentrées est compris entre m=2 et m=5.
La recherche dans un R-Tree est similaire à celle dans un B-Tree; larbre 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
nest pas une feuille, alors
appliquer Search
à tous les fils de
T
tels quils se superposent avec
S
.
T
est une feuille, on retourne
toutes les entrées qui appartiennent à
S
.
Dans lexemple, 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 à lintérieur de S
.
De R4
nous récupérons C
et de
R5
nous récupérons E
et
K
, doù le résultat : {C,E, K}
.
Lorsquun 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 nud feuille est dépassé (node overflow), le nud devra être coupé. Dans le cas où la redistribution atteint la racine la racine, la hauteur de larbre va augmenter.
Insert
Soit E
un nouveau tuple.
ChooseLeaf
pour trouver
le nud feuille L
où E
doit être placé.
L
(pas doverflow), 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 lalgorithme SplitNode a été
appliqué, alors appliquer AdjustTree
à L
aussi.
SplitNode
.
ChooseLeaf
Détermine le nud feuille où placer E
.
N
est une feuille, la retourner.
N
nest 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 dune feuille L
jusquà la racine,
en ajustant les rectangles et en coupant les nuds
lorsque cela est nécessaire.
Soit N
le nud courant, initialement,
N = L
. (N
et L
respectivement si une coupure a eu lieu).
N
est la racine, lalgorithme
est fini.
P
, un parent de N
.
Mettre à jour P
afin quil 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
doverflow. 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 lentrée qui pointe dessus dans lindex et modifier ce dernier en conséquence.
Delete
FindLeaf
pour trouver la
feuille qui contient E
.
E
du nud feuille
L
.
CondenseTree
sur
L
pour condenser "under full nodes".
FindLeaf
Trouve le nud feuille qui contient lentrée
E
. Soit T
la racine.
T
nest 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 nud feuille L
pour lequel une entré a été supprimé et modifie larbre
si le nud contient moins de M
entrées.
Lalgorithme remonte lintégralité de larbre et ajuste
les rectangles lorsque cela est nécessaire..
On pose N
= L
et
Q
un ensemble vide de nuds 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 lensemble Q
.
N
.
N = P
et retourne à la
1ère étape.
Q
dans larbre grâce à Insert.
Les nuds non-feuilles de Q
doivent être insérés à un niveau supérieur de
larbre afin que larbre soit balancé.
On veut supprimer létudiant K
de notre
base. En appliquant FindLeaf
, on obtient
le noeud R5
, on enlève lentrée
K
de R5
et on saperç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 na pas besoin dêtre
mis à jour.
Trois algorithmes SplitNode ont été propose par Guttman,
afin de séparer M+1
entrées dun nud
N
en deux nuds N
et
N
. Lorsquon sépare en deux un nud, le
but est de minimiser la taille des deux rectangles
résultants car, plus ils sont petits, plus il y a de
chance que lalgorithme de recherche ne parcours que peu
de nuds. En effet, plus les rectangles sont petits,
plus faible est la possibilité de recouvrements des
rectangles.
Exhaustive Splitnode
2M-1
combinaisons
possibles, le temps de calcul grandit de manière
exponentielle. Il nest pas adapté lorsquon
manipule de grandes tables et donc de grands
index, cest à dire lorsque M
doit être supérieur à 50.
Quadratic Cost
Linear Cost
i
les paires dentré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 dobjets, de nouveaux opérateurs ou encore de nouveaux types dindex. Le développeur crée alors pour son utilisation spécifique un Data Cartridge. Pour définir un nouveau type dindex, il lui faut :
Ceci passe par limplémentation de linterface ODCIIndex.
ODCIcreate()
CREATE INDEX
faisant référence au
type dindex ici implantée. Un certain nombre de
paramètres peut être passé en argument dappel
grâce à la clause
PARAMETERS (...)
ODCIalter()
ALTER INDEX
. Comme précédemment, la
clause PARAMETERS (...)
peut être
utilisée.
ODCItruncate()
TRUNCATE
lorsquelle 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 dappel, 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 linitialisation, la recherche des rowid satisfaisant le prédicat et la finalisation de la requête.
ODCIstart()
ODCIfetch()
ODCIclose()
Tout dabord, il faut définir un opérateur spécifique auquel on associera lindex que lon 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 à lindex sur lattribut lat et à lindex sur lattribut long, si tant est quils 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 limplémentation de cet opérateur par lintermédiaire de la définition dune fonction :
CREATE FUNCTION Between (latmin IN FLOAT, latmax IN FLOAT, longmin IN FLOAT, longmin IN FLOAT) RETURN BOOLEAN IS BEGIN ... END Between ;
Puis lier lopé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 linterface ODCIIindex. Ceci implique limplantation des méthodes de définition dindex, de maintenance et de parcours de lindex. Cest à 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 lindex 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 dindex présenté précédemment a été correctement défini dans ce système. Lutilisateur 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 à laide de lopé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);