실무 경험이 점점 쌓아가며, 데이터베이스에 인덱스를 추가하는 건 참 쉬운 일처럼 다가온다.
하지만, 명확히 어떤 구조에 의해서 데이터베이스에 인덱스 라는 개념이 생겼는지에 대해서는 설명을 할 수가 없는 걸 깨닫게 되었고, 정리를 해보려고 한다.
들어가며
신입 시절에, 당연히 관계형 데이터베이스 중에 접근성이 가장 좋은 MySQL로 개발을 하고 있었다.
크롤링한 데이터를 적재해야했기에, 1주일에 약 20만건의 데이터가 저장되어야 했다.
약 30만건의 데이터가 적재되었을 때, 조회를 페이지네이션으로 했음에도 불구하고 조회가 굉장히 느려졌고, 쓸 수 없다고 판단했다.
당시 인덱스의 개념만 알았더라면, 간단하게 해결했겠지만 신입들끼리 모여있었기에 문제 해결을 할 수가 없었다.
그래서 결국 NoSQL로 넘어갔고, 인덱스를 걸지 않았음에도 불구하고 100만건의 데이터까지는 괜찮았고 지속적으로 데이터를 삭제해주었었다.
지금 생각해보면 처음부터 NoSQL로 시작해서, 인덱스를 걸어서 사용했을 것 같다
인덱스란?
우리가 책의 특정 챕터를 찾을 때, 모든 페이지를 다 훑는 게 아닌 챕터당 페이지수가 적혀있는 목차가 있듯이 데이터베이스의 인덱스는 책의 색인과 같다.
인덱스는, 추가적인 저장 공간에 쓰기 작업을 함으로써 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다.
특정 컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터들을 오름차순으로 정렬하여 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장된다.
인덱스의 자료구조
가장 대표적인 해시테이블, B+Tree의 구조에대해서 알아보려고 한다.
해시테이블(Hash Table)
빠른 데이터 검색이 필요할 때 유용하다. 동등 비교 검색에는 최적화되어 있지만, 범위를 검색하거나 정렬된 결과를 가져오는 목적으로는 유용하지 않다. 주로 In-Memory 데이터베이스에서 사용한다.
해시 테이블은 기존 해시 알고리즘과 동일하게, Key, Value 형태로 저장하여 조회한다. (시간복잡도 O(1))
B+Tree
B+Tree는 자식 노드가 2개 이상은 B-Tree를 개선시킨 자료구조이다.
B-Tree와는 다른 특성을 가지고 있는데,
•
리프노드(데이터노드)만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드(인덱스노드)들은 데이터를 위한 인덱스(Key)만을 갖는다.
•
리프노드들은 LinkedList로 연결되어 있다.
•
데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 된다.
특정 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생하는데, 이러한 이유로 B-Tree의 리프노드들을 LinkedList로 연결하여 순차검색을 용이하게 하는 등 B-Tree를 인덱스에 맞게 최적화하였다.
비록 B+Tree는 O(𝑙𝑜𝑔2𝑛)의 시간복잡도를 가지고 있지만, 인덱싱에 더욱 적합한 자료구조가 되었다.
→ InnoDB에서 사용된 B+Tree 구조 InnoDB에서의 B+Tree는 일반적인 구조보다 더욱 복잡하게 구현이 되었다. InnoDB에서는 같은 레벨의 노드들끼리는 Linked List가 아닌 Double Linked List로 연결되었으며, 자식 노드들은 Single Linked List로 연결되어 있다
Ref:
다음 챕터는, 인덱스에 대해서 조금 더 깊게 파고들어가 볼 예정이다.
