(6) 인덱스 / B-Tree

TL;DR

인덱스란? 테이블에 대한 동작의 속도를 높여주는 자료 구조
B-Tree란? 이진 트리를 확장시켜 2개 이상의 자식을 가질 수 있게 일반화 한 자료구조
B+Tree란? B-Tree의 확장 개념으로 오직 리프 노드에만 key와 data를 저장한다.
Join

 

 

인덱스 Index

• 인덱스는 추가적인 저장 공간을 사용해 DB의 검색 속도 향상을 위한 자료구조
• 인덱스는 MYI(MySQL Index)파일에 저장되며,
• 인덱스가 설정되지 않았다면 Table Full Scan이 일어나 대용량 데이터엔 비효율적
• DBMS는 INDEX를 다양한 알고리즘으로 관리하고 있는데, 일반적으로 사용하는 알고리즘은 B+Tree 알고리즘

 

✅ 인덱스는 어떻게 동작하는가?

1. Index Table에서 where에 포함된 값을 찾음
2. 해당 컬럼의 인덱스 테이블에 저장된 key-value 값을 참조
3. 가져온 인덱스 테이블에 저장된 key-value 값으로 원본 테이블에서 값을 조회해옴

 

 

• SCOUNTER TABLE 생성 시 AIRPORT 컬럼에 대한 인덱스를 주면 AIRPORT 컬럼에 대한 인덱스 테이블이 생성된다.
• 그리고 나중에 SCOUNTER 테이블에 AIRPORT 컬럼에 대한 WHERE문이 포함된 쿼리가 나갈 때,
• AIRPORT 인덱스 테이블에 저장된 key-value 값을 참조해서 SCOUNTER TABLE 테이블에서 결과 값을 반환해온다.

 

 

✅ 인덱스 단점

• 약 10% 정도의 추가 저장 공간이 필요하다. (인덱스 테이블)
• 인덱스는 항상 정렬된 상태를 유지하기 때문에 탐색은 빠르지만 값을 추가(Insert), 삭제(Delete), 수정(Update)하는 경우에는 불리하다.
• => 추가, 삭제, 수정을 빈번하게 하는 경우에는 성능 저하가 올 수 있다.

 

✅ 인덱스 설계 시 고려할 점

• 무조건 많이 설정하지 않는다. (한 테이블당 3~5개가 적당 목적에 따라 상이)
• 인덱스 컬럼 선택 시 Cardinality 가 높은 컬럼 사용 (중복도가 가장 낮은 컬럼)

 

 

✅ 인덱스 종류

🔺 키에 따른 인덱스 분류

• 기본 인덱스(Primary Index): 기본키를 포함하는 인덱스(키의 순서가 레코드의 순서를 결정)
• 보조 인덱스(Secondary Index): 기본 인덱스 이외의 인덱스

 

🔺 파일 조직에 따른 인덱스 분류

• Clustered Index
  • 데이터 레코드의 물리적 순서가 그 파일에 대한 인덱스 엔트리 순서와 동일하게 유지되도록 구성된 인덱스
  • Mysql의 경우 PK 설정시, 기본적으로 PK를 기준으로 Clustered Index 생성
  • 테이블당 한 개를 만들 수 있다.
• Unclustered Index
  • 파일 인덱스 엔트리 순서가 데이터 레코드의 물리적 순서와 일치하지 않음.
  • 파일 인덱스 엔트리의 리프 노드에는 해당 레코드의 주소값이(실제 값X) 들어가 있음
  • 물리적으로 데이터를 정렬하지 않는 대신 위치정보를 인덱스로 구성

 

🔺 결합 인덱스(다중 컬럼 인덱스)

• 다중 컬럼 인덱스는 두 개 이상의 필드를 조합해서 생성한 INDEX
• 주 용도는 SQL에서 WHERE절의 조건 컬럼이 2개 이상 AND로 연결되어 함께 사용되는 경우에 많이 사용
• 다중 컬럼 인덱스는 단일 컬럼 인덱스 보다 더 비효율적으로 INDEX/UPDATE/DELETE를 수행하기 때문에 신중해야한다.

 

• 다중 컬럼 인덱스 사용할 때는 INDEX로 설정해준 제일 왼쪽 컬럼이 WHERE 절에 사용되어야 한다. (B+Tree 자료구조 탐색 기준)
• 순서대로 적용되기 때문에 중간 인덱스가 빠지면 인덱스 적용이 안된다.
• (name, address, age) 에서 name 과 age 만 WHERE 절에 있다면 age는 인덱스 적용이 안됨
• 따라서 결합 인덱스는 Cardinality 가 높은 순서대로 내림차순으로 적용하는게 성능상 제일 좋다.

 

✅ 인덱스 조회시 주의 사항

🔺 범위 조건(LIKE, BETWEEN, <, >)과 INDEX

between, like, <, > 등 범위 조건은 해당 컬럼은 인덱스를 타지만, 그 뒤 인덱스 컬럼들은 인덱스가 사용되지 않는다.

