B*-fa

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2016. december 18-án felülvizsgált verziótól ; az ellenőrzések 6 szerkesztést igényelnek .

A B*-fa  egy olyan típusú B-fa , amelyben a fa minden csomópontja legalább ⅔-ig tele van (ellentétben a B-fával, ahol ez a szám 1/2).

A B*-fákat Rudolf Bayer és Edward McCraith javasolta, akik a B-fák tömörségének problémáját tanulmányozták . A B*-fa viszonylag kompaktabb, mivel minden csomópontot jobban kihasználnak. Más szempontból ez a fafajta nem különbözik az egyszerű B-fától.

A „csomópont legalább 2/3-ig megtelt” követelmény teljesítéséhez el kell hagyni a túlcsordult csomópont felosztásának egyszerű eljárását. Ehelyett "transzfúzió" történik a szomszédos csomópontba. Ha a szomszédos csomópont is tele van, akkor a kulcsok körülbelül egyenlő arányban vannak felosztva 3 új csomópontra.

Egy B + -fát , amely megfelel ezeknek a követelményeknek, B *+ -fának nevezzük [1] .

Jegyzetek

  1. ↑ Rigin AM , Shershakov SA SQLite RDBMS kiterjesztés adatindexeléshez B-fa módosítások használatával  . Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS) . Institute for System Programming of the RAS (ISP RAS) (2019. szeptember 10.). doi : 10.15514/ispras-2019-31(3)-16 . Letöltve: 2021. augusztus 29. Az eredetiből archiválva : 2021. augusztus 29.

Linkek