C# - binary tree implementatie on disk

[SideShow]

Hallo

Ik ben bezig met een pet project die dienst doet als simpele document database. Dit doe ik puur voor mezelf en om bij te leren.
Ondertussen ben ik gekomen aan het punt waar ik een relatief simpele where clause mogelijk wil maken.
Ik wil een soort binary tree implementeren, maar dan niet in memory, wel op schijf. Dit zou ook meteen sortering mogelijk maken.

Nu, ik zat wat te denken aan hoe ik node referenties moest aanpakken, en kwam tot de conclusie dat ik dit kan doen net zoals dit in het werkgeheugen zou gebeuren: met "adressen" of in het geval van een file de byte positie binnenin de file.

Dit is puur hobby, maar zou toch eens het idee willen horen van meer ervaren mensen. Sla ik hier de bal volledig mis of zou dit een mogelijkheid kunnen zijn?

Het zoeken zal voorlopig simpele waarden zoals nummers en datums betreffen; geen text search dus. Voorlopig zou ik ook niet weten hoe daar aan te beginnen trouwens. :-)

[Woy]

Kijk hier eens naar: MSDN: Memory-Mapped Files

[HMS]

Kijk ook eens naar een B-Tree, die is geoptimaliseerd om op disk gebruikt te worden. (Wordt zover ik weet ook door 'grote' databases als MongoDB / MySQL / SQL Server gebruikt)

[H!GHGuY]

van on-disk b-tree structuren kun je bovendien code vinden op het net.

[Soultaker]

SideShow schreef op maandag 10 december 2012 @ 20:26:
Nu, ik zat wat te denken aan hoe ik node referenties moest aanpakken, en kwam tot de conclusie dat ik dit kan doen net zoals dit in het werkgeheugen zou gebeuren: met "adressen" of in het geval van een file de byte positie binnenin de file.

Dit kan inderdaad prima; behalve file offsets kun je ook logische adressen gebruiken (blok zoveel in het bestand). Grootste voordeel daarvan is dat je dan met 32-bits adressen nog wat verder komt. (Geen idee of dat relevant is in jouw geval, maar toch.)

Het lastigste deel is waarschijnlijk het noodzakelijke geheugenbeheer als je keys/values variabele lengte kunnen hebben, maar als je je tot getallen van een vaste grootte beperkt, is dat misschien geen probleem.

HMS schreef op dinsdag 11 december 2012 @ 09:41:
Kijk ook eens naar een B-Tree, die is geoptimaliseerd om op disk gebruikt te worden.

Inderdaad, op een harde schijf telt de seek time nog zwaarder mee, en dus biedt een ondiepe boomstructuur veel performancewinst. Ik denk dat B+-trees specifiek de meest performante datastructuren zijn die nog enigzins simpel te implementeren zijn (naast on-disk hashtables, maar die slaan geen gesorteerde data op).

[ Voor 7% gewijzigd door Soultaker op 11-12-2012 13:39 ]

[beany]

Mocht je met BTree's aan de slag gaan, verdiep je dan in B+Tree( Wikipedia: B+ tree ). Maar kijk ook eens naar bestaande implementaties om inspiratie op te doen, bv: http://sop.codeplex.com/ (met hier het bijbehorend codeproject artikel: http://www.codeproject.co.../B-Tree-Sorted-Dictionary ).

En als je hier serieus iets mee wil gaan doen, hou dan vanaf het begin af aan rekening met Transacties. Achteraf een transactie systeem implementeren is... ehhh, simpelweg: ruk (been there).