close
프로필 배경
프로필 로고

Dev Factory

Computer Science/Database · 2023. 4. 11. fullscreen 넓게보기

[DB] Index? B-Tree?

Index

일반적으로 서점이나 yes24와 같은곳에서 책을 구매하게 되면 책에는 목차와 색인이 존재한다

색인이 존재하는 이유는 특정 키워드가 포함된 내용을 빨리 찾기 위해서이고 색인을 활용하면 책의 모든 페이지를 스캔할 필요가 없다

 

Database의 Index도 마찬가지이다

Index란 Database의 데이터 & 데이터의 위치를 추가적인 저장 공간을 활용해서 보관하고 있다
Index를 활용하게 되면 조건에 맞는 데이터들을 굉장히 빠른 시간내에 조회할 수 있다

 

간단한 예시를 통해서 Index에 대한 개념을 알아보자

  • 모든 설명은 MySQL 기준

위의 같은 Member 테이블이 존재하고 데이터가 약 100만개정도 존재한다고 가정하자

SELECT *
FROM member
WHERE first_name = 'JiWon';

이러한 쿼리를 테이블에 보낼때 만약 first_name에 index가 걸려있지 않다면 어떤 일이 발생할까?

  • "JiWon"이라는 first_name을 곧바로 찾아갈 능력이 되지 않기 때문에 테이블의 처음부터 끝까지 하나하나 확인해봐야 한다
  • 운이 좋으면 O(1) / 운이 나쁘면 O(N)
    • 한마디로 운이 좋으면 첫번째 row에서 바로 찾을 수 있다는 것이고 운이 안좋으면 100만번째 row까지 가야 찾을 수 있다는 것이다

 

결국 first_name에 index가 걸려있지 않다면 Full Table Scan에 의해서 테이블 전체를 스캔하게 되고 그 시점의 시간복잡도는 O(N)이 된다

데이터가 몇억, 몇십억건이 존재하게 된다면 그 수만큼 테이블을 스캔해야 하기 때문에 성능이 굉장히 안좋아질 것이다

 

만약 first_name에 다음과 같이 index가 걸려있게 된다면 어떤 일이 발생할까?

이처럼 first_name = "JiWon"이 존재하는 튜플의 위치를 Index를 통해서 알 수 있기 때문에 그 위치를 활용해서 더욱 빠르게 접근이 가능하다

  • 시간복잡도 O(log N) → B-Tree Based Index
이렇게 Index의 유무에 따라 조회 속도에 엄청난 영향을 줄 수 있는 것이다
MySQL의 경우 모든 세컨더리 인덱스는 pointer 참조로 PK 클러스터링 인덱스를 가리키고 있다.
MySQL 아키텍처 관련 아티클은 이후 작성 예정

 

하지만 다음과 같은 특수 상황에서는 Index가 걸려있다고 하더라도 DB Optimizer가 판단해서 Index를 타지 않을 수 있다

  1. 인덱스 컬럼이 변형되었을 경우
    • Index(name) -> LENGTH(name) / UPPER(name) / ...
  2. Optimizer가 쿼리 실행계획을 세우고 판단했을 때 Index Scan보다 Full Table Scan이 성능상 이득이라고 판단될 때 (대략 20 ~ 25% 이상의 데이터를 최종적으로 읽게 될 경우)
  3. ...

 

Index 생성

Index가 무엇인지 대략적으로 감이 왔다면 이제 Index를 생성하는 방법에 대해서 간단하게 알아보자

Player Table이 위와 같이 구성이 되었다고 가정하고 다음 2가지 쿼리를 통해서 데이터를 조회하려고 한다고 가정하자

# 첫번째 쿼리
SELECT *
FROM Player
WHERE name = 'Messi';

# 두번째 쿼리
SELECT *
FROM Player
WHERE team_id = 100 AND backnumber = 10;

이 2가지 쿼리에 대해서 성능 최적화를 하고 싶다면 Player Table에 관련된 Index를 걸어야 한다

  1. name 조건에 대한 Index
  2. (team_id, backnumber) 조건에 대한 index → Unique
