DB - 인덱스(Index)란?
대학생 강의와 유튜브에서 데이터베이스에서 인덱스가 중요하다... 풀스캔은 안좋기 때문에 인덱스처리를 해줘라... 라는 내용을 들었고, 대충 인덱스가 무엇인지 알지만 스스로 깊이 공부해보고 싶어서 포스팅해본다.
실제로 팀 프로젝트를 하면서 조회 쿼리문을 더 빠르기하기 위해서 사용한적 있다.
개발자가 되기위해선 사용할 줄만 알면 안된다!
일상 생활에서 인덱스
책에서 인덱스를 많이 접해보았다.
만약 책에서 인덱스가 없다면 어떻게 될까? 매일 내가 원하는 부분을 보기위해 책을 드르륵? 긁으면서 찾을 것이다.
인덱스가 있기에 우리가 원하는 내용을 찾을때 바로 볼 수 있다.
데이터 베이스의 인덱스도 같은 맥락이다. 공공데이터를 이용하여 데이터베이스에 저장하면, 수 만개의 데이터가 한 테이블에 저장된다.
만약 모든 아파트에 대한 데이터가 있다고 생각하자!
덕상아파트라는 이름을 가진 아파트 데이터를 찾고 싶다면 Select쿼리를 날려서 Full Scan을 할 것이다. 그 수많은 데이터를 다 뒤져본다는 뜻이다. 이는 당연히 성능에 영향을 미칠 것이다.
데이터베이스의 인덱스(Index)
디비의 인덱스는 책의 인덱스와 같이 추가적인 저장공간에 미리 정렬된 정보를 저장하여, 원하는 데이터를 찾기 위해 사용된다.
즉 디비의 인덱스는 추가적인 저장공간을 사용해서 테이블 검색 속도를 향상 시키는 자료구조이다.
인덱스는 데이터의 Key와 데이터의 물리적 위치가 저장되어 있다.
예를 들면 '키에 3번인 데이터는 00테이블의 17번째 행에 저장되어있다.' 이다.
인덱스는 SELECT, WHERE 조건문에 컬럼에 대한 조회 성능을 개선할 때 사용된다.
그렇다면 왜? 인댁스를 사용할까?
왜 디비에 인덱스를 사용하나?
인덱스는 저장공간이라고 했다. 그 크기는 테이블의 데이터 크기에 비해 매우 작다. 따라서 인덱스는 테이블 보다 메모리에 적재하기 쉽다. 메모리(RAM)에 최대 1GB를 적재할 수 있고, 하드디스크에 아파트와 관련된 100GB 데이터베이스가 존재한다고 생각해보자.
자 우리는 그린빌아파트라는 데이터를 찾고자 조회쿼리문을 날렸다. 하필 그린빌아파트라는 데이터가 데이터베이스의 맨 끝에 있다면 100GB 데이터를 모두 탐색후에 찾을 수 있다는 것이다. But 우리가 가진 메모리는 1GB이기 때문에 100GB의 데이터를 100개로 나눈뒤, 100번 꺼내와야 된다. 하지만 주 기억장치(하드디스크)에 비해 보조 기억장치(RAM)의 I/O 성능은 매우 떨어진다.
인덱스를 사용하면, 이런 불필요한 I/O를 줄여 데이터 탐색 성능을 개선할 수 있다. 인덱스가 테이블의 데이터크기에 작기때문에 더 많이 적재할 수 있다는 특성을 이용해서 인덱스만을 메모리에 적재하고, 원하는 데이터의 물리적 주소를 찾아 접근하면 된다.
인덱스가 만약 없다면 어떻게 될까?
인덱스를 사용하지 않는다면 당연히 Full Scan Table이 발생한다. 그냥 쉽게말해 전부 하나하나 보면서 찾는 것이다.
위 단락에서 말하는 메모리에 데이터를 적재하는 방식이다. 즉 I/O 비용이 많이 발생해 가장 느린 조회 방식이다.
Full Scan Table 방식은 조회하고자 하는 칼럼이 인덱스가 존재하지 않거나, 존재 하더라도 디비의 옵티마이저가 인덱스 대신 풀 테이블 스캔으로 탐색하는 것이 더 좋다고 판단하면 실행된다. 옵티마이저에 대한 부분은 추후 포스팅하여 아래 링크에 남겨두도록 하겠다.
인덱스 알고리즘
해시 테이블(Hash Table)
Key를 사용해서 빠르게 Value를 가져오는 자료구조로 생각되는 것은 해시 테이블이다. 해시 테이블은 Key만 알고있다면 Value를 O(1)의 시간 복잡도로 조회할 수있다는 특징을 가지고 있다. 이거 완전히 데이터베이스에 알맞은 자료구조인 것 같다.
But! But! But!, 실제로는 많은 DBMS들은 해시 테이블을 사용하지 않는다. 이 좋은것을 왜?
해시 테이블은 부등호 연산에 적합하지 않기 때문이다. 해시테이블은 정렬이 안되어 있다. 덕상아파트를 찾기에는 더할 나위 없지만, 우리는 이런 조회만 사용하는가? 아니다. 35평 이상의 아파트를 조회하기도 한다. 즉 정렬이 되어있지 않기때문에 부등호 연산이 들어가 조회를 할 경우 모든 데이터에 접근을 할 것이다. 이러한 이유 때문에 해시테이블을 잘 사용 안한다고 한다.
부등호 연산은 <, > 말고도 NOT(~) 연산도 포함된다. NOT연산은 사실 크거나 작은 데이터를 찾는 연산이다. 아닌게 아니라!
B-Tree
B-Tree는 메모리에 담기 어려운 큰 크기의 데이터를 다루기 위해 사용된다. 뭔가 이진트리와 구조가 유사하다. 이진트리는 자식 노드가 2개인 반면 B-Tree는 자식 노드가 2개 이상이다. 하지만 자식 노드수를 키움으로써 트리의 전체적인 높이를 줄여 빠른 탐색 속도를 얻을 수 있다.
또한 B-Tree의 특징으로는 리프 노드들이 같은 Level을 가지는 것이다.
편향된 이진 트리
위 그림과 같이 편향된 이진트리를 보라. 이 트리는 이진트리의 빠른 검색속도를 가지지 못한 불쌍한 녀석이고, 링크드 리스트 처럼 되어버린다. 하지만 B-Tree는 의도적으로 리프 노드의 레벨을 동일하게 유지함으로써 위와 같은 문제를 해결한다. 이러한 특성을 가진 트리를 Self-Balance-Search-Tree라고 한다.
키와 포인터
이진 트리와 다르게 B-Tree는 한 노드에 여러가지 데이터를 저장할 수 있다. 데이터베이스에서는 B-Tree의 노드를 페이지 또는 블럭이라고 부르며, 노드 내의 데이터를 Key라고 부른다. M차 B-Tree는 M-1개의 키를 가질 수 있다. 또한, 노드 내부의 키들은 오름차순 정렬된 상태를 유지한다.
각 노드의 키들은 좌우 다른 노드를 가르키는 포인터를 가지고 있다. 왼쪽 포인터는 자신의 키보다 작은 데이터를 가진 노드를 가르키고, 오른쪽은 이 반대이다. 이것은 이진 트리의 특징과 유사하다.
데이터 포인터
노드의 각 키는 실제 데이터의 물리적 위치를 가르키고 있는 데이터 포인터를 가진다. 키를 기준으로 데이터를 탐색하여, 일치하는 키를 발견한다면, 실제 데이터를 얻을 수 있다.
데이터베이스에서는 특정 칼럼으로 인덱스를 생성할 수 있는데, 이때 칼럼의 값이 키가되고, 테이블의 행(물리적 위치)는 데이터 포인터가 된다.
조회는 겁나 빠르지만, 삽입/수정/삭제는 겁나 느리다.
아래의 블로그를 참고해보면 왜 느린지 알 수 있다.
[자료구조] 그림으로 알아보는 B-Tree
B트리는 이진트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 벨런스를 맞추는 트리입니다.
velog.io
아래는 5, 10, 15, 20, 25, 28, 30, 31, 33, 35, 40, 45, 50, 55, 60, 65 중에서 일반적인 선형 탐색과 B-Tree가 28을 찾는 과정의 애니메이션이다.
일반적인 배열 혹은 리스트는 정렬된 상태를 유지하지 않으므로, 선형 탐색 과정이 의 시간복잡도를 갖는 것을 확인할 수 있다. 위 애니메이션에서는 총 11번의 탐색을 거쳐 28을 찾는다.
B-Tree는 정렬된 트리이므로 탐색이 의 시간 복잡도를 갖는다. 28이라는 숫자를 찾는데 고작 4번의 탐색을 거친다.
이렇기 때문에 B-Tree는 검색이 빠르다.
B+ Tree
B+Tree는 B-Tree를 개선시킨 자료구조이다. 실제로 MySQL(InnoDB) 등 많은 DBMS에서는 B-Tree 대신 B+Tree를 사용한다.
그러면 B+Tree의 특징이 뭐가 있길래, 이 자료구조를 많이 사용할까?
특징
- 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보할 수 있다. 즉 더 많은 Key를 수용함으로서 트리의 높이는 더 낮아져서 탐색 속도가 B-Tree에 비해 더 향상된다. 하지만, 이런 특징으로 트리에 중복된 키가 존재할 수 있다.
- B+Tree는 순차 검색에 유리하다. 데이터베이스 특성상 부등호 연산이 많이 발생하게 되는데, B-Tree는 트리 순회를 해야되기 때문에 부등호 연산이 조금 오래걸린다. 이러한 단점을 극복하기 위해 B+Tree는 리프 노드를 연결 리스트로 연결했다. 이러한 형태 덕분에 정렬된 상태의 리프 노드를 순차 검색할 수 있게 된것이다. 그래서 인덱싱에 더욱 적합한 자료구조가 될 수 있었다.
- 실제 데이터에 접근하기 위해서는 무조건 리프 노드까지 탐색해야한다. 따라서 운이 좋으면, 금방 데이터를 찾을수도 있는 B-Tree와 다르게, B+Tree는 고정적으로 O(logN)의 탐색 시간을 갖는다.
B-Tree VS B+Tree
| 구분 | B-Tree | B+Tree |
| 데이터의 저장 | 리프 노드, 브렌치 노드 모두 데이터 저장 가능 | 오직 리프 노드에만 데이터 저장 가능 |
| 트리의 높이 | 높음 | 낮음 (But 한 노드 당 Key를 많이 담을 수 있음) |
| 풀 스캔 시, 검색 속도 | 모든 노드 탐색 | 리프 노드에서 선형 탐색 |
| 키 중복 | 없음 | 있음(리프 노드에 모든 데이터가 있기 때문에) |
| 검색 | 자주 접근 되는 노드를 루트 노드 가까이 배치할 수 있고, 루트 노드에서 가까울 경우, 브렌치 노드에도 데이터가 존재하기 때문에 빠름 | 리프 노드까지 가야 데이터 존재 |
| 링크드 리스트 | 없음 | 리프 노드끼리 링크드 리스트로 연결 |
자 이제 인덱스의 자료구조로 Hash Table을 잘 사용하지 않는 이유와 B-Tree와 B+Tree의 차이점과 각 특징을 알아 보았다.
이제 인덱스에 대해서 조금더 궁금한 점들을 알아보자.
인덱스는 무조건 사용해야 되는가?
공부한 결과 No이다.
인덱스를 사용하면, 전반적인 조회 쿼리의 성능을 개선하여 시스템 전체의 부하를 줄일 수 있다. 인덱스를 위한 저장 공간은 데이터베이스의 전체 공간의 약 10%라고 한다. 즉 남용하거나 잘못 사용하면 불필요한 저장 공간을 낭비하게 된다.
또한 B-Tree나 B+Tree를 보면서 조회 성능은 증가할 수 있으나, 생성/수정/삭제 작업에 대한 성능은 오히려 낮아진다. 즉 인덱싱한 테이블이 조회보다 생성/수정/삭제 작업이 더 많이 발생하면 오히려 전체 성능이 저하될 수 있다. 예를 들면 생성이 많이 일어나는 채팅 메시지 테이블처럼.
그러면, 선택 기준은 어떻게 되는가?
인덱스 대상 칼럼은 카디널리티(Cardinality)가 높은 칼럼을 우선적으로 선택해야 유리하다. 카디널리티는 데이터 집합에서 유일한 데이터의 개수를 의미한다.
예를 들어 아파트 테이블을 인덱싱할때 카디널리티가 낮은 지역 컬럼 대신 카디널리티가 그나마 높은 아파트이름 칼럼을 인덱싱 하는 것이 바람직한다.
끝
이번 포스팅에서는 디비 인덱스와 간단한 개념 그리고 사용되는 자료구조에 대해서 알아보았다. 하지만 실제로 데이터베이스가 내부적으로 인덱스를 어떻게 관리하고, 데이터를 찾아가는지는 잘 모르겠다.
다음 포스팅에서는 클러스터형 인덱스와 비 클러스터형을 공부하고, 실제로 인덱스가 어떻게 구성되어 있고, 데이터를 어떻게 찾아가는지 공부하고 정리할 것이다.
또한 공부한 것을 토대로 Mysql을 이용해서 실습또한 진행해보겠다.