Index 및 데이터 정렬 방법

데이터를 찾기 위해서 특정 행을 검색을 하게 되면 데이터를 순차적으로 검색을 하게 될 것이다. 

물론 이러한 방법이 문제가 있는것은 아니다. 데이터의 수가 적다면 말이다. 

 

만약 특정 행의 검색을 요청하면 컴퓨터는 그 특정행을 찾기 위해 모든 행을 전부 확인 할 것이다. 즉, 데이터 수가 많을수록 속도가 더 느려지게 될 것이다. 

 

1부터 100까지의 수 중에서 특정 수를 찾는다고 해보자. 이때 50이상인지, 이하인지를 살펴보듯이 절반씩 잘라가며 확인을 한다면 훨씬 더 빠른 속도로 값을 찾을 수 있을 것이다. 이를 이분탐색알고리즘이라하며 Blind SQL Injection에서 글자를 찾기 위한 방법으로 사용되었었다. 

 

이 방법의 전제조건은 '정렬'이 되어있어야 한다는 것이다. 따라서 이를 위해 정렬을 시킨 또 다른 행을 만들고, 그 값마다 행을 찾을 수 있는 값을 추가적으로 할당해주어야 한다. 이때 정렬해놓은 컬럼 사본을 인덱스라고 한다. 

 

Index는 검색이 수월하며 빠르다. 다만 장점만 있는것이 아니다. 단점은 컬럼을 복사해 정렬한 새로운 컬럼이 필요하다는 것이다. 즉, 더 많은 용량을 차지하게 된다. 또한 기존 데이터의 삽입, 수정을 하게된다면 인덱스 또한 수정이 필요하다. 따라서 삽입, 수정의 경우 성능적으로는 오히려 더 하락하게 된다. 

 

Primary key로 설정된 컬럼의 경우 자동으로 정렬이 되어있다. 따라서 굳이 새로 인덱스를 만들 필요가 없으며 이를 클러스터드 인덱스라고 부른다.

 

 

 

일반적으로 정렬을 할 때 사용하는 형태로 Array나 Linked List 방식이 있다. 하지만 실제로 데이터베이스에서 사용하는 정렬 방식은 Tree형식이다. 데이터를 전부 정렬을 하는것이 아닌 데이터를 그저 화살표로 연결만 해놓은 것이다. 이렇게 해도 아까와 같은 이분탐색이 가능하다. 따라서 명칭은 Binary Search Tree라 한다.

 

이보다 더 개선된 성능의 Tree또한 있다. 만약 노드마다 값을 두세개씩 넣게 된다면 값을 반으로 나누는 것이 아닌 1/3, 1/4씩 하며 값을 찾을 수 있다. 이는 B-Tree이다. 이렇게 되면 위의 방법보다 더많은 값을 같은 이동만으로 찾을 수 있다.

 

B-tree보다 더 개선된 B+Tree 방법이 있다. 이 방법은 최 하단 노드에만 값을 저장해둔다. 그리고 중간 노드는 특정 조건만을 저장해두게 된다. 마지막으로 맨 아래 노드끼리도 화살표로 구분해두게 된다. 이 방법의 장점은 범위검색이 쉽다. 즉, 조건으로 특정 값의 범위만을 찾고 그 범위 내에서 검색을 하게 된다.