# name 조건에 대한 Index
CREATE INDEX player_name_idx ON Player(name);

# (team_id, backnumber) 조건에 대한 Index
CREATE UNIQUE INDEX team_id_backnumber_idx ON Player(team_id, backnumber);

 

여기서 (team_id, backnumber)와 같이 복합적인 속성을 묶어서 하나의 Index를 도출해낸 것을 Composite Index라고 부른다
추가적으로 대부분의 RDBMS에서는 PK 속성에 대해서 자동으로 Index를 생성해준다
그리고 MySQL의 InnoDB 스토리지 엔진의 경우 FK까지 인덱스로 생성해준다
  • 자동으로 PK 속성에 대해서 Index를 생성해주는지 SHOW INDEX FROM Player; 명령어를 통해서 확인해보자

  • 이렇게 특정 테이블에 대한 인덱스 현황을 볼 수 있다
  • team_id_backnumber_idx의 경우 seq_in_index를 통해서 N개의 속성을 종합적으로 고려하는 Composite Index임을 알 수 있고 그 내부적으로도 seq_in_index를 통해서 각 인덱스 속성간 순서를 파악할 수 있다

 

Covering Index

Index의 특수한 개념으로 Covering Index라는 개념도 존재한다

현재 (team_id, backnumber)에 대한 Composite Index가 존재한다

그리고 다음 2가지 쿼리를 통해서 데이터를 조회하려고 한다

# 첫번째 쿼리
SELECT *
FROM Player
WHERE team_id = ?

# 두번째 쿼리
SELECT team_id, backnumber
FROM Player
WHERE team_id = ?

2가지 쿼리의 차이점은 어떤 속성들을 select할지 여부이고 두번째 쿼리를 유심히 살펴보자

두번째 쿼리는 Index Page만으로도 충분히 결과를 도출해낼 수 있고 디스크 레벨의 데이터까지 도달하지 않아도 된다는 것이다

여기서 이렇게 Index Page만으로도 충분히 조회하려는 데이터를 커버할 수 있는 경우 그 상황에서의 인덱스를 Covering Index라고 한다

 

 

B-Tree Index

Index를 저장하는 방식에 따라 B-Tree Index / Hash Index / ...등으로 나눌 수 있지만 가장 대표적인 B-Tree Index에 대해서 알아보자

 

BST (Binary Search Tree)

우선 B-Tree에 대해 설명하기 전에 BST(Binary Search Tree)에 대해서 먼저 살펴보자

BST의 특징은 다음과 같다

  • 부모 노드 기준 Left Sub Tree는 부모 노드보다 작은 값들만 가지고 Right Sub Tree는 부모 노드보다 큰 값들만 가진다
  • 모든 노드는 최대 2개의 자식 노드를 가질 수 있다

이 2가지 트리 역시 BST라고 볼 수 있다

하지만 차이점은 왼쪽은 균형이 잡힌듯한 모습이지만 오른쪽은 한쪽으로 쏠린 모습이다

  • Balanced / Non-Balanced

균형이 잡힌 왼쪽 트리의 경우 탐색의 시간복잡도가 O(log N)이지만 오른쪽과 같이 균형이 잡히지 않은 트리의 경우 O(N)에 수렴하게 되면서 BST의 장점을 살리지 못하게 된다

 

그리고 BST는 자식 노드를 최대 2개까지만 가질 수 있기 때문에 효율이 떨어진다고 할 수 있다

예를 들자면 BST는 결국 특정 노드에 대해서 최대 2개까지 가져올 수 있기 때문에 10번의 Disk Access를 한다고 가정한다면 최대 210개의 데이터를 가져올 수 있다는 것이다
  • 그러면 최대 2개가 아니라 2개 이상 → M개를 가져올 수 있는 구조의 트리는 없을까?

 

B-Tree

BST를 2-way Search Tree라고 한다면 B-Tree는 M-way Search Tree라고 한다