• group_no, from_date, is_bonus으로 인덱스가 잡혀있다고 가정할 때, 조회 쿼리를 아래로 잡으면 is_bonus는 인덱스가 사용되지 않는다. (중간에 from_date에서 범위 탐색을 함으로써 인덱스가 먹히지 않음)
• where group_no=XX and is_bonus=YY and from_date > ZZ

 

🔺 =, in과 INDEX

• =, in 은 다음 컬럼도 인덱스를 사용한다.
• 단, in은 인자값으로 상수가 포함되면 문제 없지만, 서브쿼리를 넣게되면 성능상 이슈가 발생

 

🔺 컬럼값 가공금지

• 인덱스는 가공된 데이터를 저장하고 있지 않는다. 인덱스로 사용된 컬럼값 그대로 사용해야만 인덱스가 사용된다.
  • where salary * 10 > 150000;는 인덱스를 사용하지 않는다.
  • 하지만, where salary > 150000 / 10;는 인덱스를 사용한다.
  • ABS(컬럼) 이런 것도 인덱스가 사용되지 않는다.

 

🔺 null 값의 경우

• null 값의 경우 is null 조건으로 인덱스 레인지 스캔 가능

 

🔺 OR 조건

• AND 연산자는 각 조건들이 읽어와야할 ROW 수를 줄이는 역할을 한다.
• 하지만 OR 연산자는 비교해야할 ROW가 더 늘어나기 때문에 풀 테이블 스캔이 발생할 확률이 높다.

 

🔺 ORDER BY 와 GROUP BY에 대한 INDEX

INDEX는 ORDER BY와 GROUP BY에도 영향을 끼치는데 다음과 같은 경우에는 INDEX를 타지 않는다.

• 연속하지 않은 컬럼에 대해 ORDER BY를 실행한 경우
  • ORDER BY도 똑같이 B*Tree 자료구조 탐색 조건에 위배되지 않아야 인덱스가 걸림
• DESC와 ASC를 혼합해서 사용한 경우
  • 정렬되는 각 컬럼의 오름차순 및 내림차순 옵션이 인덱스와 같거나 정반대인 경우에만 사용가능
• GROUP BY와 ORDER BY의 컬럼이 다른 경우
• ORDER BY 절에 다른 표현을 사용한 경우

 

---

B-Tree & B+Tree

• B-트리는 탐색을 위해서 노드를 찾아서 이동해야 한다는 단점을 가지고 있다.
• 이러한 단점을 해소하고자 B+트리는 같은 레벨의 모든 키값들이 정렬되어 있고, 같은 레벨의 Leaf node는 연결리스트 형태로 이어져 있다.
• DB에서 제일 중요한 건 검색속도이기 때문에 대부분의 DB 시스템은 B+Tree 구조를 채택하고 있다.(ex. Mysql InnoDB)

구분	B-트리	B+트리
데이터 저장	리프 노드, 브랜치 노드 모두 데이터 저장 가능	오직 리프 노드에만 데이터 저장 가능
트리의 높이	높음	낮음(한 노드 당 key를 많이 담을 수 있음)
풀 스캔 시, 검색 속도	모든 노드 탐색	리프 노드에서 선형 탐색
키 중복	없음	있음(리프 노드에 모든 데이터가 있기 때문)
검색	자주 access 되는 노드를 루트 노드 가까이 배치할 수 있고, 루트 노드에서 가까울 경우, 브랜치 노드에도 데이터가 존재하기 때문에 빠름	리프 노드까지 가야 데이터 존재
링크드 리스트	없음	리프 노드끼리 링크드 리스트로 연결

공통점	차이점
1. 모든 leaf의 depth가 같다	1. B-트리의 각 노드에서는 key 뿐만 아니라 data도 들어갈 수 있다. 여기서 data는 disk block으로의 포인터가 될 수 있다. B+트리는 각 node에서는 key만 들어가야 한다. 그러므로 B+트리에서는 data는 오직 leaf에만 존재한다.
2. 각 node에는 k/2 ~ k 개의 item이 들어있어야 한다.	2. B+트리는 B-트리와는 달리 add, delete가 leaf에서만 이루어진다.
3. 둘 다 기본적으로 트리 탐색(search)	3. B+트리는 leaf node 끼리 linked list로 연결되어 있다.
4. add시 overflow가 발생하면 split 한다
5. delete 시 underflow가 발생하면 redistribution하거나 merge 한다.

 

 

B-Tree

• B-트리는 트리 자료구조의 일종으로 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조.
  • = 이진 트리를 확장시켜 2개 이상의 자식을 가질 수 있게 일반화한 자료구조
• 이진 트리와는 다르게 하나의 노드에 많은 정보를 가질 수 있다.
• 이렇게 하나의 노드에 여러 정보를 담게 되면서 차수라는 개념이 등장
  • 허용하는 자식 노드가 최대 M개라면 M차 B-Tree라고 부른다.

