Scribd Logo
Upload

Welcome to Scribd!

  • 10 views

    1714368198-b & B+ Tree

    Uploaded by

    manav.7909mka

    Copyright:

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

    1714368198-b & B+ Tree

    Uploaded by

    manav.7909mka
    10 views16 pages

    Original Title

    1714368198-b_&_b+_tree

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

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

    1714368198-b & B+ Tree

    Uploaded by

    manav.7909mka

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 16

    B-Tree

    B Tree
    A B-tree of order m is an m-way tree (i.e., a tree where
    each node may have up to m children) in which:
    1.the number of keys in each non-leaf node is one less
    than the number of its children and these keys partition
    the keys in the children in the fashion of a search tree
    2.all leaves are on the same level
    3.all non-leaf nodes except the root have at least m / 2
    children
    4.the root is either a leaf node, or it has from two to m
    children
    5.a leaf node contains no more than m – 1 keys
    Operations
    • B-Tree of order 4
    – Each node has at most 4 pointers and 3 keys,
    and at least 2 pointers and 1 key.
    • Insert: 5, 3, 21, 9, 1, 13, 2, 7, 10, 12, 4, 8
    Insert 5, 3, 21

    *5* a

    *3*5* a

    * 3 * 5 * 21 * a
    Insert 9
    *9* a
    b c
    *3*5* * 21 *

    Node a splits creating 2 children: b and c


    Insert 1, 13
    *9* a
    b c
    *1*3*5* * 13 * 21 *

    Nodes b and c have room to insert more elements


    Insert 2
    *3*9* a

    b d c
    *1*2* *5* * 13 * 21 *

    Node b has no more room, so it splits creating node d.


    Insert 7, 10
    *3*9* a

    b d c
    *1*2* *5*7* * 10 * 13 * 21 *

    Nodes d and c have room to add more elements


    Insert 12
    * 3 * 9 * 13 * a

    b d c e
    *1*2* *5*7* * 10 * 12 * * 21 *

    Nodes c must split into nodes c and e


    Insert 4
    a
    * 3 * 9 * 13 *

    b d c e
    *1*2* *4*5*7* * 10 * 12 * * 21 *

    Node d has room for another element


    Insert 8
    *9* a

    f g
    *3*7* * 13 *

    b d h c e
    *1*2* *4*5* *8* * 10 * 12 * * 21 *
    Create a B-tree of order 5 with keys 10, 20, 50, 60, 40,
    80, 100, 70, 130, 90, 30, 120, 140, 160

    Construct a B-tree of order 5 and keys arrive in the


    following order:1, 12, 8, 2, 25, 5, 14, 28, 17, 7, 52,
    16, 48, 68, 3, 26, 29, 53, 55, 45.
    Solution of Ques 2.

    17

    3 8 28 48

    1 2 6 7 12 14 16 25 26 29 45 52 53 55 68
    What is a B+ Tree?
    – A variation of B trees in which
    – internal nodes contain only search keys (no data)
    – Leaf nodes contain pointers to data records
    – Data records are in sorted order by the search key
    – All leaves are at the same depth

    You might also like