Sequential Access와 Random Access, 순차화일과 인덱스화일

Sequential Access와 Random Access

Sequential access와 Random access

 

메모리에서 특정 레코드를 찾기 위해 디스크에 접근할 때

레코드를 찾는 순서에 따라 디스크 접근 방식을 Sequential Access와 Random Access로 나눌 수 있다.

그림에서 알 수 있듯이 Sequential access는 데이터에 대해 저장된 순서대로 접근하는 방식을 의미하고

Random access는 데이터에 대해서 랜덤하게 접근하는 방식을 의미한다.

 

이러한 Access방식에 대해 실생활에서 은행을 예로 들어 생각해보자.

은행에는 많은 사람들이 방문한다.

방문하는 사람들은 계좌번호 순서대로 줄을 서서 입장하지 않는다.

무작위의 계좌번호를 가진 손님들이 Random Access 하는 방식이다.

 

이제 Sequential Access 방식을 생각해보자.

은행이 문을 닫고 은행원은 손님들의 계좌번호를 Sorting 한 상태에서 순서대로 볼 것이다. (아마도)

이 방식이 Sequential Access 방식이다.

 

즉 일상생활에서 데이터 레코드에 접근할 때 방식은

Sequential Access, Random Access 나뉘는 것이다.

이러한 Access 방식을 생가하며 화일의 구조를 만들어야 한다.

---

Sequential file과 Index file

화일은 크게 두가지 구조로 나뉜다.

sequential file과 Index file이다. 

순차화일과 색인 화일로 부르기도 하는데 이제

두 화일을 순차화일과 인덱스 화일로 칭한다.

 

화일 처리의 주된 목적은 메모리에서 디스크 Access를 줄여서 io시간을 줄이는 것이다.

https://dingcoding.tistory.com/318?category=1035429 

순차 화일과 마스터-트랜잭션 화일

 

위에서 설명한 두가지 Access 방법에 따라 

Sequential file과 Index file의 장단점이 구분된다.

 

결론부터 말하면 Sequential file은 Sequential Access에 유리하고

Index file은 Random Access에 유리하다.

이제 그 이유를 살펴보자

 

 

 

 

 

순차화일

순차 화일

순차화일은 데이터가 순차적으로 저장되어 있기 때문에

Sequential Access를 많이 할 경우 유리하다.

Blocking Factor(메모리에서 디스크의 블록을 읽는 단위)에 따라 데이터를 읽는 양은 다르겠지만,

 

Sequential Access를 할 때

5번 21번 학생의 데이터가 필요한 상황이라 가정해보자.

그리고 쉽게 설명하기 위해서 한 번의 디스크 Access를 할때 학생 3명의 데이터를 읽을 수 있다 가정하자.

 

그렇다면 순차적으로 5번, 21번, 105번의 데이터가 필요한 경우에는

5번 학생의 데이터를 읽기 위해 디스크 Access를 한 이후에

5번, 21번, 105번 데이터를 읽어온다 (학생 3명의 데이터를 읽어올 수 있다고 가정했으므로)

메모리에는 5번 21번의 데이터가 존재하기 때문에 21번 학생의 데이터를 얻기 위해서

다시 디스크에 접근할 필요가 없다.

 

즉 데이터를 순차적으로 요청할 때 순차화일의 경우에는 Disk Access를 적게 할 수 있다는 장점이 있다.

 

 

하지만 Random Access를 할 경우 비효율적이 된다.

이번에는 5번, 700번, 105번 데이터를 읽는다 생각해보자. (이번에도 한번의 Disk Access에 3명의 데이터를 읽어온다고 가정하자)

 

Disk Access 1회:

5번 데이터를 읽을 때

메모리 버퍼에는 5, 21, 105번이 저장된다.

 

Disk Access 2회:

메모리 버퍼에 700번 데이터가 없기 때문에

다시 디스크에 접근하고 700번, x, y 데이터를 읽어오게 된다.

 

Disk Access 3회:

메모리 버퍼에 105번 데이터가 없기 때문에

다시 디스크에 접근하고 데이터를 읽어오게 된다.

 

이 때 데이터를 찾을 때마다 순차화일에서 이진탐색을 해야한다.

디스크 위에서 이진탐색을 시행하기 때문에 여러번 디스크에 접근해야 하는 것이다.

하지만 이런식으로 데이터를 처리하면 cpu의 관점에서 너무 느려진다.

한번 디스크에 접근하는데 10ms 정도 소요되기 때문이다.

 

그리고 더불어 다른 문제점으로 순차화일은 데이터를 갱신할 때 비용이 많이 든다.

(그 이유는 위의 다른 게시물 링크에서 설명한다)

 

 

Random Access 할 때도 디스크 Access 를 줄이는 방법이 필요하다.

 

 

 

---

 

인덱스 화일

 

인덱스 화일

인덱스 화일에서는 순차화일과 달리 데이터를 key값에 따라 순서대로 저장하지 않는다.

데이터가 입력되면 입력되는 그 순서대로 기록할 뿐이다.

 

하지만 해당 학번이 디스크 어느 위치에 존재하는지 나타내주는

인덱스 테이블을 메인 메모리에 두고 사용한다.

이럴 경우 메인 메모리에서 원하는 key(학번)을 찾아서 바로 디스크에 접근할 수 있다.

 

인덱스를 메인메모리에 저장할 수 있는 이유는

단순 인덱스 테이블을 메인 메모리에 저장하는 데에는 많은 용량이 필요하지 않기 때문에 가능하다.

 

그리고 추후 설명하겠지만 실제로 인덱스 테이블은 배열구조가 아닌

트리 구조로 이루어진다.

 

트리 자료구조로 인덱스 구조를 만들어 메모리에 저장하고 디스크에 접근해야 하는 일이 생기면

메모리 내의 인덱스에서 key값을 찾아 접근해야 하는 디스크의 주소를 알아내고 디스크에는 한 번 Access 하게 되는 것이다.

 

순차화일 처럼 키값을 찾기 위해 이진탐색을 하는 것은 동일하지만

순차화일은 디스크 상에서 이진탐색을 해야하는데

인덱스 화일은 메모리 상에서 이진탐색을 진행하기 때문에 

인덱스 화일이 Random Access를 할 때 유리하다.

 

 

하지만 인덱스화일은 Sequential Access를 할 때 불리하다.

순차화일은 데이터가 순차적으로 저장되어 있는 걸 읽어오기 때문에

순차적으로 데이터를 요청할 때 Disk Access를 적게 할 수 있는데 비해

인덱스화일은 실제 데이터가 무작위로 섞여 있기 때문에

순차적인 데이터 요청이 오더라도 계속 Disk Access를 하여 데이터를 읽어와야 할 것이다.

 

 

 

---

 

이처럼 순차 화일과 인덱스 화일은

Disk Access 방식에 따라 장단점이 존재한다.

하지만 이러한 두 화일의 장점을 살려 만든 B+ 트리 구조의 화일도 존재한다.