[자료구조] 인덱스와 파일구조

공부용으로 작성되는 페이지입니다. 틀린 부분이나 환경에 따라 오류가 발생할 수 있습니다. 

 

---

 

 

인덱스

데이터베이스의 테이블에 대한 검색 속도를 향상시켜주는 자료구조이다. 

인덱스를 관리하기 위한 추가 작업과 저장공간이 필요하기 때문에 잘못 사용할 경우 성능저하가 발생할 수 있다. 

 

데이터베이스는 말그대로 데이터가 저장되어있는 집합체이다. 어떤 단체나 회사냐에 따라 데이터베이스의 내용물은 다르다.

유저가 Query(질의)를 전달하면 DataBase에서 해당하는 데이터를 찾아서 유저에게 전달해주는데

이 때 인덱스가 데이터마다 고유의 주소값(pointer)를 저장하고 기억해 데이터를 찾기 더 수월하게 만들어준다. 

 

인덱스를 구성하기 위한 자료구조로는 B-Tree, B+Tree, Hash Table 가 있다.

 

(1) B-Tree : 탐색 성능을 높이기 위해 균형 있게 높이를 유지하는 검색 트리

 

 

(2) B + Tree : B Tree에서 확장된 트리로, Leaf 노드를 제외하고는 데이터를 저장하지 않는 트리 

 

 

(3) Hash Table : Key를 찾으면 Hash()을 통해 Value를 찾을 수 있는 구조이다

 

파일구조 

보조기억장치에 파일을 구성하는 데이터들을 저장하는 방식을 말한다.

 

(1) 순차 파일(Sequential File) : 데이터를 물리적 연속 공간에 순차적으로 기록하는 방식

 

연속적인 공간에 저장하므로 메모리 효율이 높고 가장 간단하여 어떤 매체에서도 사용이 용이하지만

삽입/삭제 시 전체를 복사하므로 시간이 많이 소요되고 순차 검색때문에 검색 효율 및 응답 시간이 낮다 

 

(2) 직접 파일(Direct File) : 데이터를 특정 순서 없이 해시함수를 활용하여 물리적 저장공간에 임의로 기록하는 방식

 

접근 시간이 빠르고 삽입,삭제 갱신이 용이하고 어떤 데이터라도 평균 접근 시간내 검색이 가능하다는 장점을 지니지만

데이터 주소 변환을 위한 메모리 효율 저하가 필연적이며 기억자치의 물리적 구조를 알아야해서 프로그래밍이 복잡하다.

 

(3) 색인 순차 파일(Indexed Sequential File) : 데이터를 Key 값 순으로 sort(정렬)시켜 기록하고 Index로 편성하는 방식

 

• 기본 구역(prime Area) : 실제 데이터가 기록되는 구역
• 색인 구역 (Index Area) : 기본 구역을 찾아가기 위한 Index로 구성 (Track Index < Cylinder Index < Master Index)
• 오버플로우 구역 (Overflow Area) : 기본 구역에 빈 공간이 없어 새로운 데이터 삽입이 불가할 때를 대비한 공간 

순차처리와 랜덤처리가 모두 가능하여 융통성 있는 활용이 가능하다.

당연하게도 색인 구역과 오버플로우 구역이 존재하기 때문에 이에 따른 추가 기억공간을 필요로 한다.

 

 

참고자료

https://youtu.be/QgXQVxlwS8o?si=BZdpBgkAWyPa4SpT