6. Database Indexes_[B-Tree]📌

• balanced m-way tree
• Generalization of BST in which a node can have more than one key & more than 2 children
  • child의 개수가 2보다 많을 수 O
• Maintains sorted data 
  • 특정 노드의 key 들이 정렬되어 있음
    • ex.
      • 6 | 8 | 9 (O)
      • 8 | 6 | 9 ( X)
• All leaf node must be at same level
  • BST 와의 차이점
    • BST : 위에서 부터 내려오는 방식
    • 밑에서 부터 쌓아 올리는 방식
  • 리프 노드의 레벨은 항상 똑같다
    • 리프 노드 ? 
      • 자식 노드가 없는 노드
• B-Tree of order m has following properties :
  • every node can have m children
  • min children : -> (children 의 개수 의미)
    • leaf -> 0 
    • (non-leaf) root -> 2
    • internal nodes -> (m / 2) 올림
  • every node has max (m -1) keys
  • min keys : -> (keys 의 개수 의미)
    • root node -> 1
    • all other nodes -> (m / 2) 올림 - 1