인덱스

• 데이터의 더 빠른 검색을 위해 특정 컬럼에 대해 정렬 후 색인을 만들어 데이터의 저장위치를 빠르게 찾을 수 있도록 하는 것

B 트리

• B-Tree

  

  • M-way tree의 차수가 많아지면 트리의 높이도 n이 됨 → n이 커질수록 비효율적
  • 따라서, B-tree를 만들어 규칙이 있는 m-way search tree를 구상
  • 좌우균형을 유지하는 트리로, 이진트리의 단점 극복 가능 (이진트리 단점 - 자료가 많아질수록 트리의 높이가 커져 최악의 경우 O(log N)의 시간복잡도 소요)
  • 규칙
  • 특징

• B+Tree

  

  • DB index에 자주 사용되는 자료구조
  • B-Tree 계열의 Balanced Tree 종류 중 하나
  • MySQL InnoDB 엔진은 주로 B+Tree를 사용
  • 특징

B - Tree vs B + Tree

결론

• B-Tree 를 DB에 사용하는 이유
  • 한 개의 노드에 여러 개의 key를 저장할수 있음
    • 여러 개의 key를 저장하고 균형적인 트리구조를 유지
    • 트리의 깊이를 줄여 노드에 접근 횟수를 줄임 → 디스크 접근 횟수를 줄임
  • B+Tree와 다르게 리프 노드까지 가지 않고 브랜치 노드에서 데이터를 찾을 수 있음
• B+Tree 를 인덱스에 사용하는 이유
  • 균형적인 다진 트리로 필요한 key를 탐색하기에 좋음
  • Leaf Node에 Linked list로 모든 데이터가 연결되어 있기에 여러 개의 순차적인 데이터를 탐색하는데 적합하고, 부등호 연산이 많이 요구되는 인덱스의 자료구조로 사용

• B*Tree (참고)
  • 참고사항