Comment gérer l'insertion sur un arbre très large ?!

Bonjour,

Les opérations d'insertions sont gérés au sein d'une transaction SQL ?

----------------------------------------------------------------------
Philippe TROTIN - Microsoft Service France

"Mikado" <Mikado@libertysurf.fr> wrote in message
news:%23mf79QYnFHA.3608@TK2MSFTNGP15.phx.gbl...

Salut à tous,

Petite question. Imaginons une base avec 1 million d'enregistrements gérés
sous forme d'arbre intervallaire. Du genre :

ID Libelle BG BD Niv
1 Root 1 22 1
2 Niveau 1 2 15 2
3 Niveau 1.1 3 10 3
4 Niveau 1.1.1 4 5 4
5 Niveau 1.1.2 6 7 4
6 Niveau 1.1.3 8 9 4
7 Niveau 1.2 11 14 3
8 Niveau 1.2.1 12 13
4
9 Niveau 2 16 21 2
10 Niveau 2.1 17 20
3
11 Niveau 2.1.1 18 19
4

Un premier utilisateur doit insérer 50 données dans le niveau 1.1.1. Le
bord droit du parent va donc être décalé de 101 (donc j'aurrai la valeur
106 dans mon cas) et tous les bords suivant de 2. La procédure à effectuer
est donc la suivante :

