B-koks

Datoru zinātnē, B-koks ir kokveida datu struktūra, kas tur datus sakārtotus un atļauj meklēšanu, kārtas piekļuvi, ievietošanu un dzēšanu veikt logoritmiski amortizētā laikā. B-koks ir vispārināts binārās meklēšanas koka variants. B-koks ir optimizēts priekš sistēmām, kas lasa un raksta lielus datu blokus. Tas pamatā tiek izmantots datu bāzēs un failu sistēmās.

Piemērs: A B-tree of order 2 (Bayer & McCreight 1972) or order 5 (Knuth 1997).

Pārskats

B-kokos, iekšējais bez-lapu mezgls var saturēt mainīgu skaitu bērnu mezglu (jeb apakš-mezglu), kādā noteiktā diapazonā. Kad dati tiek ievietoti, vai izdzēsti no mezgla, tā bērnu-mezglu skaits mainās. Lai saglabātu iepriekš nodefinēto diapazonu, iekšējie mezgli var tikt pievienoti vai sadalīti. Sakarā ar bērnu mezglu diapazonu, B-kokiem nevajag no jauna veikt balansu, kā tas nepieciešams citiem "sevis-balansējošiem-meklēšanas-kokiem", tādējādi, var ieekonomēt vietu atmiņā, tā kā mezgli nav pilnīgi pilni. Augšējās un apakšējās bērnu-mezglu robežas tipiski tiek labotas ar īpašu īstenošanu. Piemērām, 2-3 B-kokā katrs iekšējais mezgls var saturēt tikai 2 vai 3 bērnu- mezglus.

Katrs iekšējais mezgls saturēs noteiktu skaitu atslēgu. Parasti atslēgu skaits tiek izvēlēts, lai tas būtu starp d un 2d. Praksē, atslēgas izmanto lielāko atmiņas daļu mezglā. Koeficients 2 nodrošinās, ka mezgli var tikt sadalīti un savienoti. Ja iekšējam mezglam ir 2d atslēgas, tad atslēgas pievienošana šim mezglam var tikt veikta sadalot 2d atslēgas mezglu, divos d atslēgas mezglos un pievienojot atslēgu no mātes mezgla (Parent node). Katram sadalīšanas mezglam ir jāsatur minimālais atslēgu skaits. Līdzīgi, ja iekšējais mezgls un tā kaimiņa mezgls, abi satur d atslēgas, tad atslēga var tikt dzēsta no iekšējā mezgla, sakombinējot to ar kaimiņa mezglu.

Zaru skaits (vai bērnu mezglu) no mezgla būs par vienu vairāk, kā mezglā noglabāto atslēgu skaits. 2-3 B-kokā, iekšējie mezgli saturēs vai nu vienu atslēgu (ar diviem bērnu mezgliem) vai divas atslēgas ( ar 3 bērnu mezgliem). B-koks reizēm tiek raksturots ar parametriem (d+1) - (2d+1) vai vienkārši ar augstāko zarotnes kārtību, (2d+1).

B-koks ir balansēts sakarā ar to, ka visi mezgli, kas satur lapas ir vienādā dziļumā. Dziļums lēnām palielināsies, pamazām pievienojot elementus kokam.

B-kokam ir būtiskas priekšrocības, pār alternatīvām īstenošanām (implementācijām), kur mezglu piekļuves laiks pārsniedz piekļuves laikus ar mezgliem. Tas parasti notiek, ja mezgli atrodas sekundārā glabātuvē, tādā kā, diskdzinī. Palielinot bērnu mezglu skaitam ar katru iekšējo mezglu, koka augstums samazinās un vērtīgās piekļuves laika reizes samazinās, jo ir jāveic mazāk piekļuves, kas ekonomē laiku.

Datubāzes problēma

Laiks meklējot sakārtotā failā

Parasti kārtošanas un meklēšanas algoritmi tiek aprakstīti pēc vairākām salīdzināšanas operācijām, kuras jāveic lietojot kārtības notāciju. Piemēram bināro meklēšanu sakārtotā tabulā ar N ierakstiem var veikt O(log₂N) salīdzināšanas darbībās. Ja tabulai būtu 1,000,000 ierakstu, tad izvēlētais ieraksts varētu tikt atrasts ar aptuveni 20 darbībām: log₂1,000,000 = 19,931...

Lielas datubāzes vēsturiski tiek glabātas cietajos diskos. Laiks, kas nepieciešams diskiekārtai lai nolasītu ierakstu var dominēt pār laiku kas nepieciešams lai salīdzinātu atslēgas, kad ieraksts beidzot ir pieejams.Laiks kas nepieciešams lai nolasītu ierakstu no diskiekārtas iekļauj sevī meklēšanas laiku un rotācijas aizkavi. Meklēšanas laiks var būt no 0 līdz 20 vai vairāk milisekundes, un rotācijas aizkaves laiks ir vidēji puse no rotācijas perioda. 7200 RPM diskam, rotācijas periods ir 8.33 milisekundes. Piemēram diskam Seagate ST3500320NS "no ieraksta-līdz-ierakstam" meklēšanas laiks ir 0.8 milisekundes un vidējais lasīšanas meklēšanas laiks ir 8.5 milisekundes. Vienkāršošanas nolūkos varam uzskatīt ka nolasīšana no diska aizņem aptuveni 10 milisekundes.

Naivi rēķinot, laiks kas aizņemtu atrast ierakstu no miljona būtu 20 lasīšanas darbību reiz 10 milisekundes katra darbība, kas būtu 0.2 sekundes.