[DB이론] 인덱스(Index)

 

1. 인덱스

인덱스는 키 값으로 행 데이터의 위치를 식별하는데 사용하는 기능입니다.

그러기 위해서는 원본 테이블을 기준으로 잘 정렬된 별도의 테이블, 즉 인덱스 테이블을 생성해야 하고, 이로 인해 데이터 엑세스 성능을 높일 수 있습니다.

인덱스의 존재 유무에 따라 쿼리의 결과는 달라지지 않습니다.

 

인덱스를 효과적으로 사용하려면 정규화가 되어 있어야 합니다.

정규화가 되어 있지 않은 테이블은 컬럼이 많으며, 이에 따라 조합할 수 있는 인덱스가 많아지게 됩니다.

인덱스가 많으면, 갱신 성능이 나빠지고 디스크 공간도 많아지므로 인덱스를 효과적으로 사용하려면 정규화가 잘 되어 있어야 합니다.

 

 

인덱스 특징

인덱스는 다음과 같은 특징이 있습니다.

• 인덱스 테이블
• 이진트리 검색( 뒤에서 살펴볼 인덱스 종류 )을 위해서는 미리 데이터가 정렬되어 있어야 합니다.
• 하지만 데이터가 항상 정렬되어 있기란 어렵기 때문에, 특정 컬럼을 기준으로 이진트리를 생성하는 새로운 테이블을 생성하여 미리 정렬된 상태를 만들어야 합니다.
• MySQL에서는 테이블을 생성할 때 특정 컬럼을 PK로 설정하면, 그 컬럼에 대한 인덱스 테이블을 자동으로 만듭니다. ( 링크 )
• 인덱스 테이블은 일반 테이블과 같이 데이터베이스 객체입니다.
• 인덱스 테이블만으로는 아무런 기능을 할 수 없기 때문에 다른 테이블에 의존적입니다.

 

검색 성능이 좋다고 항상 좋은 것은 아닙니다. 언제나 trade off가 존재하죠.

인덱스를 사용하면 다음과 같은 단점이 있습니다.

• 자원
• 인덱스 테이블이라는 테이블이 생성되므로 메모리를 많이 소비하게 됩니다. 
• 따라서 PK 같은 컬럼들을 인덱싱 하도록 하고, 많은 컬럼을 인덱스로 사용하지 않도록 남용하지 않는 것이 좋습니다.
• SELECT를 제외한 INSERT, UPDATE, DELETE에 대한 성능 저하
• 어떤 테이블에 데이터를 추가할 경우, 이에 관계된 인덱스 테이블에서는 데이터를 정렬해야 하므로 전체적인 성능이 저하됩니다.

 

 

 

 

2. 인덱스 종류, B+ 트리를 중심으로...

인덱스에는 여러 종류가 있습니다.

일반적으로 B+트리 인덱스를 사용하는데, 어떤 인덱스를 사용하는지는 벤더 제품에따라 다릅니다.

 

다음은 인덱스의 종류에 대한 간단한 소개입니다.

• 해시 인덱스 ( Hash Index ) - 참고
• 해시 테이블을 이용한 인덱스로, 해시값을 사용합니다.
• 해시 값을 사용하기 때문에 매우 빠르지만, 등가비교검색( 값이 같은지 다른지 )만 가능합니다.
• 기본키는 등가비교만 해도 충분한 경우가 많으므로, 해시 인덱스를 고려해볼 수 있습니다.
• 풀 텍스트 인덱스 ( Full Text Index ) - 참고
• "ㅇㅇ"단어를 포함한 행을 검색하고 싶을 때 사용합니다.
• B+트리는 LIKE 검색으로 중간일치, 후방일치 검색을 할 수 없지만, 전문검색 인덱스 방법으로는 가능합니다.
• 형태 분석법, N 그램을 통해 단어를 구분합니다.
• R 트리 인덱스 ( 공간 인덱스 ) - 참고
• 최소 경계 사각형( MBR, Minimum Bounding Rectangle )이라는 개념을 사용해 인덱스를 구성합니다.
• MBR이란 어떤 도형을 둘러싼 최소의 직사각형을 의미합니다.
• 2차원의 데이터를 인덱싱하고 검색하려는 목적으로 사용되며, GPS( 위도, 경도 ) 같은 공간 검색에 활용됩니다.
• 그 밖에...
• 함수 인덱스
• 비트맵 인덱스

 

 

 

B+ 트리

많은 인덱스 알고리즘 중에 자세히 알아볼 인덱스는 B+트리 입니다.

 

RDB에서 인덱스는 일반적으로 B+트리 자료구조를 이용하여 검색을 수행하며,

B+ 트리는 다음과 같이 구성됩니다.

참고 : https://iq.opengenus.org/b-tree-search-insert-delete-operations/

• 실제 데이터가 저장된 리프노드( Leaf nodes )
• 리프노드까지의 경로 역할을 하는 논리프노드( Non-leaf nodes )
• 경로의 출발점이 되는 루트 노드( Root node )

B+트리는 리프노드에 이르기까지에 대한 자식 노드에 포인터가 저장되어 있습니다.

즉, B+트리의 검색은 루트노드에서 어떤 리프 노드에 이르는 한 개의 경로만 검색하면 되므로, 매우 효율적이다.

 

위와 같은 구조로 인해, B+ 트리 인덱스는 등가 비교는 물론 범위 검색에도 사용될 수 있습니다.

• 등가 비교
• WHERE key = 123
• 범위 검색
• WHERE key BETWEEN 100 AND 200
• LIKE 검색의 와일드카드는 전방 일치여야 인덱스 효과를 얻을 수 있습니다.
• WHERE key LIKE 'foo%'
• Leaf node에서 문자열이 사전 순서대로 정렬돼 있기 때문에 전방 일치가 아닌 LIKE 검색은 물리적으로 불가능합니다.

 

B+ 트리에 대해 더 자세히 알고 싶다면 아래의 링크를 추천합니다.

• https://www.javatpoint.com/b-plus-tree
• https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

 

 

 

 

3. 인덱스를 설계 한다는 것

인덱스가 늘어날수록 테이블을 갱신할 때 오버헤드가 커지고, 디스크 공간이 늘어나므로 최적의 인덱스를 찾는 것이 중요합니다.

 

인덱스를 설계 한다는 것은 어떤 컬럼을 조합해서 인덱스를 작성할 것인지,

즉 어떻게 컬럼을 조합해야 조회, 갱신의 모든 성능을 높일 수 있는지에 대한 논의입니다.

 

인덱스 설계는 응용프로그램에서 실행하는 쿼리에 대해 최적의 인덱스를 찾아내야 하는 것이므로, 최적의 인덱스 조합을 찾는 것은 오래 걸리는 어려운 작업이라고 할 수 있습니다.

 

단지, 다음과 같은 경우의 인덱스 설계는 피하는 것이 좋습니다.

• 모든 컬럼이 인덱스
• 인덱스에 포함된 컬럼이 한 개 밖에 없는 경우
• 0또는 1같은 값 밖에 없는 플래그 컬럼이 인덱스인 경우

 

 

 

이상으로 인덱스에 대해 알아보았습니다.

B+ 트리를 이해하면, 인덱스가 왜 빠른지에 대해 알 수 있습니다.

이번 기회를 통해 말로만 듣던 B+트리에 대해 알아보는 계기가 되었네요.