1. On récupère le bord gauche du parent (pour Niveau 1.1.1 c'est 4).
2. On insert les nouveaux éléments en partant du bord gauche comme base
(5,7,9,11,...99) , le bord droit = bord gauche +1 (6,8,10,...100)
3. On mets à jour le bord droit du parent (on aurrait pu le faire
directement à l'étape 1..) (pour Niveau 1.1.1 ça devient 101)
4. On mets à jour les bords suivants avec BG+2 et BD+2

Imaginons qu'un second utilisateur fasse la même manipulation quand
l'utilisateur en est seulement à l'étape 2

1. On récupère le bord gauche du parent (imaginons pour Niveau 1.2.1 c'est
12)
2. On insert les nouveaux éléments en partant du bord gauche comme base
(13,15,17...), le bord droit = bord gauche +1 (6,8,10,...100). Au même
moment, le premier utilisateur passe à l'étape 3. Paf ça fonctionne plus
correctement....

Comment faire pour éviter ce genre de problème ?!

Jérôme

utiliser une procédure stockée transactionnée comme indiqué dans mon article :

http://sqlpro.developpez.com/cours/arborescence/#L2.11

-- procédure d'insertion dans l'arbre
-- [Frédéric Brouard, Philippe Boucault 25/09/2002]

CREATE PROCEDURE SP_INS_NOMENCLATURE

@lib varchar(32), -- le libellé à insérer
@desc varchar(1024), -- la description à insérer
@id_parent int, -- Ancêtre ou frère point d'origine de l'insertion
@mode char(2) -- le mode d'insertion :
-- FA : Fils Ainé,
-- FC : Fils Cadet,
-- GF : Grand frère,
-- PF : Petit Frère,
-- P : Père
AS

DECLARE @OK int

DECLARE @bgp int -- borne gauche parent
DECLARE @bdp int -- borne droite parent
DECLARE @nivp int -- niveau parent

DECLARE @bgi int -- borne gauche à insérer
DECLARE @bdi int -- borne droite à insérer
DECLARE @nivi int -- niveau à insérer

SET NOCOUNT ON

-- gestion des effets de bord
IF @mode IS NULL OR @lib IS NULL OR @lib = ''
BEGIN
RAISERROR ('Insertion impossible sans libellé ou mode ! (TABLE
T_NOMENCLATURE_NMC)', 16, 1)
RETURN
END

SET @mode = UPPER(@mode)
IF NOT( @mode = 'FA' OR @mode = 'FC' OR @mode = 'GF' OR @mode = 'PF' OR @mode
= 'P')
BEGIN
RAISERROR ('Insertion impossible, mode inconnu !', 16, 1)
RETURN
END

-- démarrage transaction
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
BEGIN TRANSACTION INSERT_NOMENCLATURE


-- pas de parent => seul cas, table vide ou insertion d'un collatéral
IF @id_parent IS NULL
BEGIN
SELECT @OK = count(*) FROM T_NOMENCLATURE_NMC
IF @OK = 0 OR @OK IS NULL
BEGIN
IF @mode = 'FA' OR @mode = 'FC'
BEGIN
RAISERROR ('Insertion impossible dans un arbre pour un fils sans père
!', 16, 1)
GOTO LBL_ERROR
RETURN
END
ELSE
BEGIN
-- première insertion
INSERT INTO T_NOMENCLATURE_NMC ( NMC_LIBELLE, NMC_DESCRIPTION,
NMC_NIVEAU, NMC_BG, NMC_BD )
VALUES( @lib, @desc, 0, 1, 2 )
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END
COMMIT TRANSACTION INSERT_NOMENCLATURE
SELECT @@IDENTITY
RETURN
END
END
ELSE
-- Insertion d'un collatéral
BEGIN
RAISERROR ('Insertion impossible dans un arbre pour un collatéral sans
précision du parent !', 16, 1)
GOTO LBL_ERROR
RETURN
END
END

-- Le parent existe toujours ?
SELECT @OK = count(*) FROM T_NOMENCLATURE_NMC WHERE NMC_ID = @id_parent
IF @OK = 0 OR @OK IS NULL
BEGIN
RAISERROR ('Insertion impossible, le parent n''existe plus !', 16, 1)
GOTO LBL_ERROR
RETURN
END

-- On a un parent : on récupère ses éléments
SELECT @bgp = NMC_BG, @bdp = NMC_BD, @nivp = NMC_NIVEAU
FROM T_NOMENCLATURE_NMC
WHERE NMC_ID = @id_parent

-- insertion d'un père
IF @mode = 'P'
BEGIN
-- Décalage de l'ensemble colatéral droit
UPDATE T_NOMENCLATURE_NMC
SET NMC_BD = NMC_BD + 2
WHERE NMC_BD > @bdp
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END
UPDATE T_NOMENCLATURE_NMC
SET NMC_BG = NMC_BG + 2
WHERE NMC_BG > @bdp
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END

-- Décalalage ensemble visé vers le bas
UPDATE T_NOMENCLATURE_NMC
SET NMC_BG = NMC_BG + 1,
NMC_BD = NMC_BD + 1,
NMC_NIVEAU = NMC_NIVEAU + 1
WHERE NMC_BG >= @bgp AND NMC_BD <= @bdp
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END

-- Insertion du nouveau père
INSERT INTO T_NOMENCLATURE_NMC ( NMC_LIBELLE, NMC_DESCRIPTION, NMC_NIVEAU,
NMC_BG, NMC_BD )
VALUES( @lib, @desc, @nivp, @bgp, @bdp + 2 )
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END
END

-- Insertion d'un grand frère
IF @mode = 'GF'
BEGIN
-- Limite sup.
UPDATE T_NOMENCLATURE_NMC
SET NMC_BD = NMC_BD + 2
WHERE NMC_BD > @bgp
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END

-- Limite inf.
UPDATE T_NOMENCLATURE_NMC
SET NMC_BG = NMC_BG + 2
WHERE NMC_BG >= @bgp
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END

SET @bgi = @bgp
SET @bdi = @bgp + 1
SET @nivi = @nivp
INSERT INTO T_NOMENCLATURE_NMC ( NMC_LIBELLE, NMC_DESCRIPTION, NMC_NIVEAU,
NMC_BG, NMC_BD )
VALUES( @lib, @desc, @nivi, @bgi, @bdi )
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END
END


-- Insertion d'un petit frère
IF @mode = 'PF'
BEGIN
-- Limite sup.
UPDATE T_NOMENCLATURE_NMC
SET NMC_BD = NMC_BD + 2
WHERE NMC_BD > @bdp
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END

-- Limite inf.
UPDATE T_NOMENCLATURE_NMC
SET NMC_BG = NMC_BG + 2
WHERE NMC_BG >= @bdp
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END

SET @bgi = @bdp + 1
SET @bdi = @bdp + 2
SET @nivi = @nivp
INSERT INTO T_NOMENCLATURE_NMC ( NMC_LIBELLE, NMC_DESCRIPTION, NMC_NIVEAU,
NMC_BG, NMC_BD )
VALUES( @lib, @desc, @nivi, @bgi, @bdi )
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END
END

-- Insertion d'un fils ainé
IF @mode = 'FA'
BEGIN
-- Limite sup.
UPDATE T_NOMENCLATURE_NMC
SET NMC_BD = NMC_BD + 2
WHERE NMC_BD > @bgp
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END

-- Limite inf.
UPDATE T_NOMENCLATURE_NMC
SET NMC_BG = NMC_BG + 2
WHERE NMC_BG > @bgp
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END

SET @bgi = @bgp + 1
SET @bdi = @bgp + 2
SET @nivi = @nivp + 1
INSERT INTO T_NOMENCLATURE_NMC ( NMC_LIBELLE, NMC_DESCRIPTION, NMC_NIVEAU,
NMC_BG, NMC_BD )
VALUES( @lib, @desc, @nivi, @bgi, @bdi )
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END
END

-- Insertion d'un fils cadet
IF @mode = 'FC'
BEGIN
-- Limite sup.
UPDATE T_NOMENCLATURE_NMC
SET NMC_BD = NMC_BD + 2
WHERE NMC_BD >= @bdp
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END

-- Limite inf.
UPDATE T_NOMENCLATURE_NMC
SET NMC_BG = NMC_BG + 2
WHERE NMC_BG > @bdp
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END

SET @bgi = @bdp
SET @bdi = @bdp + 1
SET @nivi = @nivp + 1
INSERT INTO T_NOMENCLATURE_NMC ( NMC_LIBELLE, NMC_DESCRIPTION, NMC_NIVEAU,
NMC_BG, NMC_BD )
VALUES( @lib, @desc, @nivi, @bgi, @bdi )
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END
END

-- renvoi de l'identifiant de l'élément inséré
SELECT @@IDENTITY

COMMIT TRANSACTION INSERT_NOMENCLATURE
RETURN

LBL_ERROR:
ROLLBACK TRANSACTION INSERT_NOMENCLATURE


A +

--
Frédéric BROUARD, MVP SQL Server. Expert SQL / spécialiste Delphi, web
Livre SQL - col. Référence : http://sqlpro.developpez.com/bookSQL.html
Le site du SQL, pour débutants et pros : http://sqlpro.developpez.com
************************ www.datasapiens.com *************************


Mikado a écrit:

Salut à tous,

Petite question. Imaginons une base avec 1 million d'enregistrements gérés
sous forme d'arbre intervallaire. Du genre :

ID Libelle BG BD
Niv
1 Root 1 22
1
2 Niveau 1 2 15
2
3 Niveau 1.1 3 10
3
4 Niveau 1.1.1 4 5
4
5 Niveau 1.1.2 6 7
4
6 Niveau 1.1.3 8 9
4
7 Niveau 1.2 11 14
3
8 Niveau 1.2.1 12 13 4
9 Niveau 2 16 21
2
10 Niveau 2.1 17 20 3
11 Niveau 2.1.1 18 19 4

Un premier utilisateur doit insérer 50 données dans le niveau 1.1.1. Le bord
droit du parent va donc être décalé de 101 (donc j'aurrai la valeur 106 dans
mon cas) et tous les bords suivant de 2. La procédure à effectuer est donc
la suivante :

1. On récupère le bord gauche du parent (pour Niveau 1.1.1 c'est 4).
2. On insert les nouveaux éléments en partant du bord gauche comme base
(5,7,9,11,...99) , le bord droit = bord gauche +1 (6,8,10,...100)
3. On mets à jour le bord droit du parent (on aurrait pu le faire
directement à l'étape 1..) (pour Niveau 1.1.1 ça devient 101)
4. On mets à jour les bords suivants avec BG+2 et BD+2

Imaginons qu'un second utilisateur fasse la même manipulation quand
l'utilisateur en est seulement à l'étape 2

1. On récupère le bord gauche du parent (imaginons pour Niveau 1.2.1 c'est
12)
2. On insert les nouveaux éléments en partant du bord gauche comme base
(13,15,17...), le bord droit = bord gauche +1 (6,8,10,...100). Au même
moment, le premier utilisateur passe à l'étape 3. Paf ça fonctionne plus
correctement....

Comment faire pour éviter ce genre de problème ?!

Jérôme