Binaire-tree data-opslag implementatie

Ik ben begonnen met het gebruik van binaire bomen in c ++, en ik moet zeggen dat ik het idee echt leuk vind en dat dingen voor mij duidelijk zijn, totdat ik denk aan het opslaan van gegevens op de schijf in een volgorde waarin ik later meteen een stuk gegevens kan lezen. Tot nu toe heb ik alles (knooppunten) in de ram opgeslagen ... maar dit is slechts een eenvoudige en niet echte app. Ik ben niet geïnteresseerd in het opslaan van de hele binaire boom op de schijf, want dat zou weer nutteloos zijn, omdat je het opnieuw moet lezen in het geheugen! wat ik zoek is een methode net zoals bijvoorbeeld MYSQL. Ik heb hier geen goed artikel over gevonden, dus ik zou het op prijs stellen als iemand een aantal urls of boeken opneemt.

1
Om het antwoord van pst uit te werken, gebruiken databases meestal een andere gegevensstructuur, een B-structuur die vergelijkbaar is met een BST, maar veel betere prestaties biedt voor gebruik op schijf. Het slaat alles in gesorteerde volgorde op, zoals een BST, maar slaat meer waarden op in elk knooppunt. Veel standaardalgoritmen-teksten, zoals CLRS, bespreken hoe deze structuren kunnen worden gebruikt.
toegevoegd de auteur templatetypedef, de bron
Een array gaat over de enige datastructuur die je "instant" kunt doen (vermoedelijk impliceer je O (1)) random reads. Al het andere vereist volgende aanwijzingen/indexen, die noodzakelijkerwijs meerdere toegangen vereisen.
toegevoegd de auteur Oliver Charlesworth, de bron
Lees de vraag opnieuw, ik ben op zoek naar een manier om de gegevens in een gesorteerde volgorde op te slaan, waar ik onmiddellijk een aantal gegevens kan lezen!
toegevoegd de auteur iNDicator, de bron
Hmm ik zie dit nog steeds als in-RAM opslaan, maar ik moet dan iets missen. Dus met die "Heap-implementatie" hoe ga ik de gegevens die op de schijf zijn opgeslagen wijzen?
toegevoegd de auteur iNDicator, de bron
Er zijn veel artikelen over B-trees (B +, etc.). Dat komt vaker voor in databases ;-) Het bekijken van [binary] heap -implementaties kan ook nuttig zijn. Ik heb talloze implementaties gezien die werden ondersteund door een array. (bijvoorbeeld en.wikipedia.org/wiki/Binary_heap#Heap_implementation )
toegevoegd de auteur user166390, de bron
Ik heb het gelezen :) Dat is hoe databases werken. B-tree varianten worden vaak gebruikt omdat ze "slappe" regels toevoegen die onnodige gegevensverschuivingen binnen elke "pagina" vermijden. (Maar te veel speling en dan verspilde reads gebeuren ...)
toegevoegd de auteur user166390, de bron
@iNDicator Stel je voor dat de schijf de array is. mmap zal het zelfs als zodanig ontmaskeren. Natuurlijk zijn databases over het algemeen veel slimmer dan dit en zullen ze vaak in "pagina's" werken (lees een pagina, update een pagina [in het geheugen], schrijf een pagina). Ze gebruiken technieken om te beslissen welke pagina ('s) in het geheugen moeten worden bewaard, omdat de schijf-IO veel duurder is dan het hoofdgeheugen. Een eenvoudige mmap zal het besturingssysteem vertrouwen "doet zijn werk goed genoeg" met zijn eigen FS-buffers en read-ahead-heuristieken.
toegevoegd de auteur user166390, de bron
(Het is niet zo dat OS FS-buffers niet goed zijn - het is gewoon dat een database meer kennis/informatie heeft om betere keuzes te maken voor een bepaald scenario voor gegevensgebruik.)
toegevoegd de auteur user166390, de bron

1 antwoord

Het belangrijkste verschil met b-tree en b + tree: - De bladknooppunten zijn gekoppeld voor het snel opeenvolgend lezen van vergrendelingen. Kan naar oplopend wijzen, kan aflopend wijzen, of beide (zoals ik in een IBM DB heb gezien)

  • Je zou het op schijf moeten schrijven, als de tafel of het bestand groter wordt, zul je geheugenproblemen hebben. (SEEK-bewerkingen op bestanden ZIJN ECHT SNEL .. Je kunt een bestand van 1 GB op schijf maken in minder dan 1 seconde ... C# filestream, methode .SetFilesize)

  • Als het u lukt om meerdere lezers/schrijvers te hebben, moet u concurrency controle hebben over de index en tabel (of bestand) .... Gaat u dat doen in het geheugen? Als er zich een stroomstoring voordoet, hoe rol je dan terug? Ja, dat doet u niet.

IE: veld f1 is geïndexeerd.

WAAR 1 = 1 (geen toegang tot b + tree, geef me alles en de bestelling is niet relevant)

WHERE 1 = 1 ORDER BY f1 ASC/DESC (Need to access b + tree, geef me alles in oplopende/aflopende volgorde)

WHERE f1>=100 (Need to access b+tree, lock up where the leaf node =100 and give all leaf node items following right pointers. If this process is a multithreaded read, they probablly come with a strange order, but no problem... no order by in clause).

WHERE f1>=100 order by f1 asc (Need to access b+tree, lock up where the leaf node =100 and give all leaf node items following right pointers. This process shouldnt be multithreaded following the b+tree, comes naturally in order.

Veld f2 geïndexeerd met een b + tree en type string.

Waar de naam als '% ODD' (Intern, de vergeleken waarde moet worden omgekeerd en het symbool alle blijft aan het einde Zoals begint met 'DDO' en eindigt met iets. 'DDOT' is in de groep dus 'TODD' moet behoren tot de resultaat !!!! Lastige, lastige logica; P)

met deze verklaring, WAAR naam als '% OD%' (heeft in het midden 'OD'). De dingen worden heet :)))) Intern is het resultaat de UNIE van het subresultaat voor 'OD%' met het subresultaat omgekeerd 'DO%'. Daarna verwijdert in het midden de start 'OD' en eindigt 'OD' zonder 'OD', anders is het een geldig resultaat ('ODODODODOD' is het een geldig resultaat. Ongeldige resultaten 'ODABCD' en 'ABCDOD').

