DB indexing이란?
index는 우리나말 말로하면 색인. 책 뒷쪽에 많이 있는 바로 그것 index다.
책에서 색인이 있으면, 원하는 페이지를 빠르게 찾을 수 있다. 읽었던 내용을 까먹었을 때도, 책 전체를 전부 다시 읽을 필요 없이 색인을 통해 찾을 수 있다.
DB Index도 이와 비슷한 역할을 한다.
DB에서 원하는 정보를 검색하기 위해서는 모든 row를 다 한 번씩 확인해야한다.
시간 복잡도가 O(N) 밖에 되지 않아서 큰 문제가 되지 않는다고 생각 할 수 있다.
하지만 DB 안에 있는 데이터의 양이 커질 수록 생각보다 큰 로드를 초래한다.
Index는 검색 시에 모든 정보를 조회해서 원하는 값을 찾을 필요 없도록 만들어준다.
그래서 책에 비유하자면 색인과 비슷한 것이다.
그렇다면 이런 DB의 인덱스는 어떤 방식으로 구현되어 있을까?
B+Tree
DB index는 많은 경우 B+tree를 사용한다.
MySQL에서도 기본값으로 B+Tree를 사용하는 걸로 알고 있다. (InnoDB에서 인덱싱 방식으로 B+Tree를 사용)
B+tree를 이해하기 위해서는, 먼저 B-Tree 에 대해 알아야한다.
B-Tree
B-Tree는 검색 성능 향상을 위해 일정 높이를 유지하는 Balanced Tree이다.
모든 leaf 노드(가장 바닥에 있는 노드) 동일한 깊이를 유지해야한다.
B-Tree는 다음과 같은 특성을 가진다.
- 부모의 key의 수가 n개라면, n+1개의 자식을 갖는다.
- 노드의 key는 항상 정렬된 상태다.
- 모든 leaf node들은 같은 level에 있어야 한다.
B+Tree
이러한 B-Tree 유사하지만 데이터 접근을 더 빠르게 하기 위해 B+Tree를 활용합니다.
B+Tree는 값이 전부 leaf 노드에 모여있습니다. 상부는 그저 인덱스를 위한 값들입니다.
또한 모든 leaf 노드들은 doubly linked list 형태를 띄고 있습니다.
그렇기 때문에 데이터를 찾아 이곳 저곳 이동할 필요가 없습니다.
DB에서 가장 중요한 요소 중에 하나는 검색속도이기 때문에, B+Tree의 형태를 사용해서 인덱스를 구현합니다.
*B+Tree 이외에도 hash table, dense indexing, sharpse indexing등 알아볼 내용이 많지만, 그건 다음 시간에 알아보도록 하자.
Index의 장단점
장점
장점은 당연하게 검색이 빠르다는 것이다.
단순 select를 했을 때보다 훨씬 빠르게 정보를 얻을 수 있다.
단점
- 추가 삭제가 느려진다.
검색이 빨라진 만큼 새로운 데이터를 넣거나 삭제하는 시간이 오래걸릴 수 밖에 없다.
B+트리 구조를 유지해야하기 때문에, 데이터를 넣거나 삭제하는 행동이 더 비싸진다.
- 메모리를 사용한다.
인덱싱 된 정보도 어딘가 저장하고 있어야 한다. 결국 DB의 메모리를 추가로 사용해야하는 대가가 있다.
결론
결론은 적절하게 인덱스를 사용해야한다.
인덱스가 검색을 빠르게 해주기 때문에, 간단하게 생각해서는 모든 entity에 인덱스를 추가하면 좋지 않을까 생각할 수도 있다.
하지만 이렇게 되면 추가로 저장공간을 사용해야하며, Delete, Insert가 더 어려워지게 된다.
따라서 적당한 범위내에서 delete insert 보다 select가 많이 되는 entity에 사용 인덱스를 사용하는 것이 좋다.
참고 자료
https://grip.news/archives/1428
