Waarom duurt zoeken eigenlijk zo lang?

[Verwijderd]

Opeens vroeg ik mij af: waarom duurt zoeken op een harde schijf eigenlijk zo lang, zowel in Windows als in Linux? Ik heb echt het gevoel alsof er letterlijk de hele harde schijf afgezocht wordt.

Ik dacht altijd dat er bij bijna elk filesystem gebruik gemaakt werd van een tabel van bestanden aan het begin van de hard disk, dus een lijst met alle bestanden erin met verwijzingen naar die bestanden om ze fysiek op de schijf te kunnen vinden. Als dat zo zou zijn en ik naar een bestand zoek, hoeft het OS toch alleen maar even door die tabel heen te fietsen om het bestand te vinden? Immers is het enkel metadata (bestandsnaam, eventueel datum of grootte) waar ik naar zoek.

Gerelateerd hieraan: als ik door mappen blader van een schijf die in standby staat, gaat de schijf weer draaien. Kan die tabel, als die aanwezig is, niet gewoon volledig in het RAM geplaatst worden zodat het spinnen niet nodig is voor simpele browse/zoek acties, en pas gaan spinnen bij een echte read/write van bestandsgegevens?

[F_J_K]

Het is jaaaren geleden dat ik hier naar heb gekeken, dus neem het met een korreltje zout: inderdaad is er afhankelijk van het bestandsssyteem "gewoon" een index. Uitgaande van NTFS: dan nog moet een hele (iirc B+) boom worden doorzocht in de MFT. In deze MFT zitten trouwens ook meteen (vanuit efficiency-oogpunt) kleine files opgenomen. Aangezien dit $MFT 'file' standaard al een dozijn procent van je hardeschijfgrootte is, valt er heel wat te doorzoeken - ondanks dat je qua zoeken met een B+-boom best goed zit. Maar ik kan me zo voorstellen dat de index niet de bestandsnaam is, maar iets anders. En dan moet je dus gemiddeld genomen (bij een volledig gevulde MFT) 6% van je hardeschijfgrootte inlezen en nog interpreteren ook.

Dat geeft meteen antwoord op je RAM-vraag: koop heel veel meer RAM

Edit: als ik snel even zoek lijkt mijn geheugen het nog te doen
Om snel te zoeken kan je dus een indexeringtool gebruiken, die wel de bestandsnaam als index gebruikt. Dan gaat het heel; erg veel sneller. Als dat ook een B+-boom is, zit je al snel aan O(log n). En da's ook bij enorme hoeveelheden files rap.

[ Voor 16% gewijzigd door F_J_K op 28-04-2009 20:27 ]

[Verwijderd]

Die tabel is heel groot. Zomaar in je ram plaatsen gaat dus niet. Daarnaast staat die tabel ook in stukjes in een boom structuur verspreidt over de schijf. Daarom duurt het zoeken zolang, hij moet al die kleine stukjes langs. Zowel op Linux als op Windows kun je wel een index file bouwen wat eigenlijk een platgeslagen file is van je tabel. Deze doorzoeken gaat stukken sneller.

[jan99999]

In (sommige) linux kun je in het indexerings programma aangeven wat hij indexeren moet, dus bijv waar veel files staan die je wilt doorzoeken.

[Verwijderd]

De term B+-boom zegt me even helemaal niets, dus ik ga wel even kijken wat dat nou precies inhoudt. Zelf een index maken duurt natuurlijk ook wel een tijdje, maar het zoeken gaat dan wel echt snel in ieder geval. Maar hier bestaan uiteraard al tools voor.

Maar ik vind het wel raar dat dan uit designoogpunt er niet standaard een index aanwezig is om het zoeken te versnellen. Misschien wordt dit mij meer duidelijk als ik dat verhaal over B+-bomen bekijk.

[F_J_K]

Is ook niet zo relevant als je niet in detail wil gaan. Samenvatting: het is veel. Neem een dedicated indexeringtool.

Veel sneller dan de huidige oplossingsrichtingen gaat waarschijnlijk niet (die genoemde B+ tree is juist opgezet om enorm veel sneller dan 'gewoon een lijst' te kunnen zoeken). Zoeken naar bepaalde bestanden is zegmaar niet het belangrijkste dat een filesystem (c.q. het OS erboven) moet kunnen doen. Denk aan de vele andere metadata, en natuurlijk robuustheid.

[ Voor 12% gewijzigd door F_J_K op 29-04-2009 07:03 ]

[Verwijderd]

Verwijderd schreef op dinsdag 28 april 2009 @ 19:50:
Opeens vroeg ik mij af: waarom duurt zoeken op een harde schijf eigenlijk zo lang, zowel in Windows als in Linux? Ik heb echt het gevoel alsof er letterlijk de hele harde schijf afgezocht wordt.

Gebruik je nog XP ?

[Verwijderd]

Een index file bijhouden is ook een vrij dure operatie. Je moet elke keer elke alteratie bijhouden. Normaal gesproken doet je systeem dat op het moment dat hij in idle staat verkeerd. Maar in sommige gevallen is het helemaal niet wenselijk dat hij de index file bijwerkt. Denk bijvoorbeeld aan laptop's waarmee je zo lang mogelijk op de accu wilt werken.

Verder heeft elk OS wel een index optie die meestal standaard meegeleverd wordt. Linux/BSD hebben locate, OS X heeft spotlight en Windows heeft iets van Search nog wat.