B*-træ

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 18. december 2016; checks kræver 6 redigeringer .

Et B*-træ  er en type B-træ , hvor hver knude i træet er mindst ⅔ fuld (i modsætning til et B-træ, hvor dette tal er 1/2).

B*-træer blev foreslået af Rudolf Bayer og Edward McCraith , som studerede problemet med kompakthed af B-træer . B*-træet er relativt mere kompakt, fordi hver node bruges mere fuldt ud. I øvrigt adskiller denne type træ sig ikke fra et simpelt B-træ.

For at opfylde kravet "knuden er mindst 2/3 fuld", er man nødt til at opgive den simple procedure for opdeling af en overfyldt knude. I stedet er der en "transfusion" ind i den tilstødende knude. Hvis naboknuden også er fuld, så er nøglerne omtrent ligeligt opdelt i 3 nye knudepunkter.

Et B + -træ , der opfylder disse krav, kaldes et B *+ -træ [1] .

Noter

  1. ↑ Rigin AM , Shershakov SA SQLite RDBMS-udvidelse til dataindeksering ved hjælp af B-  træændringer . Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS) . Institut for Systemprogrammering af RAS (ISP RAS) (10. september 2019). doi : 10.15514/ispras-2019-31(3)-16 . Hentet 29. august 2021. Arkiveret fra originalen 29. august 2021.

Links