Overweeg wat ik heb gezegd en kijk nog een paar dingen als je diep gona doet: - FastIO op bestanden: C# Filestream no_buffered_flag, wriththought disk flag on. - Geheugentoewijzingsbestanden/geheugenweergaven: Ja, we kunnen een enorm bestand in kleine hoeveelheden manipuleren als we het nodig hebben - Indexen: Bitmapindex, hashindex (hashfunctie, perfecte hashfunctie; dubbelzinnigheid van de hashfunctie), schaarse index, dichte index, b + boom, r-boom, omgekeerde index. - Multithread: lock, mutexes, semaforen - Transactionele concessies (logbestand, 2 fase commit, 3 fase commit); - Sloten (database, tabel, pagina, record) - Salsloten: 3 manieren om het te doden (langer conflicterend proces; jonger tegenstrijdig proces; het proces dat meer objecten vergrendelt). Moderne RDBM's gebruiken een mix van de 3 manieren ... - SQL-ontleding (AST-structuur). - Recurrente zoekopdrachten in caching plaatsen. - Triggers, procedures, weergaven, etc. - Parameters doorgeven aan de procedures (kan het objecttype gebruiken; P)

  • DONT LOAD EVERYTHING IN MEMORY,INTELLIGENT SOLUTIONS LOADS PARTS AS THEY NEED IT AND RELEASES WHEN ITS NO LONGER USABLE. Why=> your db engine (and PC) becomes more responsive using less memory. Using b+tree for lockup the branch leaf nodes needs just 2 Disk IO's. Knowing the lockup value, you get the record long pointer. SEEK the main file for the position, read the content. This is too fast. Memory is faster... Yes it is, but can you put 10 GB's of a b+tree on memory? If so, how your DB engine program starts to behave? Slowlly?

