6. Database Indexes_[Binary Search Tree]

• Tree
  • a root as a parent could have children
  • a root has no parent
  • each child as a root node of a sub-tree could have children
  • each child has only one parent
• M-way tree
  • a tree that the maximum number of children is M
• Binary Search Tree (BST)
  • 2-way tree :
    • a node could have left child node and right child node
  • B-Tree :
    • generalization of BST in which a node can have more than one key & more than 2 children
  • Each node is an entry <key, a pointer to record>
  • For each node n <k, p>
    • all the keys in left sub-tree is less than k
      • 왼쪽은 key 보다 작음
    • all the keys in right sub-tree is larger than k
      • 오른쪽은 key 보다 큼
  • Search
  • Insert
  • Delete
  • Space
  • Tree 의 성능 향상시키기 위해서는 Tree의 높이를 압축시켜야 함
    • 한 번 찾을 때 마다 반 씩 없어지는
    • 꽉 차이는 Tree 가 좋다
    •  In a good case : full binary tree or complete binary tree
  • 최소 높이 증명
    
    • The maximum number of nodes for a height h
    • (when a height is the maximum number of edges from a leaf node to the root node)
      • 높이가 h 일때 노드의 최대 개수는 얼마인가
      • 리프 노드 -> 루트 노드 : 높이
  •  

[자료구조] 트리 (출처 : 이미지 클릭)

트리는 항상 루트(root)에서부터 시작합니다. 루트는 자식 노드(child)를 가지며, 간선(edge)으로 연결되어 있습니다.

• 차수(degree) : 자식 노드의 개수
• 크기(size) : 자신을 포함한 모든 자식 노드의 개수
• 리프(leaf) : 자식 노드가 없는 노드
• 높이(height) : 현재 위치에서 리프까지의 거리
• 깊이(depth) : 루트에서부터 현재 노드까지의 거리
• 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합