Processing math: 100%
Close
Close Window

DSA Coursenotes

Chapter 12 Week 14

Show Source |    | About   «  11.2. 2-3 Trees   ::   Contents   ::   12.2. SkipLists  »

12.1. B-Trees

12.1.1. B-Trees

12.1.1.1. B-Trees (1)

  • The B-Tree is an extension of the 2-3 Tree.

  • The B-Tree is now the standard file organization for applications requiring insertion, deletion, and key range searches.

    • Databases

    • File Systems

12.1.1.2. B-Trees (2)

  1. B-Trees are always balanced.

  2. B-Trees keep similar-valued records together on a disk page, which takes advantage of locality of reference.

  3. B-Trees guarantee that every node in the tree will be full at least to a certain minimum percentage. This improves space efficiency while reducing the typical number of disk fetches necessary during a search or update operation.

A B-tree of order four

12.1.1.3. B-Tree Definition

  • A B-Tree of order m has these properties:

    • The root is either a leaf or has two children.

    • Each node, except for the root and the leaves, has between ⌈m/2⌉ and m children.

    • All leaves are at the same level in the tree, so the tree is always height balanced.

  • A B-Tree node is usually selected to match the size of a disk block.

    • A B-Tree node could have hundreds of children.

12.1.1.5. B+-Trees

  • The most commonly implemented form of the B-Tree is the B+-Tree.

  • Internal nodes of the B+-Tree do not store record – only key values to guild the search.

  • Leaf nodes store records or pointers to records.

  • A leaf node may store more or less records than an internal node stores keys.

12.1.1.6. 23+-Tree Build Example

1 / 28 Settings
<<<>>>

Example 2-3+ Tree Visualization: Insert

Created with Raphaël 2.1.2
Proficient Saving... Error Saving
Server Error
Resubmit

An example of building a “2−3+ tree

12.1.1.7. 23+-Tree Search Example

1 / 10 Settings
<<<>>>

Example 2-3+ Tree Visualization: Search

Created with Raphaël 2.1.2
  1. 15
    J
  2. 22
    X
  1. 52
    B
  1. 33
  1. 65
    S
  1. 71
    W
  2. 89
    M
  1. 71
  1. 46
  2. 65
  1. 33
    O
  1. 46
    H
  2. 47
    L
  1. 52
Proficient Saving... Error Saving
Server Error
Resubmit

An example of searching a “2−3+ tree

12.1.1.8. 23+-Tree Delete Example

1 / 33 Settings
<<<>>>

Example 2-3+ Tree Visualization: Delete

Created with Raphaël 2.1.2
  1. 15
    J
  1. 71
    W
  2. 89
    M
  1. 22
  1. 65
    S
  2. 70
    F
  1. 51
    B
  2. 52
    T
  1. 71
  1. 46
  2. 65
  1. 46
    H
  2. 47
    L
  1. 22
    X
  2. 33
    O
  1. 51
Proficient Saving... Error Saving
Server Error
Resubmit

An example of deleting from a “2−3+ tree

12.1.1.9. B+-Tree Find

1 / 10 Settings
<<<>>>

Example B+ Tree Visualization: Search in a tree of degree 4

Created with Raphaël 2.1.2
  1. 10
    S
  2. 18
    E
  1. 40
    Q
  2. 55
    F
  1. 25
  2. 40
  1. 77
    A
  2. 89
    B
  1. 98
    A
  2. 127
    V
  1. 25
    T
  2. 39
    F
  1. 98
  1. 77
Proficient Saving... Error Saving
Server Error
Resubmit

An example of search in a B+ tree of order four. Internal nodes must store between two and four children.

12.1.1.10. B+-Tree Insert

1 / 42 Settings
<<<>>>

Example B+ Tree Visualization: Insert into a tree of degree 4

Created with Raphaël 2.1.2
Proficient Saving... Error Saving
Server Error
Resubmit

An example of building a B+ tree of order four.

12.1.1.11. B+-Tree Deletion

1 / 23 Settings
<<<>>>

Example B+ Tree Visualization: Delete from a tree of degree 4

Created with Raphaël 2.1.2
  1. 5
    F
  2. 10
    S
  1. 44
    Q
  2. 48
    E
  1. 12
  2. 44
  1. 67
    A
  2. 88
    B
  1. 58
    A
  2. 60
    F
  1. 12
    V
  2. 27
    T
  1. 67
  1. 58
Proficient Saving... Error Saving
Server Error
Resubmit

An example of deletion in a B+ tree of order four.

12.1.1.12. B+-Tree Insert (Degree 5)

1 / 33 Settings
<<<>>>

Example B+ Tree Visualization: Insert into a tree of degree 5

Created with Raphaël 2.1.2
Proficient Saving... Error Saving
Server Error
Resubmit

An example of building a B+ tree of degree 5

12.1.1.13. B-Tree Space Analysis (1)

  • B+-Trees nodes are always at least half full.

  • The B*-Tree splits two pages for three, and combines three pages into two. In this way, nodes are always 2/3 full.

  • Asymptotic cost of search, insertion, and deletion of nodes from B-Trees is Θ(logn).

  • Base of the log is the (average) branching factor of the tree.

12.1.1.14. B-Tree Space Analysis (2)

  • Example: Consider a B+-Tree of order 100 with leaf nodes containing 100 records.

  • 1 level B+-tree:

  • 2 level B+-tree:

  • 3 level B+-tree:

  • 4 level B+-tree:

  • Ways to reduce the number of disk fetches:

    • Keep the upper levels in memory.

    • Manage B+-Tree pages with a buffer pool.

12.1.1.15. B-Trees: The Big Idea

  • B-trees are really good at managing a sorted list

    • They break the list into manageable chunks

    • The leaves of the B+-tree form the list

    • The internal nodes of the B+-tree merely help find the right chunk

   «  11.2. 2-3 Trees   ::   Contents   ::   12.2. SkipLists  »

nsf

© Copyright 2011-2023 by OpenDSA Project Contributors and distributed under an MIT license. Last updated on Nov 27, 2023. Created using Sphinx 4.4.0.
Close Window