B koks

Datoru zinātnē B-koks ir kokveida datu struktūra, kas uztur datus sakārtotus un atļauj meklēšanu, kārtas piekļuvi, ievietošanu un dzēšanu veikt logaritmiski 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ēram, 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. 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 realizā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.

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 var 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.