[MySQL] B-Tree 인덱스

인덱스를 생성하는 도중 의문에 생겼다.

다중컬럼 인덱스를 생성하면 단일컬럼인덱스를 왜 또 생성해주어야할까?

다중컬럼 인덱스를 걸어두면 단일컬럼 조회 시에도 인덱스 스캔을 타야 하는 것이 아닐까?

B-Tree 인덱스 구조를 파헤쳐보면  이 문제에 대한 해답을 얻을 수 있었다.

---

 

인덱스란?

• 테이블을 처음부터 끝까지 검색하는 방법인 FTS(Full Table Scan) 과 달리 인덱스를 검색하여 해당 자료의 테이블에 접근하는 방법입니다.
  • 인덱스를 책에 마지막에 있는 인덱스 목록(찾아보기) 에 비유하자면 책의 내용은 데이터 파일이 될 것이고 데이터 파일에 저장된 레코드의 주소는 인덱스 목록에 있는 페이지 번호가 될 것입니다.

 

인덱스의 장단점

• 인덱스는 항상 정렬된 상태를 유지하기 때문에 원하는 값을 검색하는데 빠르지만, 새로운 값을 추가하거나 삭제, 수정하는 경우에는 쿼리문의 실행 속도가 느려집니다.
• 즉, 인덱스는 저장성능을 희생하고 그 대신 데이터의 검색 속도를 높이는 기능이라 할 수 있습니다.

 

 

B- Tree 인덱싱 알고리즘 알아보기

---

대부분의 인덱스는 거의 B-Tree 를 사용할 정도로 일반적이 용도에 적합한 알고리즘이다.

검색 속도가 O(1) 인 해시테이블 알고리즘은 왜 사용하지 않을까?

• 해시 테이블
  • 컬럼의 값으로 생성된 해시를 기반으로 인덱스를 구현합니다
  • 시간 복잡도가 O(1) 이라 검색이 매우 빠릅니다.
  • 부등호(<,>) 와 같이 연속적인 데이터를 위한 순차 검색이 불가능하기 때문에 사용에 적합하기 않습니다.

 

 

B-Tree 의 구조 및 특성

 

B-Tree 는 트리 구조의 최상위에 "루트 노드" 가 존재하고 그 하위에 자식  노드가 붙어있는 형태다.

• 트리 구조의 가장 하위에 있는 노드를 "리프 노드" 라 하고, 트리 구조에서 투르, 리프도 아닌 중간노드를 "브랜치 노드"라 한다.
• 데이터 베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리가 되는데, 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주소값을 가지고 있다.

인덱스의 키 값은 모두 정렬돼 있지만, 데이터 파일의 레코드는 정렬돼 있지 않고 임의의 순서로 저장돼 있다.

 

B-Tree 인덱스를 통한 데이터 읽기

 

 

다중 컬럼 인덱스 

• 두 개 이상의 컬럼으로 구성된 인덱스를 다중 컬럼 인덱스(Concatendated Index)한다.
• 다중 컬럼에서는 다음 컬럼이 이전컬럼에 의존해서 정렬된다고 한다.
• 다중 컬럼 인덱스에서는 인덱스 내에서 각 컬럼의 위치(순서)가 상당히 중요하다.

emp_no 값이 빠르더라도 dept_no 컬럼의 정렬 순서가 늦다면 인덱스는 뒤쪽에 위치하게 된다.

두 번째 컬럼 만으로 질의하는 경우는 인덱스를 타지 못하게 된다. 즉 두 번째 컬럼의 정렬은 첫 번째 컬럼이 동일한 레코드에서만 의미가 있는것이다. 그래서 다중 컬럼 인덱스에서는 인덱스 내에서 각 컬럼의 위치(순서)가 상당히 중요하다.

 

 

 

 

 

참고자료 : 

https://dev-coco.tistory.com/158

Real MySQL 8.0