[프로그래밍 일반] 한 권으로 읽는 컴퓨터 구조와 프로그래밍_ch7 데이터 구조와 처리

 

 

 

- 기본데이터 타입

프로그래밍 언어는 다양한 기본 데이터 타입 (primitive data type)을 제공한다.
이런 타입에는 크기size, 해석interpretation 두가지 측면이 존재한다.

- 배열

프로그래밍 언어는 배열(array)를 지원한다.
모든 배열 [] 에는 원소elements와 그 원소의 위치index가 존재한다

각 원소는 0번째 element의 주소 기저주소(base address)로 부터 얼마나 멀리 떨어져 있는지에 따라 계산한다.
다차원(multi dimentional)인 배열도 만들수있다. 

- 비트맵

기본 데이터 타입을 사용해 배열을 만들 수 있지만,
데이터를 표시하기에는 기본 데이터가 너무 클때도 있다
그럴 때는 비트들의 배열인 비트맵을 활용하는 것이 효율적이다.

비트맵에 대하 수행할 수 있는 기본연산은
비트설정하기
비트지우기
비트가 1인지 검사하기
비트가 0인지 검사하기이다.

- 문자열

여러문자로 이뤄진 시퀀스를 문자열이라고 한다.

- 복합 데이터 타입

간단한 물건을 저장할 때는 단순한 공간으로 충분하지만,
복잡한 물건을 저장하는 방법이 필요하다면
구조체를 활용할 수 있다.
구조체는 여러 멤버로 구성된다.

- 단일 연결 리스트

배열은 물건 목록을 유지하는 가장 효율적인 방법이다.
하지만 데이터 양이 정해져있지 않은 경우에는 배열이 비효율적이다.
데이터가 늘어날때 새로 더 큰 배열을 만들고 기존 배열의 내용을 복사해야하기 때문이다.
필요이상으로 배열 크기를 크게 잡아놓으면 메모리 낭비가 심해진다

연결 리스트는 목록에 들어갈 원소 개수를 모르는 경우
배열보다 더 잘 작동한다.

리스트 맨 앞은 헤드, 마지막은 테일이다. 보통 null포인터로 다음원소가 리스트원소가 아님을 표현한다.

- 동적 메모리 할당

연결 리스트에서 새 노드를 위한 메모리를 얻는 방법은
동적 메모리 할당이다.

배열 등의 변수가 사용하는 메모리는 정적static이다.
이런 변수에 할당된 주소는 바뀌지 않는다.

반면에 리스트 노드와 같은 존재는 동적이다.
필요에 따라 생기기도하고 사라지기도 한다.

C언어의 경우, 처음에는 전체 힙이 한 블록으로 존재한다.
프로그램이 메모리를 요청하면 malloc함수로 충분한 크기의 블록을 찾아서 
요청 받은 공간에 대한 포인터를 돌려주고,
프로그램에게 할당한 메모리를 반영해 블록의 크기와 링크를 조정한다.
프로그램이 free함수로 메모리를 해제하면 메모리가 다시 연결 리스트에 추가된다.
시간이 지남에 따라 메모리 공간은 파편화된다.

 

- 가비지 컬렉션

자바나 자바스크립트의 경우 malloc이나 free함수를 사용하지 않고 
가비지 컬렉션을 활용해 프로그래머가 제어하지 않고 동적메모리 할당을 지원한다.

자바같은 언어는 포인터 대신 참조를 사용한다.
포인터를 추상화해서 거의 비슷한 기능을 제공하지만 실제 메모리 주소를 노출하지는 않는다.

- 이중 연결 리스트

단일 연결 리스트의 delete는 상당히 느리다
경우에 따라 아주 긴 리스트를 순회해야 할 수도 있다.

이중연결리스트는 다음 원소에 대한 포인터뿐만 아니라
이전 원소에 대한 포인터도 들어있는 리스트이다.
이로인해 노드당 부가 비용은 2배가 되지만,
delete시 노드를 앞에서부터 방문할 필요가 없어진다.

- 계층적인 데이터구조

앞에서는 선형적인 데이터구조를 살펴봤다.
데이터를 효율적으로 찾고 싶은 경우,
선형적인 구조는 단점이 많다.

이를 보완하기 위한 계층적인 데이터 구조는
노드에 들어갈 수 있는 포인터 수에 제한이 없기 때문에,
원하는 대로 데이터를 조직할 수 있다.
가장 간단한 계층적 데이터 구조는 2진트리이다.

- 대용량 저장장치

디스크의 기본 단위는 블록이고, 연속적인 블록을 클러스터라 부른다.
클러스터는 한 트랙 안에 있는 연속적인 섹터로 이뤄지지만,
현실적으로 대부분의 경우 사용 가능한 섹터가 있다면 위치와 관계없이 저장된다.

데이터를 디스크에 저장하기 위해서는 포인터가 아닌 파일 이름을 사용한다.
파일이름과 데이터가 저장된 디스크 블록을 연결하여 저장된다.
블록 중 일부를 아이노드(index + node)로 따로 지정한다.
아이노드는 인덱스노드로, 파일이름, 파일 소유자, 파일크기, 파일에 대한 허가 내역등 파일정보들이 저장된다.
아이노드 정보 중에는 블록에 데이터가 있는지 디렉터리 정보가 있는지를 표시하는 것도 있다.
이로인해 트리구조의 계층적 파일 시스템이 가능하다.

- 데이터 베이스

2진트리는 데이터를 메모리에 저장할 때는 훌륭한 방법이지만,
메모리 안에 들어갈 수 없을 정도로 커다란 데이터를 저장할 때는 잘 작동하지 않는다.
데이터베이스는 정해진 방식으로 조직화된 데이터 모음이다.
DBMS는 보통 맨 아래 데이터 저장 메커니즘을 감싼 여러 계층의 인터페이스로 구성된다.

데이터베이스는 B트리라는 데이터 구조를 활용한 시스템이다
B트리는 2진 트리노드보다 더 많은 가지가 있따.
내부 노드는 균형이 잡혀있어 검색 시간을 미리 예측할 수 있다.

- 인덱스

데이터에 접근을 위해 별도로 조직화된 노드를 활용하면 효율적이다.
이를 인덱스라 한다. 
다만, 인덱스의 경우 유지보수를 해야한다는 트레이드 오프가 있다.

 

-  해시

데이터 구조를 순회하며 비교를 여러번 수행하지 않고,
해싱으로 보다 효율적으로 데이터에 접근할 수 있다.

해시함수의 결과를 배열 인덱스로 활용하는 방법이 있다.
이런 배열을 해시 테이블이라고 한다.

해시함수는 계산하기 쉽고 키를 골고루 버킷(해시테이블의 각 원소)에 뿌려줘야한다.
동일한 버킷에 값이 들어가는 경우 충돌이 일어난다.
충돌이 일어나는 경우, 단일 연결 리스트를 활용한 해시 체인으로 해결할 수 있다.

- 효율성과 성능

성능과 효율이 분리된 상황을 응용하는 방법으로 샤딩이 있다.
샤딩은 수평 파티셔닝으로,
인터페이스를 통해  요청된 데이터베이스 연산을
모든 샤드에 전달(분산)한 후 컨트롤러가 결과를 하나로 모아 처리한다.
하나의 요청에 대해 여러 작업자가 동시에 병렬적으로 작업을 수행할 수 있어
성능이 향상된다.

샤딩의 변종으로 맵리듀스가 있다.
컨트롤러가 중간 결과를 모으는 방법을 코드로 직접 작성할 수 있게 해준다.