Scribd Logo
Upload

Welcome to Scribd!

  • 114 views

    B+ Tree: What Is A B+ Tree Searching Insertion Deletion

    Uploaded by

    mudit bhargava
    B+ trees allow for efficient insertion, retrieval, and removal of records. They store records in leaf nodes and keys in internal nodes, with leaf nodes linked in a linked list. This structure allows faster searching than many other trees. Insertion may cause splitting of nodes, requiring rearrangement to maintain balance, while deletion may combine nodes or replace keys in internal nodes. B+ trees are commonly used to store large datasets across storage levels.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd

    B+ Tree: What Is A B+ Tree Searching Insertion Deletion

    Uploaded by

    mudit bhargava
    114 views24 pages
    B+ trees allow for efficient insertion, retrieval, and removal of records. They store records in leaf nodes and keys in internal nodes, with leaf nodes linked in a linked list. This structure allows faster searching than many other trees. Insertion may cause splitting of nodes, requiring rearrangement to maintain balance, while deletion may combine nodes or replace keys in internal nodes. B+ trees are commonly used to store large datasets across storage levels.

    Original Title

    B+tree-Example-1

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    B+ trees allow for efficient insertion, retrieval, and removal of records. They store records in leaf nodes and keys in internal nodes, with leaf nodes linked in a linked list. This structure allows faster searching than many other trees. Insertion may cause splitting of nodes, requiring rearrangement to maintain balance, while deletion may combine nodes or replace keys in internal nodes. B+ trees are commonly used to store large datasets across storage levels.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    114 views24 pages

    B+ Tree: What Is A B+ Tree Searching Insertion Deletion

    Uploaded by

    mudit bhargava
    B+ trees allow for efficient insertion, retrieval, and removal of records. They store records in leaf nodes and keys in internal nodes, with leaf nodes linked in a linked list. This structure allows faster searching than many other trees. Insertion may cause splitting of nodes, requiring rearrangement to maintain balance, while deletion may combine nodes or replace keys in internal nodes. B+ trees are commonly used to store large datasets across storage levels.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    You are on page 1of 24

    B+ Tree

     What is a B+ Tree
     Searching
     Insertion
     Deletion
    What is a B+ Tree
     A B+ tree is a variant of B-tree which stores sorted
    data in a way that allows for efficient insertion,
    retrieval and removal of records each of which is
    identified by index key. A B+ tree stores all the
    records at the leaf node of the tree and only keys are
    stored in the internal nodes. The leaf nodes of B+
    tree are often linked with linked list.
    Advantage of B+ Tree over B-tree
     A B tree can store both keys and records in internal
    nodes while B+ tree stores all the records at the leaf
    level of the tree and index keys are stored in the
    internal nodes.
     The leaf nodes of a B+ tree are often linked to one
    another in a linked list which supports both sequential
    and random access making the queries simpler and
    more efficient.
     B+ tree are used to store large amount of data that
    can not be stored in the main memory. So, in b+ tree,
    the secondary memory is used to store leaf nodes of
    the tree and primary memory is used to store internal
    nodes of the tree.
    What is a B+ Tree
    What is a B+ Tree
    2.The searching time in a B+ tree is much
    shorter than most of other kinds of trees. For
    example: It is assumed that to search a data
    in one million key-values, a balanced binary
    requires about 20 block reads, in contrast
    only 4 block reads is required in B+ Tree.
    Searching
     Since no structure change in a B+ tree during
    a searching process, so just compare the key
    value with the data in the tree, then give the
    result back.
    For example: find the value 45, and 15 in
    below tree.
    Searching
     Result:
    1. For the value of 45, not found.
    2. For the value of 15, return the position
    where the pointer located.
    Insertion
    The insert algorithm for B+ Tree
    Data Index Action
    Page Page
    Full Full
    NO NO Place the record in sorted position in the appropriate leaf page

    YES NO 1. Split the leaf page


    2. Place Middle Key in the index page in sorted order.
    3. Left leaf page contains records with keys below the middle key.
    4. Right leaf page contains records with keys equal to or greater than the
    middle key.
    YES YES 1. Split the leaf page.
    2. Records with keys < middle key go to the left leaf page.
    3. Records with keys >= middle key go to the right leaf page.
    Split the index page.
    4. Keys < middle key go to the left index page.
    5. Keys > middle key go to the right index page.
    6. The middle key goes to the next (higher level) index.

    IF the next level index page is full, continue splitting the index pages.
    Insertion
     Since insert a value into a B+ tree may cause
    the tree unbalance, so rearrange the tree if
    needed.
     Example #1: insert 28 into the below tree.

    25 28 30
    Insertion
     Result:
    Insertion
     Example #2: insert 70 into below tree
    Insertion
     Process: split the tree

    50 55 60 65 70

    50 55 60 65 70
    Insertion
     Result: chose the middle key 60, and place it
    in the index page between 50 and 75.
    Insertion
     Exercise: add a key value 95 to the below
    tree.

    75 80 85 90 95

    75 80 85 90 95
    25 50 60 75 85
    Insertion
     Result: again put the middle key 60 to the
    index page and rearrange the tree.
    Deletion
     Delete algorithm for B+ trees

    Data Page Below Fill Index Page Below Fill Action


    Factor Factor
    NO NO Delete the record from the leaf page. Arrange
    keys in ascending order to fill void. If the key of
    the deleted record appears in the index page,
    use the next key to replace it.
    YES NO Combine the leaf page and its sibling. Change
    the index page to reflect the change.

    YES YES 1. Combine the leaf page and its sibling.


    2. Adjust the index page to reflect the
    change.
    3. Combine the index page with its sibling.

    Continue combining index pages until you


    reach a page with the correct fill factor or
    you reach the root page.
    Deletion
     Same as insertion, the tree has to be rebuild if the
    deletion result violate the rule of B+ tree.
     Example #1: delete 70 from the tree

    This is OK.
    60 65
    Deletion
     Result:
    Deletion
    Example #2: delete 25 from below tree, but 25
    appears in the index page.
    But…

    28 30
    This is
    OK.
    Deletion
     Result: replace 28 in the index page.

    Add 28
    Deletion
     Example #3: delete 60 from the below tree

    65

    50 55 65
    Deletion
     Result: delete 60 from the index page and
    combine the rest of index pages.
    Conclusion
     For a B+ Tree:
     It is easy to maintain it’s balance.
     The searching time is short than most of
    other types of trees.
    Reference
     http://babbage.clarku.edu/~achou/cs160/B+Tr
    ees/B+Trees.htm
     www.csee.umbc.edu/~pmundur/courses/CMS
    C461-05/ch12.ppt

    You might also like