дърво метод съхранение BD - поръчал дърво прекосява (гнезда)

Съдържание статия

1. Въведение

При проектирането на базата данни, често е необходимо да се съхранява дърво, и като таблицата на базата данни не е специално предназначен за съхранение на дървета, е необходимо да се прибягва до различни трикове. Най-лесният и най-лесния начин - да се запази всеки елемент
дърво освен идентификатор (ID) позоваване на елемент родител (parent_id). Но работата с такова дърво е свързано с големи режийни, така например, за всички
дърво, ние трябва да използваме рекурсия (или емулация), което го прави един SQL-заявка
за всеки елемент дърво. По-долу е описание на метода, който ви позволява да се сведе до минимум разходите за извършване на необходимите операции често с дървета.

2. Описание на метода

Да предположим, че имаме едно дърво, и ние казваме, че всяко дърво елемент има двойка стойности, обикновено известна като ляво и дясно. Отиваме около дървото от дълбочината на корен (рекурсивно) и присвоява пореден индекс на левия стойността на върха, когато стигнем до нея за първи път, както и правото стойност, когато стигнем до него за втори път или връх е най-добрият върха на дървото (което все още няма наследници) , Например, както е показано на снимката на борда:

дърво метод съхранение BD - поръчал дърво прекосява (гнезда)

3. Ползи

Това, което правим за вас? Това ни дава, че изпълнението на някои често използвани операции за работа с дърво (не е свързано с промени в тях) ние може да носи един (1) SQL-заявка:

Получаване на поддърво (списъкът на върховете, които са поддърво на определен даден възел). За това ние само трябва да поиска списък с елементи останали стойности, които са по-големи от тези на даден възел, както и правото стойност - по-малко:

SELECT * FROM `` tree` КЪДЕ left`> И `right` <

Пътят от корена. Операция обратна предишния - да поиска списък с елементи, останали стойности са по-малки от даден връх и правото стойност - по-опростена и наляво или надясно стойност:

SELECT * ОТ `` tree` КЪДЕТО left` РЕД ОТ `left` ASC;

Първи разширите елементите на списъка дърво (заобикаляйки бездната).
За да направите това, ние просто трябва да си поръчате проба от ляво на стойност:

SELECT * от 'tree` РЕД ОТ `left`;

Комбинирайте това с параграф 1, не е възможно да се получи подробен списък с определен поддърво.

обем Получаване поддърво (брой елементи в този поддърво). За тази цел ние дори
не правят допълнителна молба. В горната част, за които ние трябва да се обемът просто да вземем (вдясно - ляво - 1) / 2.

Получаване общ корен поддърво минимален обем на две дадени върховете
може да се получи, ако искането елемент с най-голямата стойност на левия (или десния най-малък), за които стойността е по-малка от ляво, така наляво и надясно през двете дясно:

$ Наляво = минути ($ node1_left, $ node2_left);
$ Надясно = макс ($ node1_right, $ node2_right);
SELECT * ОТ `` tree` КЪДЕТО left` <$left AND ` right `> $ Право ORDER BY `left` DESC LIMIT 1;

Освен това, нашите дърво има някои евентуално полезни свойства:

Крайната точка на дървото е на стойност, равна на дясно, ляво + 1;
Първите потомък върховете е оставил определена стойност, равна на стойността на лявата родител - 1;
Последното дете на определен връх има правото стойност, равна на стойността на дясната родител + 1.

Въпреки това, за рекурсивно дърво прекосявам, още по-лесно да се използва по-традиционния метод за съхранение на дървесина, като се използва идентификатора и parent_id. Не виждам причина да го изостави - метод за съхранение на две дърво може успешно да се комбинират и да използват по този начин предимствата и на двете.

4. Недостатъци

Този метод е т.нар В посока надолу на, което е, че ако добавяте, изтривате и да се премести дървесни елементи, които трябва да отново да разчита на ценностите на ляво и дясно на дървото.

4.1. Добавянето на елемент

Добавянето на нов елемент дете до известна даден връх може да се направи по два начина: в горната част на списъка на подчинените елементи, както и в края.

