인덱스

인덱스?

데이터베이스에 빠른 접근을 위해 생성한 자료구조

B트리가 나오기전의 인덱스의 문제점

메모리상에선 상관없었지만 하드디스크등의 보조 기억장치에서 대량의 데이터에 대해 검색을 할때 랜덤탐색을 통한 오버헤드가 발생한다.

인덱스에 사용하는 자료구조

• 해시테이블: 조회 및 수정 속도가 빠를수 있음,해시충돌시 성능 저하, 범위 탐색에 취약,
• b-tree: 균형 트리, 단일 개체 검색속도에 이점
• b+tree: 균형 트리, 리프노트에만 데이터와 래퍼런스가 같이 있어 저장공간 절약, 리프노트끼리는 연결리스트로 연결되어있어 범위검색시 선형탐색을 사용하여 강점이 있음

데이터베이스에 이진탐색쿼리가 부적합한 이유들은?

• 데이터들이 물리적으로 정렬되어있지 않을수 있다. 따라서 메모리상에서의 이진탐색은 효율적이지만, 하드디스크상에서의 이진탐색은 sequential 탐색이 아닌 수많은 random access를 발생시킬수 있다. (페이지화된 이진트리로 보완가능하나 단편화 문제가 있다)

• AVL 트리로 밸런스를 해결할수 있지만, 수정-삭제-추가 시에 밸런스검사 및 리밸런싱으로 인한 부하가 있다.

• 페이지화된 이진트리로 노드들을 메모리상의 페이지단위로 묶어둘수 있지만, balance가 깨질 위험이 크다.

• 페이지화된 이진 트리에서는 페이지(page) 단위로 데이터를 관리한다. 페이지의 크기가 작거나 데이터의 크기가 큰 경우, 하나의 페이지에 모든 데이터가 들어갈 수 없어 여러 개의 페이지가 필요하게 된다. 이로 인해 데이터의 일부만 페이지에 저장되는 경우가 발생하고, 이로 인해 페이지 내 데이터의 정렬 순서와 트리의 구조 사이에 불일치가 생길 수 있다.

• 이진트리는 노드의 갯수가 2개로 제한되어 있어 다단계 인덱싱과 궁합이 좋지 않다.

클러스터, 넌클러스터 인덱스

키와 실제 데이터가 같이 공존하는 인덱스를 클러스터 인덱스, 키와 클러스터디 인덱스의 키가 공존하는 인덱스를 넌클러스터 인덱스라고 한다. 클러스터드 인덱스는 일반적으로 한개이며 생성비용이 크지만 키와 데이터가 같이 붙어있어 탐색속도가 빠른 장점이있다. mysql 엔진중 myisam의 경우 클러스터 인덱스에는 키와 myisam에 발급한 데이터를 참조하는 키가 들어있어서 넌클러스터드 인덱스의 구분이없다.

커버링 인덱스

인덱스에 사용된 키를 이용해서만 쿼리를 진행하는 컨셉이다. 넌클러스터드 인덱스는 클러스터드 인덱스를 거쳐 데이터에 접근하니 오버헤드가 있고, 불필요한 데이터에 접근하기위해 시간복잡도와 공간복잡도를 까먹을수 있으니, 인덱스에 사용된 키를 이용해서만 쿼리를 하면 효율적이다.