B-Tree (Balanced Tree) 예제

1.1.1 What is a tree?

    The computer tree data structure is a parent, child non-cyclic graph
    where each child has exactly one parent (except the root which has
    no parent) and each parent can have one or more children.  Each
    element of the tree is called a node whether it is a root, child,
    and/or parent.

 

트리란?
컴퓨터 트리 데이터 구조는 parent와 하나의 parent만을 갖는 child(parent를 갖지 않는 root는 제외)간의 비 순환구조이며 각각의 parent는 하나 이상의 child를 가질 수 있다. 트리의 각 요소들은 root, child 혹은 parent node라 부른다.

1.1.1.1 What is a balanced tree?

    A balanced tree is where the leaf nodes (children which are not parents)
    are all on the same level (same distance from the root).

밸런스드 트리란?

밸런스드 트리는 동일한 레벨의 leaf 노드들을 갖는 트리이다.

1.1.1.2 What are the advantages of a balanced tree?

    A balanced tree guarantees O(log(n)) performance, where n is the number
    of nodes (root, children, parents) in the tree, meaning that the time
    to find a node (note: tree is self-sorted or otherwise indexed) is
    logrithmically related to the number of nodes in the tree.  In English,
    the more nodes you add does NOT increase search time proportionally,
    which would slow, but search time increases at a much, much slower rate.
    A full balanced tree of height 31 where all non-leaf nodes have exactly
    two children (this is a full binary tree) contains over 4 billion nodes,
    but at most only 31 comparisons are required to find a specific node.

    An efficient balanced tree is implemented with search, insert, and delete
    operations all at O(log(n)) performance.

Examples

Sample B-Tree

 

 Searching a B-Tree for Key 21  

 Inserting Key 33 into a B-Tree (w/ Split) 

  출처 : http://alumni.cse.ucsc.edu/%7Edavevw/BTReadme.txt그림은 까먹었음 --;;