• 따라서 아무리 최악의 경우라도 O(logN)의 검색 성능을 보여준다.

 

✅ B-트리 모양의 특징

1. 노드에는 2개 이상의 데이터(key)가 들어갈 수 있으며, 항상 정렬된 상태로 저장된다.
2. 모든 노드는 최대 M개의 자식을 가진다.
3. 모든 노드는 키와 자식 노드에 대한 포인터로 이루어져있다.
4. 특정 노드의 데이터(key)가 K개라면, 자식 노드의 개수는 K+1개여야 한다.
5. 특정 노드의 왼쪽 서브 트리는 특정 노드의 key 보다 작은 값들로, 오른쪽 서브 트리는 큰 값들로 구성된다.
6. 노드 내에 데이터는 floor(M/2)-1개부터 최대 M-1개까지 포함될 수 있다
7. 모든 리프 노드들이 같은 레벨에 존재한다.
   즉, 루트 노드에서 모든 리프 노드로 가는 경로의 길이가 같다.

 

✅ B-트리 탐색 과정

B-트리는 루트 노드에서 탐색을 시작하여 하향식으로 탐색을 진행한다. 찾고자 하는 값이 K라면 다음과 같은 과정을 거친다.

1. 루트 노드에서 탐색을 시작한다.
2. K를 찾았다면 탐색을 종료한다.
3. K와 노드의 key값을 비교해 알맞은 자식 노드로 내려간다.
4. 해당 과정을 리프 노드에 도달할 때까지 반복한다.
5. 리프 노드에서도 K를 찾지 못한다면 트리에 값이 존재하지 않는 것

 

✅ B-트리 삽입 과정

B-트리에 데이터를 삽입하는 과정은 탐색과는 다르게 상향식으로 진행된다. B-트리에서의 데이터 삽입은 항상 리프 노드에서 시작된다.

1. 해당원소가 들어 가야 할 리프노드를 찾는다.
2. 노드에 빈 자리가 있다면 새로운 원소를 삽입한다.
3. 노드에 빈 자리가 없다면 노드를 2 개로 분할한다.
4. 기존 노드의 원소와 새로운 원소 중에 중간 값을 분할된 부모 노드의 값으로 한다.
5. 중간 값보다 작은 값은 왼쪽 노드로 큰 값은 오른쪽 노드에 넣는다
6. 중간 값을 부모 노드로 넣을 때, 부모 노드에 자리가 없으면 부모 노드도 위의 규칙에 의해 분할한다

 

✅ B-트리 삭제 과정

삭제 과정중에서도 아래와 같은 조건을 만족해야 하며, 조건이 위반되면 트리를 재구조화 한다.

1. 내부 노드(루트가 아닌 노드)는 M/2 ~ M개의 자식 노드를 가질 수 있다.
2. 각 노드는 floor(M/2)-1 ~ M-1 개의 데이터(key)를 가질 수 있다.
3. 노드의 key가 K개 라면 자식 노드의 개수는 K+1개여야 한다.

 

 

B+Tree

• B-tree 확장 개념으로, 브랜치 노드에 key만 담아두고, 오직 리프 노드에만 key와 data를 저장.
  • B-트리의 특징을 가지고 있지만, 모든 키 값들이 리프 노드에 정렬되어있는 트리 구조
  • 리프 노드를 순차적으로 연결하는 포인터 집합을 가지고 있는 자료 구조(선형 검색 가능)
    -> 리프노드끼리 Linked list로 연결되어 있다.
• B-tree는 탐색을 위해 노드를 찾아서 이동해야 한다는 단점을 가지고 있는데, 이 단점을 해소하고자 같은 레벨의 모든 키값들이 정렬되어 있고, 같은 레벨의 sibiling node는 연결리스트 형태로 이어져 있다.
• Index node들과 Data node(레코드)로 구성이 되어있다.
  • Index node: leaf node를 제외한 나머지 node. 인덱스 노드의 value에는 다음 노드를 가리킬 수 있는 포인터 주소가 존재
  • Data node: leaf node. 오직 리프노드에만 key와 data를 저장하고, 리프 노드끼리 연결 리스트로 연결. 데이터 노드의 value에는 데이터가 존재

 

✅ B+트리 장점

1. 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key를 수용할 수 있다.
   • 하나의 노드에 더 많은 key를 담을 수 있기 때문에 트리의 높이는 더 낮아진다.
   • B+트리의 높이는 B-트리 보다 낮게 구성되므로 검색시간과 디스크에 접근하는 횟수가 줄어든다
2. 풀 스캔 시, B+트리는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형탐색만 하면 되기 때문에 B-트리에 비해 빠르다.
   • B-트리의 경우에는 모든 노드를 확인해야 한다.

 

✅ B+트리 단점

B-트리의 경우 best case에는 루트에서 끝날수 있지만, B+트리의 경우 무조건 leaf노드까지 가야한다.