12. 데이터베이스 순차접근(Full Table Scan)과 인덱스(Index)

1. 순차접근(Full Table Scan)

 데이터베이스의 한 릴레이션에서 데이터를 찾거나 재배열하기 위해 데이터가 저장된 목록 중의 모든 데이터 요소를 차례차례 조사하여 원하는 것을 찾아내는 것을 순차접근(Full Table Scan)이라 합니다. 이런 순차 접근에 의한 검색은 튜플의 수가 많아지면 검색 시간이 매우 오래걸린다는 단점이 있습니다. 만일 데이터가 오름차순 또는 내림차순으로 정렬되어 있다면, 이진 탐색을 통하여 검색시간을 줄일 수 있겠지만, 데이터들이 지속적인 변화를 통해 삽입,삭제,갱신 작업이 일어나므로 항상 오름차운이나 내림차순으로 유지하기에는 현실성이 떨어집니다.

---

 2. 인덱스(Index)

 1) 인덱스 정의, 인덱스의 장단점

 스캔기법의 단점을 보완하기 위해 등장한 것이 인덱스입니다. 인덱스는 데이터의 주소를 기억하고 관리하는 인덱스 파일(Index File)과 실제 데이터를 기억하는 데이터 파일(Data File)로 구성되어 있습니다. 데이터를 검색 시, 먼저 인덱스 파일에서 찾고자하는 데이터가 저장된 주소를 찾고 그 뒤 찾은 주소값을 통해 데이터 파일에서 데이터를 찾습니다. 이 인덱스 기법은 수많은 데이터 중에서 원하는 자료를 빠르게 검색할 수 있도록 해줍니다.

 하지만 인덱스는 저장공간을 차지하는 문제와 함께, 항상 정렬상태를 유지해야하기 때문에 튜플의 값이 변경되거나 수정, 삭제가 되면 인덱스도 재정렬을 해야합니다. 그래서 인덱스를 많이 사용한다면, 인덱스의 재정렬에서 많은 시간이 소요되어 DBMS의 성능을 저하하는 단점이 있습니다. 그래서 인덱스는 필요한 속성에만 사용해야합니다. 여기서 중복값을 허용하지 않는 인덱스를 고유 인덱스라고 부르는데, 이는 가장 좋은 선택성을 가집니다.

※ 선택성(=분포도, Selectivity): 전체 행의 수 분에 해당 값

 인덱스 기법은 여러가지 구조로 형성되는데 그 구조 중에선 B―트리와 B+―트리, 클러스터드 인덱스, 넌클러스터드 인덱스가 있습니다.

[예시]

[데이터 파일]

주소값	제품코드	제품명	분류	가격
100	AA01	탁자	가구	700,000
200	AA02	나무옷장	가구	400,000
300	AA03	침대	가구	1,100,000
400	BA01	50인치 TV	가전	900,000
500	BA02	전기밥솥	가전	250,000
600	BA03	냉장고	가전	1,500,000

제품의 정보들을 저장하는 데이터 파일이 있고, 왼쪽에 각 값에 해당하는 주소값이 배정되어 있다고 가정해봅니다. 이 데이터베이스의 인덱스 파일을 작성하면 아래와 같습니다.

 

[인덱스 파일]

제품코드	주소
AA01	100
AA02	200
AA03	300
BA01	400
BA02	500
BA03	600

이렇게 작성된 인덱스 파일을 통해 자료를 검색할 수 있습니다. 만일 제품코드 'BA01'이란 값의 데이터를 찾으려고 한다면, 먼저 인덱스 파일을 통해 해당 값이 저장된 물리적 주소인 '400'을 찾습니다. 그 뒤 데이터 파일에서 400주소값을 가지는 항목을 바로 찾아가 원하는 데이터를 찾을 수 있습니다. 만일 순차접근방식을 통해 검색한다면 AA01부터 BA01까지 모두 검색하여 더 많은 시간이 소요될것입니다.

 

---

 

 

 

2) 인덱스의 종류

- B―트리(Balanced Tree)

 자료 구조를 균형있는 트리구조로 나타내어 검색의 효율을 증진시키는 방법입니다. 트리의 한 노드는 다음과 같이 구성됩니다.

여기서 P1은 data1보다 작은 값을 가지는 하위 노드의 주소를 가리키며, P2는 마찬가지로 data2보다 작은 값을 가지는 하위 노드의 주소를, P3는 data3보다 작은 값을 가지는 하위노드의 주소를 가리킵니다.

[예시]

여기서 연파란색의 배경이 있는 된 표의 셀은 주소값을, 배경이 투명한 표의 셀은 데이터를 나타냅니다. 

---

- B+―트리

B 트리의 변형으로 단말 노드를 찾기 위한 인덱스 세트와, 단말 노드로만 구성된 순차 세트로 구성되어 있습니다.

[예시]

 

---

- 클러스티드 인덱스(Clustered Index)

 

테이블에서 하나의 속성을 기준으로 정렬시켜 재구성한뒤, 그 테이블을 토대로 인덱스를 만드는 방법입니다. 그래서 테이블의 물리적 순서와 인덱스의 순서가 동일하게 됩니다.

 

- 넌클러스티드 인덱스(Non Clustered Index)

 테이블을 재구성하지 않고, 데이터 주소를 이용하여 인덱스를 만든 뒤 주소값을 이용하여 검색하는 방법입니다.