7장. 데이터베이스, 인덱스, 데이터 이동, 벡터를 사용한 I/O

한 권으로 읽는 컴퓨터 구조와 프로그래밍을 읽고 스터디를 위해 정리한 글입니다.😀

 

데이터 베이스

• 데이터베이스(database) : 데이터 모음 (정해진 방식으로 조직화 됨)
• 데이터베이스 관리 시스템(database management system) : 데이터베이스에 정보를 저장하고 읽어올 수 있게 해주는 프로그램

데이터베이스는 B트리라는 데이터 구조를 활용한 시스템이다. (루돌프 바이어, 에드 맥크래이트가 개발함)

• B 트리 : 데이터를 정렬하여 탐색, 삽입, 삭제 및 순차 접근이 가능하도록 유지하는 트리형 자료구조이다.

(데이터를 쉽게 다룰 수 있게 하는 자료 구조의 일종이라고 보면 됨)

• B 트리 사용이유 : B 트리는 Balanced- Tree(균형 트리)의 일종으로 트리의 균형이 맞음

즉 트리내에서 삽입과 삭제가 일어나더라도 최대한 균형있는 트리 형태를 유지하여 이진 탐색의 장점을 살린 트리임.

만약 편향 트리라면?

• 편향 트리란 : 한 쪽 방향으로만 노드가 뻗어나가있는 트리 구조를 말함.

ex) 편향 트리 구조를 이용해서 데이터를 저장하고 검색을 하는 상황.

모든 노드를 하나하나 다 보면서 원하는 키 값을 찾는 검색을 하기 때문에 효율이 극히 떨어짐.

 

편향트리

 

하지만 균형이 갖춰진 트리라면 이진탐색으로 효율적임. B트리도 이러한 균형 트리의 일종이다.

 

B트리와 균형2진 트리 비교

• 디스크에서 데이터를 읽어올 때는 노드 한 개씩 읽어옴.
• B트리에서는 노드 한 개에 데이터가 많기 때문에 한 번에 많은 데이터를 읽어올 수 있다.
• 두개만 있던 균형 2진 트리보다 성능이 좋음.
• B트리 노드 안에 비어있는 데이터가 있을 수 있지만, 데이터를 많이 읽어올 수 있다는 점에서 균형 2진트리보다 성능이 더 나음.

 

인덱스

이름 인덱스로 조직화된 노드(B트리)이다.

인덱스가 하나인 경우 → 주 인덱스라고 부름

 

이름, 성으로 조직화된 노드(B트리)

인덱스가 여럿이면 다양한 방법으로 원하는 데이터를 효율적으로 검색할 수 있음. (일단 화살표부터 훨씬 많음 → 검색할 방법이 다양)

 

 

데이터가 바뀌면 모든 인덱스를 갱신해야함. 하지만 데이터 변경보다 데이터 검색이 더 자주 벌어지기 때문에, 인덱스 갱신은 감수할 만하다.

(인덱스가 갱신 될 일보다 인덱스로 검색 할일이 많음. 그래서 갱신에 신경쓰기보다 인덱스를 활용한다는 데 초점을 두는 것 같음)

데이터 이동

배열을 사용하려면 배열 크기를 증가시킬 필요가 있을 때마다 데이터를 복사해야 함.

프로그램은 데이터를 이동시키기위해서 많은 시간을 소비함.

그래서 이를 효율적으로 하는 것이 중요.

 

• 첫 번째 방법

 

목적을 위해서는 무조건 각 과정을 반복해야함.

• 두 번째 방법

 

각 과정을 모두 반복하지 않고 length 부분은 한 번만 처리.

• 세 번째 방법 (실제로 가장 일반적인 구현)

더프의 장치(Duff’s Device)

 

위와 비슷하게 모두 반복하지 않음.

각 과정을 반복해야했던 것보다 훨씬 효율적이다.

 

백터를 사용한 I/O

시스템 성능에 있어서 데이터를 효율적으로 복사하는 것이 중요함.(복사 시간이 너무 오래걸림)

그래서 아예 피할 수 있으면 성능을 더 올릴 수 있음.

MP3 파일은 여러개의 MP3 프레임으로 구성됨.

MP3 파일(프레임 + 프레임 + 프레임....)

 

MP3 프레임은 헤더(header)와 데이터로 구성된다.

MP3 프레임 배치 (헤더, CRC, 사이드 정보, 주 데이터, 부 데이터)

프레임을 만들어본다고 생각해보자.

프레임에 필요한 데이터들을 모두 복사해와서 프레임을 만든다.

그러나 이전에 말했던 것처럼 복사하면 시간이 너무 오래걸려서 성능이 떨어짐.

 

 

그래서 복사 xxx

프레임의 각 부분을 가리키는 주소값(포인터)을 정한다.

그리고 주소값들을 하나로 합쳐서 프레임으로 만들어준다. (이걸 백터라고 함)

그럼 필요할 때마다 주소값에 있는 거 불러오면 된다. (복사하는 시간이 없어져서 매우 효율적이게 됨)

백터를 사용해 데이터를 쓰는 행위 : 수집(gathering)

(여러 주소값에서 데이터를 모아 오므로)

백터를 사용해 데이터를 읽는 행위 : 분산(scattering)

(여러 주소값 찾아들어가서 데이터를 읽어오므로)

 

 

 

 

 

 

 

 

 

참고자료

[OS] 책 설명이 x같아서 내가 쉽게 쓴 B 트리

MPEG 1 Layer 3 (MP3) 정리