B Tree och B + Tree Datastruktur i C ++

b tree b tree data structure c

Denna C ++ handledning förklarar B Tree & B + Tree Datastrukturer. De används för att lagra data på diskar när hela data inte kan lagras i huvudminnet:

B-träd är ett självbalanserat träd samt ett specialiserat m-vägträd som används för diskåtkomst.

När mängden data som ska lagras är mycket hög kan vi inte lagra hela data i huvudminnet. Därför lagrar vi data på disken. Datatillgång från skivan tar mer tid jämfört med huvudminnet.

När antalet nycklar för data som lagras på diskar är mycket högt, kommer man vanligtvis åt data i form av block. Tiden för åtkomst till dessa block är direkt proportionell mot trädets höjd.

=> Klicka här för den absoluta C ++ träningsserien.

Vad du kommer att lära dig:

• B-Tree In C ++
  • Grundläggande funktioner för B-Tree
    • # 1) Söker
    • # 2) Insättning
    • # 3) Radering
  • Tillämpningar av B-träd
• B + träd i C ++
  • Fördelar med B + träd
• Skillnaden mellan B-Tree och B + Tree
• Slutsats
  • Rekommenderad läsning

B-Tree In C ++

B-trädet är ett platt träd, dvs. höjden på B-trädet hålls på ett minimum. Istället sätts så många nycklar i varje nod i B-trädet. Genom att hålla B-trädets höjd till ett minimum är åtkomsten snabbare jämfört med andra balanserade träd som AVL-träd.

Ett typiskt B-träd visas nedan:

skillnad mellan testfall och testscenario

Generellt hålls nodstorleken i B-trädet densamma som blockstorleken.

Nedan listas några av egenskaperna hos B-Tree.

• Alla blad av B-träd är på samma nivå.
• Ett B-träd av ordning m kan ha högst m-1 nycklar och m barn.
• Varje nod i B-trädet har högst m barn.
• Rotnoden måste ha minst två noder.
• Varje nod utom rotnoden och bladnoden innehåller m / 2 barn.

Därefter diskuterar vi några av de grundläggande funktionerna för B-tree.

Grundläggande funktioner för B-Tree

Nedan följer några av de grundläggande funktionerna för B-Tree.

# 1) Söker

Att söka i B-träd liknar det i BST. I ovanstående träd, om vi vill leta efter artikel 3, fortsätter vi enligt följande:

• Jämför 3 med rotelement. Här, 3<6 and 3 <15. So we proceed to the left subtree.
• Jämför 3 med 4 i vänster underträd. Som 3<4, we proceed to the left subtree of node 4.
• Nästa nod har två nycklar, 2 och 3. 3> 2 medan 3 = 3. Så vi har hittat nyckeln vid denna nod. Återgå till den hittade platsen.

Att söka i B-träd beror på trädets höjd. Det tar vanligtvis O (log n) tid att söka efter ett visst objekt.

# 2) Insättning

Införandet av ett nytt objekt i B-träd görs på bladnodnivå.

Nedan följer stegsekvensen (algoritm) för att infoga ett nytt objekt i B-trädet.

• Korsa B-trädet för att hitta en plats vid bladnoderna för att infoga objektet.
• Om bladnoden innehåller nycklar
• Annars om bladnodnycklar = m-1, då:
  • Infoga ett nytt objekt i ett ökande antal objekt.
  • Ta medianen av noder och dela noden i två noder.
  • Tryck median till dess överordnade nod.
  • Om föräldernodnyckel = m-1 upprepar du stegen ovan för föräldernoden också. Detta görs tills vi hittar rätt bladnod.
• Slutligen sätter du in elementet.

Vi har visat infogning i B-träd enligt följande.

Låt oss infoga artikel 70 i trädet som visas nedan.

vad används c ++ för

Det angivna trädet är med minsta grad 'm' = 3. Därför kan varje nod rymma, 2 * m -1 = 5 nycklar inuti det.

Nu infogar vi artikel 70. Eftersom vi kan ha 5 nycklar i en nod, jämför vi element 70 med rotelementet 30. Sedan 70> 30 kommer vi att infoga objekt 70 i rätt underträd.

I rätt underträd har vi en nod med tangenterna 40, 50, 60. Eftersom varje nod kan ha 5 nycklar i kommer vi att infoga objektet 70 i själva denna nod.

Efter införandet ser B-trädet ut enligt följande.

# 3) Radering

Precis som införandet utförs raderingen av nyckeln också på bladnodnivå. Men till skillnad från infogning är radering mer komplicerad. Nyckeln som ska raderas kan vara antingen en bladnod eller en intern nod.

För att radera en nyckel följer vi nedanstående sekvens av steg (algoritm).

1. Leta reda på bladnoden.

två. Om antalet nycklar i en nod> m / 2 raderar du den angivna nyckeln från noden.

3. Om bladnoden inte har m / 2-nycklar måste vi fylla i nycklarna genom att ta nycklar från höger eller vänster underträd för att bibehålla B-trädet.