Vergeet binaire bomen en convencional btrees: het zijn academische tutorials. In het echte leven worden ze vervangen door hashtables of b + trees (B PLUS TREE toont opslag en bestelde oplopend- http: //en.wikipedia.org/wiki/B%2B_tree )

  • Overweeg om dataspaces te gebruiken voor de db-gegevens in meerdere schijven. U kunt de prestaties van Disk IO parallel laten lopen. Vergeet niet om ze te spiegelen ... Elke dataspace zou een fragment van de tabel moeten hebben met een fragment van de index, met een gedeeltelijk logbestand. U zou de coördinator moeten ontwikkelen die de vragen voor de subeenheden op een slimme manier presenteert.

IE: 3 dataspaces ... INSERT INTO etc ...... zou alleen in 1 tabelruimte moeten voorkomen.

maar selecteer * van TB_XPTO, moet aan alle gegevensruimten worden gepresenteerd.

selecteer * uit TB_XPTO volgorde door een geïndexeerd veld, moet worden gepresenteerd aan alle dataspaces. Elke dataruimte voert de instructie uit, dus nu hebben we een 3 subsets per suborder.

Het resultaat zal op de coördinator zijn, waar het opnieuw zal worden geordend. Verwar, MAAR SNEL !!!!!!

De coördinator moet de hoofdtransactie besturen.

als dataspace A gecommit dataspace B gecommit dataspace C bevindt zich in een niet-gecommitteerde staat de coördinator rolt een C, B en A terug.

als dataspace A gecommit dataspace B gecommit dataspace C gecommiteerd de coördinator legt de algehele transactie vast.

COORDINATOR LOGBOEK: CREËER MASTER TRANSACTIE UID 121212, KIND TRANSACTIES (1111,2222,3333)

DATA RUIMTE EEN LOGBOEK 1111 INSERT len byte array 1111 INSERT len byte array COMMIT 1111

DATA RUIMTE B LOG 2222 INSERT len byte array 2222 INSERT len byte array COMMIT 2222

DATA SPACE C LOG 3333 INSERT len byte array 3333 ---> No more nothing..... Power failure here!!!!!!!

Controleer in de startup-coördinator of de db correct is afgesloten, zo niet, dan zal het zijn logbestand controleren. Er ontbreekt een master-COMMIT-regel zoals COMMIT 121212. Daarom vraagt ​​het de gegevensruimten voor de logboekconsistentie. A, B geeft COMMITED uit, maar C, na het controleren van zijn logbestand, detecteert een fout. Antwoorden ONGEMOKEN. Hoofdcoördinator FORCES TABLESPACE A, B, C VOOR ROLLBACK 1111,2222,3333 Daarna rolt hij zijn master-transactie terug en zet DB-status = OK.

Het belangrijkste punt hier is snelheid bij invoegen, selecteren, bijwerken en verwijderen

  • Overweeg om de index goed in balans te houden. Veel verwijderingen op de index zullen het uit balans brengen. Een ongebalanceerde index verlaagt de prestaties ... Voeg een heap toe aan het hoofd van het indexbestand om het te beheren. Sommige wiskunde zou hier helpen. Als het aantal verwijderingen groter is dan 5% van de records, moet u het balanceren en de teller resetten. Als een update is voltooid in een geïndexeerd veld, moet deze ook worden meegerekend.

  • Wees slim gezien de veldindex. Als de kolom Geslacht is, zijn er slechts 2 opties (ik hoop, lol .... ops, kan ook nullabel zijn ....), een bitmapindex is goed toegepast. Als de onderscheidbaarheid (ik denk dat ik het slecht spellen) van een veld 100% is (alle waarden heterogeen), zoals een reeks toegepast op een veld zoals Oracle, of een identiteitsveld zoals SQL Server, wordt een b + -boom goed toegepast . Als een veld een soort geometrisch type is, zoals in Oracle, is de R-tree de beste. Voor strings is de omgekeerde Index goed toegepast, of b + tree indien heterogeen.

  • Houston, we hebben problemen ... NULL-waardevelden moeten ook in de index worden beschouwd. Het is ook een waarde !! IE: WAAR F1 is null

  • Voeg wat socketfunctionaliteit toe: Async TCP/IP SERVER

-If you delete a record, dont resize the file right now. Mark it as deleted. You should do some metrics here too. If unused space > x and transactions =0, do a database lock and re-allocate pointers, then resize database. Some spaces appears on the DB file, you can try to do some page locks instead of database lock... Things can keep going and no one gets hurt.... Measure the last unlocked page of the DB, lock it for you. Check a deleted page that you can fill with your page. Not Found, release lock; If found, move for the new position, fix pointers, mark old page as deleted, resize file, release lock. Why so many operations? To keep the log well formed!!!! You can split the page in small pages, but you get fragmentation (argh...we lost speed commander?)... 2 algorithms comes here. Best-Fit, and Worst-Fit....Google it. The best is .... using both :P

En als je al deze dingen oplost, kun je hardop roepen "DAM, ik heb een database ... IM GONA NAME IT ORACLE !!!!" ; P

2
toegevoegd
WOW, dit is een echt antwoord! Bedankt voor het geweldige antwoord!
toegevoegd de auteur iNDicator, de bron