인덱스 키의 빈번한 Update로 발생할 수 있는 오버헤드

인덱스 키의 빈번한 Update가 문제인 이유

인덱스

우리가 책을 읽을 때 목차가 없다면 원하는 부분을 찾기 위해 책의 앞 부분 부터 한 페이지씩 넘겨가며 내용을 찾아야 할 것이다. 이러한 상황을 막기 위해 책은 페이지와 매핑한 목차를 제공한다. 데이터 베이스에서도 탐색 성능 향상을 위해 책의 목차와 같은 인덱스를 제공한다. 즉, 인덱스는 데이터 베이스의 탐색 성능 향상을 위한 목차이다.

인덱스의 자료구조

이진 트리의 경우 그 균형이 맞다면 O(log_2 N) 의 효율성을 가진다. 하지만 균형이 맞지 않은 트리의 경우 링크드 리스트와 같아 선형 탐색을 하게 되고 최악의 경우 O(N) 의 효율성을 가지게 된다.

 

때문에 트리는 균형을 맞추기 위해 요소가 추가, 갱신, 삭제 될 때 마다 균형을 맞추기 위한 리밸런싱이 필요하다. 리밸런싱은 아래와 같이 선형의 모양을 띈 트리를 가운데 요소를 회전시켜 균형을 맞추는 작업을 의미한다.

 

 

 

인덱스는 탐색 속도 향상이 목적인 만큼 자료 구조로 균형 트리를 선택했다.
MySQL은 이진 트리가 적은 팬아웃 때문에 높이가 높아지고 그 균형 트리 유지를 위해 잦은 트리 리밸런싱이 발생하여 팬아웃이 2개 이상인 B+Tree를 선택했다.

인덱스의 오버헤드

인덱스의 리밸런싱

인덱스를 사용한다는 것은 탐색 성능 향상을 위해 추가 저장공간을 확보하여 해당 색인정보를 저장해 두는 것을 의미한다. 또한 인덱스의 자료구조는 위에 설명한 듯이 균형 트리인 B+Tree 이다. 때문에 균형 트리의 특성상 추가/삭제/갱신 작업이 시행될 때 그 균형을 맞추기 위해서 인덱스의 래밸런싱이 필요해진다. 즉, 인덱스는 검색 성능 향상을 위해 추가/삭제/갱신 작업의 일부 성능을 포기하는 것이다.
그럼에도 불구하고 인덱스를 사용하는 이유는 데이터 베이스의 대부분의 요청은 조회 작업이기 떄문이다.

키의 갱신은 대개 인덱스 트리를 리밸런싱 하는 작업으로 이어진다. 때문에 갱신이 잦은 컬럼을 인덱스 키로 잡는 것은 잦은 리밸런싱을 발생 시킬 수 있어 주의해야 한다.

업데이트와 삭제로 인한 단편화

B+Tree의 노드는 하나의 디스크의 페이지로 볼 수 있다. B+Tree의 경우 Leaf Node에 모든 데이터를 몰아둔다. 그런데 키에 업데이트와 삭제는 이러한 노드 중간 중간을 비어두게 한다. 즉, 하나의 노드(페이지)에 저장되는 키의 개수가 줄어들게 되고 탐색을 할 때 더 많은 페이지를 읽어야 하는 상황으로 이어질 수 있다.

이러한 문제를 해결하기 위해서 데이터베이스는 노드에서 삭제되거나 갱신된되어 빈 공간들을 단편화 해야한다. 즉, 노드를 연속된 공간으로 만들기 위한 단편화 작업을 하게되어 추가적인 오버헤드가 발생한다.

참조

• Real MySQL
• Database Internals