Vi följer dessa steg:

• Om det vänstra underträdet innehåller m / 2-element trycker vi på det största elementet till modernoden och flyttar sedan det mellanliggande elementet till den plats där nyckeln raderades.
• Om det högra underträdet innehåller m / 2-element trycker vi på det minsta elementet till föräldernoden och flyttar sedan det mellanliggande elementet till den plats där nyckeln raderades.

Fyra. Om ingen nod har m / 2-noder kan ovanstående steg inte utföras, så vi skapar en ny bladnod genom att sammanfoga två bladnoder och det mellanliggande elementet i föräldernoden.

5. Om en förälder saknar m / 2-noder upprepar vi ovanstående steg för föräldernoden i fråga. Dessa steg upprepas tills vi får ett balanserat B-träd.

Nedan visas en illustration för att ta bort en nod från B-trädet.

Tänk på följande B-träd igen.

Låt oss anta att vi vill ta bort nyckeln 60 från B-trädet. Om vi ​​kontrollerar B-trädet kan vi upptäcka att nyckeln som ska raderas finns i bladnoden. Vi tar bort nyckeln 60 från denna bladnod.

Nu kommer trädet att se ut som visas nedan:

Vi kan märka att efter att tangenten 60 har tagits bort uppfyller B-trädbladnoden de nödvändiga egenskaperna och vi behöver inte göra några fler ändringar av B-trädet.

Men om vi var tvungna att ta bort nyckel 20, skulle bara nyckel 10 ha kvar i vänster bladnod. I det här fallet skulle vi behöva flytta rot 30 till bladnoden och flytta tangenten 40 till roten.

När du tar bort en nyckel från B-trädet, bör du därför vara försiktig och egenskaperna hos B-trädet bör inte brytas.

Traversal In B Tree

Traversal i B-träd liknar också inorder-traversal i BST. Vi börjar rekursivt från vänster och kommer sedan till roten och fortsätter mot vänster subtree.

Tillämpningar av B-träd

• B-träd används för att indexera data, särskilt i stora databaser, eftersom tillgång till data som lagras i stora databaser på diskar är mycket tidskrävande.
• Att söka efter data i större osorterade datamängder tar mycket tid men detta kan förbättras avsevärt med indexering med B-träd.

B + träd i C ++

B + träd är en förlängning av B-trädet. Skillnaden i B + -träd och B-träd är att i B-träd kan nycklarna och posterna lagras såväl interna som bladnoder medan i B + -träd lagras posterna som bladnoder och nycklarna lagras endast i interna noder.

Posterna är länkade till varandra på ett länkat listmode. Detta arrangemang gör sökningar av B + träd snabbare och effektivare. Interna noder i B + -trädet kallas indexnoder.

B + träd har två ordningar, dvs en för interna noder och en för blad eller externa noder.

Ett exempel på B + Tree visas nedan.

Eftersom B + -trädet är en förlängning av B-trädet, finns fortfarande de grundläggande operationerna som vi diskuterade under ämnet B-trädet.

Samtidigt som vi sätter in och tar bort bör vi bibehålla de grundläggande egenskaperna för B + Trees intakta. Radering i B + -trädet är dock jämförelsevis enklare eftersom data endast lagras i bladnoderna och de kommer alltid att raderas från bladnoderna.

vad är en 7z-fil mac

Fördelar med B + träd

• Vi kan hämta poster i lika stort antal diskåtkomst.
• Jämfört med B-trädet är höjden på B + -trädet mindre och förblir balanserad.
• Vi använder nycklar för indexering.
• Data i B + -trädet kan nås sekventiellt eller direkt när bladnoderna är ordnade i en länkad lista.
• Sökningen går snabbare eftersom data lagras endast i bladnoder och som en länkad lista.

Skillnaden mellan B-Tree och B + Tree

Slutsats

I denna handledning har vi diskuterat B-träd och B + träd i detalj. Dessa två datastrukturer används när det finns mycket mycket datamängd och när hela datan inte kan lagras i huvudminnet. För att lagra data på diskar använder vi oss av B-tree och B + tree.

B-trädsökning är något långsammare eftersom data lagras i interna noder såväl som bladnoder i den. B + träd är en förlängning av B-träd och informationen här lagras endast i bladnoder. På grund av denna faktor är sökning i ett B + -träd snabbare och effektivare.

=> Besök här för en komplett lista över C ++ -studier.

Rekommenderad läsning

• AVL-träd- och högdatastruktur i C ++
• Länkad listdatastruktur i C ++ med illustration
• Kodatastruktur i C ++ med illustration
• Stack datastruktur i C ++ med illustration
• Cirkulär länkad datastruktur i C ++ med illustration
• Introduktion till datastrukturer i C ++
• Prioriterad ködatastruktur i C ++ med illustration
• Dubbelt länkad datastruktur i C ++ med illustration