인덱스

해시 인덱스

- 범위질의에는 사용하면 안된다.(나이 < 30 인 레코드를 찾아라)

- 동등질의에만 사용해야 한다.(이름 = "홍길동" 인 레코드를 찾아라)

해시 인덱스는 키값을 해시하여 고정길이의 아웃풋으로 만든다. 그리고 같은 아웃풋이 같은것들을 상자에 모은다.

-> 이렇게 하면 나중에 그 키값에 해당하는 레코드를 찾을때 바로 찾을 수 있다.

이렇게 되면 이름="홍길동"과 같은 동등질의에서는 해쉬함수 적용 한번에 바로 데이터레코드를 찾을 수 있으므로 굉장히 빠르다.

B+ Tree 인덱스

- 범위질의에 강하다.

- 동등질의에도 나쁘지 않다.

leaf 노드를 데이터 엔트리라고 부르며, 그 외의 노드들은 인덱스 엔트리라고 불린다.

데이터 엔트리는 <key,rid> 쌍으로 이루어져 있으며 rid는 record id의 약자이며, 실제 데이터 레코드의 주소를 갖고 있다.

데이터 레코드는 디스크에 있는 실제 데이터를 의미하고, 데이터 엔트리는 인덱스에 존재하는 하나의 노드라는 차이점을 혼동하지말자.

인덱스 엔트리는 <key,다음노드의포인터>로 구성되어 있다.

B+ tree의 leaf 노드들은 서로 연결되어 있으며, 정렬되어 있다. 그렇기 때문에 B+ tree인덱스를 구축하게 되면 범위 질의에 강한것이다. B+ tree는 기본적으로 이진탐색트리와 유사하지만, 여기서는 이진이 아니라 더 많이 가지가 뻗어 나간다.

(얼마나 가지가 뻗는가를 영어로 Fan out이라고 한다.)

B+ tree를 구성하는 방법은 총 3가지가 있다.(leaf노드를 어떻게 구성하느냐에 따라 달라짐)

1. leaf노드 = <key,data record>

2. leaf노드 = <key,rid>

3. leaf노드 = <key,list of rid>

이런식으로 leaf노드를 어떤식으로 구성하느냐에 따라 B+ tree를 세가지 다른 방식으로 구현 할 수 있다.

우선 첫번째 방식은 leaf노드에 데이터 레코드가 직접 들어가 있다. 원래 인덱스라는것은, 실제 데이터 레코드가 어디에 위치했는지 포인터를 기록하기 위해서 존재하는 파일인데, 

1번 방식의 B+ tree는 인덱스에 실제 데이터 레코드를 직접 저장해버린다. 이렇게 되면 인덱스 파일만 뒤져도 내가 원하는 레코드를 바로 가져 올 수 있다.

2번 방식의 B+ tree는 우리가 생각하는 보편적인 인덱스이다. leaf 노드인 데이터 엔트리에 rid는 record id의 약자이다. 즉, 

<key,rid> 중에서 key값에 해당하는 레코드가 실제 디스크에 어디에 저장되어있는지 포인터를 저장하고 있는것이 rid이다.

그렇기 때문에 rid를 따라가면 데이터 레코드중에서 내가 원하는 레코드를 바로 가져올수 있게 된다.

3번 방식의 B+ tree는 key값에 해당하는 데이터 레코드가 여러개 존재할때 사용한다. 예를들어 나이라는 필드에 대해서 B+ B+ tree인덱스를 3번방법으로 구축하는 경우를 생각해보자. 나이라는것은 사실 여러 사람이 동일한 값을 가질 수 있기 때문에 여러개의 중복 데이터가 존재한다. 그 여러개의 중복 데이터를 모두 가리켜야 인덱스가 제대로 동작하는것일텐데, 그렇게 하기 위해서 3번 방식을 사용하는것이다. 예를들어 나이가 30이라는 레코드가 10번,20,30,40번 주소 총 4개의 주소에 존재한다고 할때 이 <30,list of rid>값을 갖는 B+ tree의 leaf노드는 사실 <30,{10,20,30,40}> 이런식으로 값을 갖고 있는것이다. 따라서 B+ tree를 3번 방식으로 구축하게 되는 경우 나이가 30인 레코드를 모두 불러올수 있게 된다.

B-Tree와 B+Tree

B-Tree가 B+ Tree와 다른점은 인덱스 엔트리가 <key,다음 노드의 포인터>로 구성되어 있는게 아니라, 마치 B+ tree의 leaf 노드처럼<key,rid>값으로 구성되어 있다. 즉, 트리 전부가 <key,rid>로 구성되어 있다.

이렇게 했을때 단점은, 범위 질의에서 나타난다. B+ Tree의 경우 leaf노드에 모든 데이터 엔트리가 밀집해 있기 때문에, 범위질의를 할때 연결된 leaf노드를 탐색하게되면 금방 내가 원하는 데이터 레코드를 가져올수 있었다.

하지만 B-Tree에서는 내가 원하는 어떤 범위에 해당하는(나이 < 30) 레코드의 주소를 탐색하기 위해서 부모노드와 자식노드, 형제노드를 모두 이리저리 옮겨다니면서 확인해야 되는 불편함이 존재한다. 이렇게 되면 검색 속도도 당연히 더 오래걸릴것이다.

그렇기 때문에 요즘엔 B+Tree가 인덱스 구축에 대세가 된것이다.

멀티 칼럼 인덱스

멀티 칼럼 인덱스란, 키값이 하나의 필드로 구성되어 있는게 아니라 여러개의 필드로 구성되어 있다는 것이다.

위에서 <key,rid>로 데이터엔트리가 구성된다고 했었는데 여기서 key는 1개의 속성이었다(예를들면, 나이필드) 근데, 나이 필드 뿐만아니라 성별필드도 같이 묶어서 인덱스를 구축할수 있다는 것이다.

이렇게 멀티 칼럼 인덱스를 구축해 놓으면 다음과 같은 질의에 이 인덱스가 도움이 될 수 있다.

나이 < 30 AND 성별 = "남자"

B+ Tree의 leaf노드에는 우선 나이를 기준으로 정렬되어있을것이고, 나이가 같다면 성별을 기준으로 한번더 정렬 되어 있을것이다. 그렇기 때문에 위와 같은 질의에 이 인덱스가 도움이 된다.

Index Only Plan

어떤 질의에 대한 결과를 내놓을때 인덱스를 활용하게 되는데, 인덱스의 데이터 레코드인<key,rid>에서 데이터 파일에 있는 rid에 해당하는 값을 가져오는 2단계 접근 방식을 통해 값을 가져왔었다.

근데 Index Only Plan이라는것은 어떤 질의에 대한 결과를 데이터 레코드까지 가지 않고 인덱스만 뒤져봄으로써 내줄수 있다는것이다.

예를들어 가격에 대해서 B+ Tree인덱스가 구축되어 있을때 다음과 같은 질의가 들어오면,

가격 < 10000 인 레코드의 개수를 찾아라.

B+ Tree의 리프노드에 가격으로 정렬된 레코드만 뒤져봄으로써 레코드가 몇개 존재하는지 알 수 있다.