B*-copac

Un arbore B*  este un tip de arbore B în care fiecare nod al arborelui este plin de cel puțin ⅔ (spre deosebire de un arbore B în care această cifră este 1/2).

Arborii B* au fost propuși de Rudolf Bayer și Edward McCraith , care au studiat problema compactității arborilor B. Arborele B* este relativ mai compact deoarece fiecare nod este utilizat mai pe deplin. În alte privințe, acest tip de arbore nu diferă de un simplu arbore B.

Pentru a îndeplini cerința „nodul este plin de cel puțin 2/3”, trebuie să renunțăm la procedura simplă de împărțire a unui nod debordant. În schimb, există o „transfuzie” în nodul vecin. Dacă și nodul vecin este plin, atunci cheile sunt împărțite aproximativ egal în 3 noduri noi.

Un arbore B + care satisface aceste cerințe se numește arbore B *+ [1] .

Note

1. ↑ Rigin AM , Shershakov SA Extensie SQLite RDBMS pentru indexarea datelor utilizând modificările B-tree  . Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS) . Institutul pentru Programarea Sistemelor RAS (ISP RAS) (10 septembrie 2019). doi : 10.15514/ispras-2019-31(3)-16 . Preluat la 29 august 2021. Arhivat din original la 29 august 2021.

Link -uri

• Dicționarul de algoritmi și structuri de date pentru intrarea B*  -tree
• Donald Knuth . 4. Generarea tuturor copacilor. Istoria generației combinatorii // The Art of Programming = The Art of Computer Programming. - M. : „Williams” , 2007. - V. 4. - S. 160. - ISBN 0-321-33570-8 .