B*-träd

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 18 december 2016; kontroller kräver 6 redigeringar .

Ett B*-träd  är en typ av B-träd där varje nod i trädet är minst ⅔ fullt (till skillnad från ett B-träd där denna siffra är 1/2).

B*-träd föreslogs av Rudolf Bayer och Edward McCraith , som studerade problemet med kompakthet hos B-träd . B*-trädet är relativt mer kompakt eftersom varje nod används mer fullständigt. I övrigt skiljer sig denna typ av träd inte från ett enkelt B-träd.

För att uppfylla kravet "noden är minst 2/3 full" måste man överge den enkla proceduren för att dela en överfull nod. Istället sker en "transfusion" till den närliggande noden. Om den närliggande noden också är full, är nycklarna ungefär lika uppdelade i 3 nya noder.

Ett B + -träd som uppfyller dessa krav kallas ett B *+ -träd [1] .

Anteckningar

  1. ↑ Rigin AM , Shershakov SA SQLite RDBMS-tillägg för dataindexering med B-trädändringar  . Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS) . Institutet för systemprogrammering av RAS (ISP RAS) (10 september 2019). doi : 10.15514/ispras-2019-31(3)-16 . Hämtad 29 augusti 2021. Arkiverad från originalet 29 augusti 2021.

Länkar