즉, 2개가 아닌 2개 이상인 M개를 자식 노드로 가질 수 있는 구조를 허용한다는 의미이다

 

B-Tree의 특징은 다음과 같다

  • DB나 파일 시스템에서 주로 사용되는 트리 구조이다
  • BST와 달리 자식 노드를 2개 이상 보유할 수 있다
  • BST의 Non-Balanced와는 달리 B-Tree는 Balance가 항상 맞춰져 있는 트리 구조이다
  • 특정 노드에 2개 이상의 Key가 존재할 경우 Key들은 항상 오름차순 정렬로 존재한다
  • 부모 노드의 Key 개수가 N개라면 자식 노드의 개수는 항상 N + 1개이다

BST에서 부모 노드 & 자식 노드간의 값 관계는 위와 같은 관계로 이루어져 있다

 

B-Tree라고 별 다를거 없이 BST와 유사한 관계로 부모 & 자식이 맺어져 있다

 

B-Tree의 공식?

위와 같은 특징들을 종합해서 B-Tree의 공식을 정의할 수 있다

M → 각 Node에서 뻗어나갈 수 있는 최대 자식 Node 개수
M / 2 (반올림) → 각 Node가 뻗어나갈 수 있는 최소 자식 Node 개수
M - 1 → 각 Node의 최대 Key 개수
M / 2 - 1 (반올림) → 각 Node의 최소 Key 개수

 

 

Data Insert With B-Tree

3차 B-Tree에 데이터를 Insert하는 예제를 통해서 B-Tree의 데이터 삽입은 어떠한 과정으로 이루어지는지 알아보자

N차 B-Tree에서 N이 의미하는 바는 "자식 노드를 최대 몇개까지 가질 수 있냐"이다
이를 반대로 말하자면 자식 노드의 부모 노드는 최대 N - 1개의 Key값을 가질 수 있다는 것이다
→ 그러면 예제로 살펴보는 3차 B-Tree는 특정 노드에 최대 2개의 Key값을 보관할 수 있다는 의미가 되는 것이다

 

Data Insert 과정에서 알아야 하는 개념은 다음 2가지 이다

  1. 데이터 삽입은 항상 Leaf Node에 적용된다
    • Leaf Node로 찾아가는 과정은 현재 위치상의 Root Node의 Key값과의 대소관계를 비교해서 좌-우를 선택해서 뻗어나가게 된다
  2. 노드가 넘칠 경우 노드의 Median Key를 기준으로 (1) 좌-우로 분할하고 (2) Median Key는 Level Up된다
    • 노드가 넘친다 -> N차 B-Tree에서 특정 노드의 Key 개수가 N - 1개를 초과한다
    • Median Key -> 특정 노드의 Key 값 중 가운데 Key
    • Level Up -> Median Key가 부모 노드 레벨로 옮겨진다
      • 옮겨지는 과정에서 또 노드가 넘칠경우 반복해서 Median Key를 다시 부모 노드로 옮기는 것이다

 

Example) Insert 시나리오

 

Data Delete With B-Tree

위에서 B-Tree에 데이터를 삽입하는 과정을 알아봤으니 이제 데이터 삭제하는 방법까지 알아보자

데이터를 삭제하는 과정에서 알아야 하는 개념은 다음과 같다

  1. 각 Node의 최소 Key 개수 (M/2 - 1)는 반드시 유지해야 한다
  2. 삭제 역시 항상 Leaf Node에서 적용된다
    • 삭제하는 데이터가 반드시 Leaf Node에 있어야 삭제되는것은 아니고 Internal Node에 존재해도 삭제는 가능하지만 삭제 과정을 더 큰 분류로 바라보게 되면 결국에는 Leaf Node에서 삭제된다
  3. Leaf Node 데이터 삭제
    • 삭제 후 조건 1을 만족한다면 그대로 놔둔다
    • 삭제 후 조건 1을 만족하지 않는다면 다음과 같은 step을 추가적으로 진행한다
      • Sibling Nodes(형제 노드)들에게 도움을 요청해서 조건 1을 만족할 수 있도록 데이터를 받아온다
      • Sibling Nodes들도 데이터 여유가 없다면 Parent Node에게 도움을 요청해서 데이터를 받아온다
  4. Internal Node 데이터 삭제
    • 삭제할 데이터가 존재하는 Node를 기준으로 Left/Right Sub Tree의 Predecessor or Successor 중 하나와 자리를 교체한 후 Left Node 위치에서 삭제한다
      • Predecessor → Left Sub Tree 중에 가장 큰 값
      • Successor → Right Sub Tree 중에 가장 작은 값

 

