-
[데이터베이스] index란 무엇일까?CS/데이터 베이스 2021. 10. 15. 21:54
최근 졸업 프로젝트, SW마에스트로 프로젝트를 하면서 여가시간이 나지 않아 블로그를 쓰지 못했다..
사실 조금씩 시간만 냈다면 쓸 수 있었을 텐데 이런저런 핑계를 댄것 같다.
2학기 중간고사가 다가오면서 여러 공채들 서류를 내고, 코딩테스트도 보면서 시간이 빠르게 흘러 갔던것 같다.
11월 중반에 끝나는 SW마에스트로 프로젝트를 하면서 데이터베이스 인덱스에 관해서 좀 더 깊게 알고자 했다.
책, 인강 등 지원금이 많이 나왔기 때문에 Spring 인강을 통해 많은 기술들을 접해볼 수 있었고, 추후 개발자에게 필요한
여러 책들을 살 수 있어 좋았다.
그 중 오늘은 Real MySQL8.0에 관한 내용 중 Index관련 하여 글을 적어보고자 한다.
Mysql 스토리지 엔진 중 InnoDB 엔진에 관해 작성했다.
1. 인덱스(index) 란?
정의: 데이터베이스 분야에 있어서 테이블에 대한 동작의 속도를 높여주는 자료구조. (위키백과)
사실 이렇게 정의만 보았을 때 그래서 어떤 자료구조고 어디에 저장되어 있는데? 라는 의문이 들 수 있다.
먼저 인덱스의 자료구조는 크게 해시, B-Tree (Balanced) 로 구성되어 있다.
물론 더 많은 자료구조들이 있지만 위의 두가지 정도만 알아보도록 하자.
- 해시 인덱스
출처: https://en.wikipedia.org/wiki/Hash_table 인덱스 자료 구조로 hash가 사용된다면, 다음과 같이 탐색이 이루어질 수 있다. (key를 통해 index를 구현했다고 하자)
해시 인덱스의 장점으로는 hash function을 통해서 key값을 주게되면 해당하는 key가 있는 bucket을 알 수 있다.
따라서 O(1) 만에 접근이 가능하여 아주 빠르게 해당하는 key값을 조회할 수 있다.
하지만, hash 자료구조는 범위 질의에는 약하다.
그 이유는 어떤 column에 대해 해시 인덱스를 구성했을 때 해당하는 column 순으로 해시값이 정렬되어 있지 않기 때문이다.
그렇게 때문에 범위 질의는 In ( ) 절을 통해서 가능하며 비교 연산자로 찾는 것은 불가능하다.
B-Tree의 경우 리프 노드들이 key값에 대해 정렬된 상태이기 때문에 범위 질의에서 a <= key <= b 라면,
a에 해당하는 leaf 노드를 찾고 b에 해당하는 leaf 노드까지 쭉 탐색이 가능하기 때문이다.
하지만 B-Tree일 경우에도 범위질의를 사용하는데 주의할 필요가 있다.
Clustered index와 non-clustered index 쪽에서 나머지는 설명하도록 하겠다.
- B-Tree 인덱스
B-Tree는 Balanced Tree이다. 말 그대로 균형잡힌 트리이며, 리프 노드까지의 height가 모두 같은 것이 특징이다.
B-Tree에서는 해당하는 트리가 균형이 잡힐 수 있도록, merge 또는 split을 통해 재균형 과정을 반복한다.
출처: https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Tree B-Tree에 대해 자세히 알고 싶다면 위의 출처를 이용해 들어가 보면 된다.
2. Clustered Index
출처: https://hoing.io/archives/5960 위의 그림은 Clustered Index로 구성된 테이블의 예시이다. 원하는 CustId를 따라가 보았을 때 해당하는 페이지에
비슷한 값들이 Clustered(군집화) 되어 있는 것을 볼 수 있다. 이것이 Clustered Index의 특징이다.
MySQL에서 Clustered Index는 InnoDB 스토리지 엔진에서만 지원한다.
Clustered Index는 PK 기준으로 정렬이되며 이는 데이터의 물리적 위치를 PK가 결정한다는 것을 유의 해야한다.
따라서 PK 값이 바뀌게 된다면 데이터의 물리적 위치까지 변하게 될 것이고 이는 데이터가 많을 수록 리스크가 커진다.
Clustered Index는 PK 기준으로 저장 위치가 결정되므로, 한 테이블당 하나 밖에 있을 수 없다.
하나를 기준으로 물리적으로 정렬된 데이터를 다른 기준으로 정렬하지 못하기 때문이다.
Clustered Index와 B-Tree Index와의 차이점은 Index의 leaf 노드에는 레코드의 모든 컬럼값이 같이 저장되어 있다.
이의 장점은 Range search를 통해 1~9번의 PK를 조회 할 때 각 페이지에 PK값이 1~4, 4~9값이 Clustered 되어 있기 때문에
Disk I/O가 적게 발생하게 될 것이다.
3. Un-Clustered Index
출처: https://courses.cs.washington.edu/courses/cse544/99sp/lectures/storage/sld025.htm Un-clustered Index는 기본적으로 leaf node에 포함된 정보가 Clustered Index와 다르다.
데이터들이 Clustered Index로 정렬이 되어 물리주소로 저장되어 있기 때문에,
다른 Column을 기준으로 보았을 땐 데이터 파일들이 뒤죽박죽으로 되어 있을 것이다.
Unclustered Index의 leaf 노드에는 (index key, PK) 로 저장이 되어있다.
(물론 Clustered Index가 없는 테이블에는 PK 대신 그 위치를 식별할 수 있는 Rid(파일 식별자 + 페이지 번호 + 페이지 내 행 번호)로
되어 있을 것이다.)
리프노드까지 탐색에 성공했을 때 PK를 기준으로 clustered Index를 통해 해당하는 페이지를 찾을 수 있다.
즉, PK값을 이용해 Clustered Index를 한 번 더 검색한 후, Clustered Index의 리프 페이지에 저장돼 있는 레코드를 읽는다.
이렇게 Clustered Index, Un-Clustered Index를 보았다. 이때 Un-Clustered Index에서 Range Search를 할 때 유의 해야 할
이유가 어떤 것인지 떠올랐다면 대단한 것이다.
내가 찾고자하는 범위 내 데이터들은 실제러 여기저기 다른 디스크 페이지에 있을 확률이 있고, 범위가 넓어짐에 따라
오히려 Full Scan 보다 더욱 안 좋은 성능을 낼 수도 있다.
(물론 쿼리 옵티마이저가 이런 부분은 계산할 것으로 추정된다.)
참고 자료:
https://www.freecodecamp.org/news/database-indexing-at-a-glance-bb50809d48bd/