UPDATE `` tree` SET left` = `left` + 2, когато` left`>;
UPDATE `` tree` SET right` = `right` + 2, когато` right`>;
INSERT INTO `` tree` SET left` = + 1, `right` = + 2;

UPDATE `` tree` SET left` = `left` + 2, когато` left`>;
UPDATE `` tree` SET right` = `right` + 2, когато` right`> =;
INSERT INTO `` tree` SET left` =, `right` = + 1;

Къде $ parent_left и $ parent_right - това наляво и надясно стойност на възела родител, съответно.

Добавянето на няколко елемента в една и съща майка елемент може да бъде оптимизирана не е задължително да изпълнява две актуализация за всеки добавен елемент - това е възможно да се извърши актуализация на 2 за всички добавени елементи директно.

4.2. Изтриването на елемент или поддърво

Изтриването на елемент или под-дърво е сравнително проста:

Изтрива от `` tree` КЪДЕТО left`> = И `right` <= ;
UPDATE `` tree` SET left` = `left` - + - 1, където` left`>;
UPDATE `` tree` SET right` = `right` - + - 1, където` right`>;

Къде $ наляво и надясно $ - лява и дясна стойности на най-горния елемент за премахване или под-дърво.

4.3. Преместването елемент или поддърво

Преместването елемент дърво е най-трудно в тази операция, е необходимо да се преизчисли стойностите на ляво и дясно на цялото дърво, въпреки че може би оптимално се осъществява чрез добавяне на движението на превозваните дървени елементи на един и отстраняване на връх движимо с цялата поддървото.

4.4. интегритет

За съжаление, на целостта на дървото лесно да се счупят и достатъчно трудно да се възстанови. Точно възстановяване е пълно преизчисляване на дървото. Компромис целостта може, например, аварийно спиране, свързани с промяна на структурата на дървото. Както е посочено по-горе, прибавянето и отстраняването на елемент дърво се състои от множество заявки. Ако изпълните само част от тях, а след това на целостта на дървото ще бъде счупен. Ето защо: Първо, аз силно препоръчвам да се запази едно дърво в операции по поддръжката на маса (например, InnoDB в MySQL) и експлоатира добавяне и премахване на дървени елементи в рамките на сделката (START сделка; ...; COMMIT;); На второ място, добави уникален индекс на левите и десните ценности - е, разбира се, не е гаранция за целостта, но може да помогне за предотвратяване на глупави грешки при работа с дърво.

4.5. Грижа за актуализиране на дървото

Когато изпълнението дърво модификация не трябва да забравяме, че левите и десните ценности се сменят след всяка промяна в структурата. По този начин, ако направите избор на елементите на дървото от таблицата на базата данни, заедно с модификация, на левия и десния стойностите в извадката ще бъдат остарели. Или ако имаш на левия и десния стойности и записва в съответните променливи, след модификация на дървото се съхранява в стойностите на променливите е вероятно да не е актуална.

5. Освен това четене

5 коментара към "метод дърво за съхранение в база данни - поръчал Tree Traversal (гнезда)"

Възможно ли е да се съхранява в таблицата с помощта на този метод на няколко дървета?

Или основния елемент на цялото дърво може да бъде само един?

Възможно е, освен това, ние не изглежда да има каквито и да било средства за осигуряване на дървовидната структура на списъка, с изключение, разбира се, собствения си мозък - ние не контролираме отсъствие на цикъла и уникалността на корена. Освен това, един и същ възел може по този начин да включва няколко дървета наведнъж, но дори и тогава се оказва, "пищов". Лично аз просто питам този въпрос - разбира се, че всичко е добре, как можете бързо да работят с дървета чрез SQL?

Остава да се разбере как да се форматира (отстъп) дървото от базата данни?

И аз вярвам, че трябва да бъде така:
- Първите потомък върховете е оставил определена стойност равна на стойността на лявата майка + 1; (Вместо 1)
- Последното дете на определен връх има правото стойност, равна на стойността на дясната родител - 1 (вместо един)

Кажете ни какво мислите за това

Свързани статии

Алкални свойства на почвата, подобрени методи, избора на широколистни дървета