B-Tree 인덱스
-
DB 인덱싱 알고리즘 중 가장 일반적으로 사용, 가장 먼저 도입된 알고리즘
-
보통 DBMS는 B-Tree를 변형한 B+-Tree와 B*-Tree를 사용
-
컬럼의 원래 값을 변형시키지 않은 채로 정렬 유지
B-Tree 구조
-
트리 구조 (1개의 루트 노드, 하위에 자식 노드)
-
리프 노드(가장 하위 노드)는 실제 데이터 레코드의 주솟값을 가짐
-
데이터 파일의 레코드는 정렬되어 있지 않음
인덱스 연산
- INSERT, DELETE, UPDATE, SELECT
인덱스 키 추가
-
저장될 키 값으로 B-Tree의 적절한 위치를 검색
-
레코드의 키 값과 레코드의 주소 정보를 B-Tree 리프 노드에 저장
-
리프 노드가 가득 찼다면 리프 노드가 분리되어야 하고, 상위 브랜치 노드까지 수정해야 하므로
-
B-Tree 인덱스 키 추가는 비용이 많이 든다
인덱스 키 삭제
-
해당 키 값이 저장된 리프 노드를 찾아 삭제 마크를 함
-
삭제 마킹된 인덱스 키 공간은 방치 or 재활용
-
마킹 작업도 디스크 쓰기가 필요하므로 디스크 I/O 필요
인덱스 키 변경
-
키 값에 따라 저장될 리프 노드 위치가 결정됨
-
해당 키 값 삭제 > 새로운 키 값 추가
인덱스 키 검색
- 트리 탐색
- 루트 노드, 브랜치 노드, 리프 노드까지 이동하며 비교 작업 수행
-
검색 속도 향상 > INSERT, UPDATE, DELETE 작업의 추가 비용이 있음에도 인덱스를 구축함
-
UPDATE, DELETE에서도 레코드를 검색하는 과정을 거침
-
B-Tree는 키 값의 뒷부분만 검색하는 용도로 인덱스를 사용할 수 없다??
B-Tree 인덱스 성능에 영향을 미치는 요소
-
인덱스를 구성하는 컬럼의 크기
-
레코드 건수
-
유니크한 인덱스 키 값
인덱스 키 값의 크기
- 인덱스는 페이지 단위로 관리
- 페이지 = 디스크에 데이터를 저장하는 최소 작업 단위
- 일반적으로 자식 노드 개수가 가변적이다
- 페이지와 키 값의 크기에 따라 달라짐
- B-Tree의 B는 Binary가 아니라 Balanced (자식 노드 개수가 2개가 아님)
- 키 값이 커질수록
- 디스크에서 read 횟수가 늘어남 > 느려짐
- 인덱스 크기도 커짐 > 제한된 버퍼에 캐시해 두는 레코드 수 감소-> 메모리 효율 감소
- 키 값의 크기는 작을수록 좋음
B-Tree 깊이
-
디스크 읽는 횟수에 영향
-
키 값 크기 증가 > 페이지에 담는 인덱스 키 개수 감소 > 깊이 증가 > 디스크 읽기 횟수 증가
-
키 값의 크기는 작을수록 (깊이가 낮을수록) 좋음
카디널리티
-
인덱스 키 값 중 유니크한 값의 수
-
중복된 값이 많아질수록 카디널리티 감소 > 느려짐
읽어야 할 레코드 건수
- 일반적인 DBMS는 인덱스를 통해 레코드 1건 읽는 비용 = 테이블에서 직접 레코드 1건을 읽는 비용 * (4~5)로 예측
- 손익 분기점을 판단해야 함
- 전체 레코드의 20~25%
- 읽어야 할 레코드 수가 전체 레코드의 20~25% 이상이라면 직접 테이블을 처음부터 끝까지 읽을 것임
B-Tree 인덱스로 데이터 스캔
-
MySQL이 어떻게 인덱스를 이용해서 레코드를 읽는지 알아야 인덱스 사용 유무 결정
-
MySQL이 인덱스를 이용하는 세 가지 방법은 다음과 같다
- 인덱스 레인지 스캔
- 인덱스 풀 스캔
- 루스 인덱스 스캔
- 인덱스 스킵 스캔
1. 인덱스 레인지 스캔
- 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식
- 검색하려는 값의 개수나 결과의 개수와 관계x
- 인덱스의 정렬 특성 때문에 오름차순 혹은 내림차순으로 레코드를 가져옴
- 인덱스 탐색
- 루트 노드부터 비교 > 브랜치 노드 > 리프 노드를 거쳐야만 레코드의 시작점을 찾음
- 인덱스 스캔
- 탐색한 시작 위치부터 리프 노드의 인덱스를 순서대로 읽음
- 리프 노드의 끝까지 읽으면 리프 노드 간의 링크를 이용해 다음 리프 노드를 찾아 스캔
- 읽어들인 인덱스 키와 레코드 주소로 페이지를 가져온 후 최종 레코드를 읽어옴
- 데이터 파일의 레코드를 읽어 올 때 1개의 레코드마다 1번의 랜덤 I/O
- 인덱스로 읽는 작업은 비용은 큼 > 전체 레코드의 20~25%를 넘으면 직접 읽는 것이 효율적
- 스캔이 끝나면 읽은 레코드를 사용자에게 반환하고 쿼리를 끝냄
- (커버링 인덱스) 디스크의 레코드를 읽을 필요x > 랜덤 읽기 ↓ > 성능 향상
2. 인덱스 풀 스캔
-
인덱스 레인지 스캔과 달리 인덱스의 처음부터 끝까지 읽는 방식
-
쿼리의 조건절에 사용된 컬럼이 인덱스의 첫 번째 컬럼이 아닌 경우
-
인덱스에 명시된 컬럼만으로 조건을 처리할 수 있는 경우 사용
-
인덱스 리프 노드의 맨앞 또는 맨뒤로 이동하고, 리프 노드를 연결하는 링크드 리스트를 따라 처음부터 끝까지 스캔
- 테이블 풀 스캔보다는 효율적 (적은 I/O)
3. 루스 인덱스 스캔
-
듬성듬성하게 인덱스를 읽는 방식
-
인덱스 레인지 스캔과 비슷하지만, 필요하지 않은 인덱스 키 값은 스킵하고 넘어감
-
GROUP BY 또는 MAX(), MIN()을 최적화 하는 경우
4. 인덱스 스킵 스캔
다중 컬럼 인덱스 Multi-column Index
-
두 개 이상의 컬럼으로 구성된 인덱스
-
두 개의 컬럼으로 구성된 경우
- 첫 번째 컬럼을 우선으로 정렬 후 두 번째 컬럼으로 정렬
-
인덱스 내 컬럼의 순서가 중요하다
0개의 댓글
