Nederlands
Menu

Datastructuren en algoritmen

Wat is de belangrijkste reden dat voor indexen in databases en bestandssystemen vaak B-bomen (inclusief B+-bomen) worden gebruikt in plaats van binaire zoekbomen?

  1. AElke knoop bevat veel sleutels, waardoor de boom laag blijft en het bereik bij elke gelezen knoop sterk wordt ingeperkt; zo zijn er minder bloklezingen van schijf of vergelijkbare opslag nodig
  2. BElke knoop bevat maar één sleutel, dus er zijn minder vergelijkingen nodig dan in een binaire zoekboom
  3. CDe boom hoeft bij invoegen niet te worden aangepast, dus hij is eenvoudiger te implementeren dan een binaire zoekboom
Antwoord en toelichting tonen

Antwoord: A. Elke knoop bevat veel sleutels, waardoor de boom laag blijft en het bereik bij elke gelezen knoop sterk wordt ingeperkt; zo zijn er minder bloklezingen van schijf of vergelijkbare opslag nodig

Schijven en SSD's lezen gegevens in blokken van enkele kilobytes, ook als er maar één byte nodig is, dus het aantal leesbewerkingen beperken is belangrijk. Een B-boom zet honderden sleutels in één knoop (één blok), zodat elke gelezen knoop zich honderdvoudig vertakt; zelfs 100 miljoen records zijn in 3 tot 4 niveaus bereikbaar. Raakt een knoop bij invoegen of verwijderen te vol, dan wordt hij gesplitst, en wordt hij te leeg, dan wordt hij samengevoegd; zo blijven alle bladeren op dezelfde diepte. Een binaire zoekboom met 100 miljoen records heeft minstens ongeveer 27 niveaus, en op elk niveau een ander blok lezen is traag.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Datastructuren en algoritmen

  1. Wat is een geschikte manier om een ijle graaf, een graaf met weinig kanten in verhouding tot het aantal knopen, in het geheugen op te slaan, zoals een wegennet met ongeveer 1 miljoen knopen en 3 miljoen kanten?
  2. In een graaf waarvan de kanten geen gewicht hebben, wil je vanaf een startknoop het kleinste aantal kanten naar elke andere knoop bepalen. Welke combinatie van zoekmethode en datastructuur is geschikt?
  3. In een ongerichte graaf zijn de buren van elke knoop A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. Diepte-eerst zoeken met recursie begint bij knoop A. De buren worden in de vermelde volgorde onderzocht, en zodra een nog niet bezochte knoop wordt gevonden, gaat de zoekactie daarheen. In welke volgorde worden de knopen bezocht?
  4. In een ongerichte graaf zijn de gewichten (afstanden) van de kanten S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3 en A−T: 6. Welk kortste pad van S naar T vindt het algoritme van Dijkstra, en wat is de lengte ervan?
  5. Aan welke voorwaarde moet de graaf voldoen opdat het algoritme van Dijkstra juiste kortste paden vindt?