Example) Delete 시나리오

현재 트리의 상황이고 아래와 같은 시나리오로 데이터를 삭제해보자

Delete 14의 중간 과정이다

  • 위와 마찬가지로 삭제시키고 좌-우 Sibling을 모두 살펴보니 이제 더이상 Sibling의 도움을 받을 수 없는 상황에 도달하였다
  • 이 상황에서는 이제 Sibling이 아닌 Parent의 도움을 받아서 진행해야 한다

데이터 4는 지워도 해당 Node는 최소 Key 개수를 만족하기 때문에 그 후 프로세스가 없고 그 자체로 데이터 4 삭제가 완료된다

하지만 데이터 1을 삭제하는 순간 해당 Node는 최소 Key 개수를 만족하지 않기 때문에 우측 Sibling & Parent Node의 도움을 받아서 최소 Key 개수를 만족할 수 있게 된다 [15, 17]

 

하지만 여기서 [15, 17] Node의 Parent Node를 보니 최소 Key 개수를 만족하지 않음을 확인할 수 있다

이제 Parent Node의 최소 Key 개수를 만족시켜야 한다

위와 마찬가지로 Parent Node & 우측 Sibling의 도움으로 데이터를 양도받게 되고 데이터가 옮겨짐에 따라 해당 데이터 Node가 가리키고 있는 Pointer역시 이동됨을 확인할 수 있다

 

지금까지 B-Tree상에서 Leaf Node를 삭제하는 방법을 알아보았고 이제 Leaf Node가 아닌 Internal Node의 삭제도 간단한 하나의 예시로 알아보자

이러한 트리구조에서 데이터 14를 삭제해보자

  • Internal Node의 데이터를 삭제하기 위해서는 해당 Node의 Predecessor or Successor중에 하나 골라서 삭제해주면 된다
    • 데이터 14의 경우 Predecessor는 13 / Successor는 15이다
  • 여기서 Predecessor인 13을 선택했다고 가정하고 데이터 14 삭제를 진행해보자

 

B+-Tree

B+-Tree는 B-Tree의 확장된 개념으로써 다음과 같은 특징이 있다

  • B-Tree는 Internal & Leaf Node 모두 Data에 대한 Pointer를 보유할 수 있다
    • Internal & Leaf 모두 실질적인 Data에 접근이 가능하다는 의미이다
  • B+-Tree는 오직 Leaf Node만이 Data에 대한 Pointer를 보유할 수 있다
    • Internal은 오직 다음 노드에 대한 Pointer만 보유하고 있고 실질적인 Data에 대한 접근은 Leaf Node에서만 가능하다는 의미이다
  • 그리고 Leaf Node끼리는 LinkedList로 연결되어 있다

 

B+-Tree는 특정 값을 찾아야 하거나 특정 범위 내에 값들을 찾아야 하는 상황에서 모든 Leaf Node에 실질적인 Data Pointer가 존재하고 Leaf Node끼리 LinkedList로 연결되어 있기 때문에 탐색에 매우 유리한 자료구조이다

  • Internal Node → 다음(자식) 노드를 위한 Pointer가 존재
  • Leaf Node → 실질적인 Data Pointer가 존재
탐색에 있어서 B+-Tree가 B-Tree보다 유리한 이유는 다음과 같이 말할 수 있다

