[B-Tree Index] B트리 인덱스

B = Balanced

• 데이터베이스에서 가장 일반적으로 사용되는 인덱스 구조
  • 최상단에 `루트 노드` 그 하위에 자식 노드들이 존재
    • 중간에 존재하는 노드를 `브랜치 노드`, 마지막에 존재하는 노드를 `리프 노드`라고함.
    • 인덱스의 `리프노드`는 실제 데이터 레코드를 찾아가기 위한 주소 값을 가지고있음.

• `INSERT`, `UPDATE`, `DELETE` 작업시 빠른 검색을 위해서 인덱스 관리에 따르는 추가 비용을 감당하면서 인덱스를 구축함.
  • 인덱스를 검색하는 작업(트리탐색)
    • B-Tree의 `루트 노드`부터 시작해 `브랜치 노드`를 거쳐 `최종 리프 노드`까지 이동하면서 비교하며 작업을 수행함
    • 이러한 트리 탐색은 `UPDATE`, `INSERT`를 하기 위해 검색할 때도 사용됨.
    • B-Tree 인덱스를 이용한 검색은 100% 일치 또는 값의 앞부분만 일치하는 경우에 사용할 수 있음
      • 검색시 `Like %{keyword}%`로 쿼리를 구현하면 인덱스를 타지 않음.

---

• B-Tree 인덱스는 인덱스를 구성하는 `컬럼의 크기`, `레코드의 건수`, `유니크한 인덱스 키 값의 개수` 등에 의해 검색이나 변경 작업의 성능이 영향을 받음.
• B-Tree는 자식 노드의 개수 : 인덱스 페이지 크기와 키 값의 크기에 따라 결정됨.
• B-Tree의 깊이 : Depth와 인덱스 키 값의 크기는 연관이 있음.
  • 만약 depth=3에 키 값의 크기가 16KB 라면, 대략 2억개 정도 담을 수 있다고 함.
    • 그런데 키 값의 크기가 32KB 라면 5천만개로 줄어듬.
    • 즉, B-Tree 깊이는 MySQL에서 값을 검색할 때 몇 번이나 랜덤하게 디스크를 읽어야 하는지와 직결되는 문제
  • 인덱스 키 값의 크기가 커지면 커질수록 하나의 인덱스 페이지가 담을 수 있는 인덱스 키 값의 개수가 작아지기 때문에 같은 레코드 건수라 하더라도 B-Tree(Depth)가 깊어져서 디크스 읽기가 더 많이 필요하게 됨.
    • 즉, 인덱스 키 값의 크기는 가능하면 작게 만드는 것이 좋음

---

1. 선택도(cardinality) : 모든 인덱스 키 값 가운데 유니크한 값의 수를 의미
   • 주민번호 같은 경우는 모든 사람이 갖는 고유의 값이기 때문에 Cardinality가 높음.
   • 반면에 `성별`에 대한 정보는 2가지 뿐이기 때문에 Cardinality가 상대적으로 낮음.
2. 데이터 읽기 : MySQL이 인덱스를 이용하는 대표적인 방법 3가지
   1. 인덱스 레인지 스캔 : 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식
      • 원하는 결과를 찾으면 결과를 사용자에게 반환하고 쿼리를 끝냄.
      • 루트와 브랜치 노드를 이용해 특정 검색 시작 값을 가지고 있는 리프 노드를 검색하고, 그 지점부터 필요한 방향(오름차순 or 내림차순)으로 인덱스를 읽어 나가는 과정.
      • 가장 중요한 것은 어떤 방식으로 스캔하든 관계없이, 해당 인덱스를 구성하는 컬럼의 정순 또는 역순으로 정렬된 상태로 레코드를 가져온다는 것.
      • 인덱스의 리프 노드에서 검색 조건에 일치하는 건들은 데이터 파일에서 레코드를 읽어오는 과정이 필요함.
        • 이때 레코드 한건한건 랜덤 I/O가 실행됨.
        • 그래서 인덱스를 통해 데이터 레코드를 읽는 작업은 비용이 많이 드는 작업으로 분류되는 것
   2. 인덱스 풀 스캔
      • 인덱스를 사용하지만 인덱스 레인지 스캔과는 달리 인덱스의 처음부터 끝까지 모두 읽는 방식
        • 대표적으로 쿼리의 조건절에 사용된 컬럼이 인덱스의 첫 번째 컬럼이 아닌 경우 인덱스 풀 스캔 방식이 사용됨.
        • 예를들어, 인덱스는 A, B, C 컬럼 순으로 만들어져 있지만 쿼리의 조건절은 B 컬럼이나 C 컬럼으로 검색하는 경우
      • 쿼리가 인덱스에 명시된 컬럼만으로 조건을 처리할 수 있는 경우 주로 이 방식이 사용됨.
        • 인덱스뿐만이 아니라 데이터 레코드까지 읽어야 한다면 절대 이 방식으로 처리되지 않음.
      • 인덱스의 자체 크기는 테이블 자체의 크기보다는 훨씬 작으므로 인덱스 풀 스캔은 테이블 전체를 읽는 것보다는 적은 디스크 I/O로 쿼리를 처리할 수 있음.
   3. 루스 인덱스 스캔
      • 인덱스 레인지 스캔과 유사하나, 중간마다 중요하지 않은 인덱스 키 값은 무시하고 다음으로 넘어가는 형태로 처리함.
        • 데이터베이스에 옵티마이저는 WHERE 조건문을 통해 필요한 데이터와 불필요한 데이터를 구분할 수 있기 때문에 조건에 만족하지 않은 인덱스는 무시하고 넘어감.
        • 루스 인덱스 스캔은 Group by 또는  max, min 과 같은 집합함수에서 많이 사용됨.
      • 아래의 쿼리에서 인덱스가 "dept_no + emp_no"라고 할때, MIN(emp_no)을 구하는 경우 인덱스는 정렬되어있기 때문에 가장 작은 값 하나만 읽고 뒷부분은 모두 스킵하는 방식으로 동작할 것 임.

mysql > SELECT dept_no, MIN(emp_no)
                FROM dept_emp
                WHERE dep_no BETWEEN 'd002' AND 'd004'
                GROUP BY dept_no;

 

---

 

출처 

https://devlog-wjdrbs96.tistory.com/342

[MySQL] B-Tree 인덱스란?

http://wiki.gurubee.net/pages/viewpage.action?pageId=12517389

2.1. B-tree 인덱스 - [종료]대용량 데이터베이스 스터디 - 개발자, DBA가 함께 만들어가는 구루비 지

 https://lkhlkh23.tistory.com/112

[데이터베이스] 인덱스 스캔 방식