1. B+-Tree는 Internal Node에 Data Pointer가 존재하지 않기 때문에 더 많은 Key를 저장할 수 있고 이로 인해 트리의 높이가 줄어들어서 탐색 시간이 줄어든다
2. B+-Tree의 Leaf Node는 모두 LinkedList로 연결되어 있기 때문에 범위 탐색에 굉장히 유리하고 순차적 데이터 액세스가 빠르게 수행된다
3. B+-Tree에서 모든 데이터는 Leaf Node에 저장되기 때문에 탐색 시간이 일관되게 유지된다

 

위와 같이 B+-Tree는 굉장히 많은 장점을 보유하고 있지만 단점 또한 존재한다

  • 모든 Data Pointer가 Leaf Node에만 저장되기 때문에 Leaf Node에 추가적인 공간이 더 필요하고 Leaf Node간의 연결을 위한 포인터도 추가적으로 필요하다
    • 이로 인해서 B-Tree보다 더 많은 메모리를 차지할 수 있다
  • 모든 데이터가 Leaf Node에 저장되기 때문에 데이터에 대한 액세스가 항상 Leaf Node까지 이루어져야 하고 그에 따라서 B-Tree에 비해 최소 데이터 액세스 비용이 높을 수 있다

 

 

Why B-Tree Based Index?

그러면 왜 대부분의 DBMS는 Index의 자료구조로 B-Tree Based를 활용하는걸까?

 

B-Tree vs Hash

사실 B-Tree Based Index말고 Hash Index역시 존재한다

Hash Table은 [key: value]로 데이터를 저장하는 자료구조로써 특정 key에 대해서 굉장히 빠르게 value를 가져올 수 있는 자료구조이다

특정 key에 대해서 조회 시간복잡도가 O(1)인 Hash Table을 왜 DBMS Index에 범용적으로 활용하지 않는걸까?

그 이유는 Hash Table은 =연산(Equality)에 특화되어있기 때문이다

해시 함수는 값이 1정도만 달라져도 완전히 다른 Hash Function Result를 도출한다

이러한 특성으로 인해 부등호 연산 or 정렬이 자주 활용되는 조회를 위해서는 Hash Table이 적절하지 않은 것이다

  • 범위나 부정형 조건에 따른 SQL Query는 Hash Table Index를 활용할 수 없다

 

B-Tree vs BST

Hash Index가 적절하지 못한 이유는 알았으니 이 다음으로는 BST 구조와 비교해보자

사실 BST 구조는 특징을 생각해보면 왜 B-Tree가 유리한지 알 수 있다

DB는 Secondary Storage에 존재하고 초기 데이터 역시 조회를 통해서 Main Memory에 캐싱하지 않는 이상 Secondary Storage에 존재한다

간단하게 CPU / Main Memory / Secondary Storage만 비교해본다면 처리 속도는 CPU > Main Memory >>> Secondary Storage이다
→ 결국 조회 성능을 최적화하기 위해서는 Disk(Secondary Storage) I/O 횟수를 최소화시켜야 한다

BST 구조와 B-Tree 구조를 비교해보자면 BST 구조는 아무리 최적화를 시켜도 특정 Node에 대한 자식 Node를 최대 2개까지 보유할 수 있다
하지만 B-Tree는 M-Way Search Tree이므로 M에 따라서 자식 Node를 최대로 보유할 수 있는 개수가 달라진다

자식 Node를 많이 가지면 가질수록 최종적인 Data Pointer에 Access하기 위한 Depth가 줄어든다
→ 이러한 이유로 인해서 B-Tree가 BST 구조에 비해 조회에 유리하다는 것을 알 수 있다

  • B-Tree 구조가 탐색 범위를 더욱 빠르게 좁혀나갈 수 있기 때문에 Disk I/O 횟수를 최적화시킬 수 있고 이러한 이점으로 인해 BST 구조보다 B-Tree 구조가 Index에 더 적합하다는 것이다

 

 

티스토리툴바