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

어떻게 해야 프로그램에서 데이터를 잘 구성하고 처리할까

서론

• 데이터 구조(data structure): 데이터를 조직화하는 표준적 방법
• 참조 지역성(locality of reference): 필요한 데이터를 메모리에서 서로 근처에 유지하고, 금방 사용할 데이터는 더 가까운 곳에 저장하는 것

기본 데이터 타입

• 프로그래밍 언어는 기본 데이터 타입(primitive data type)을 제공
• 두 가지 측면
  • 크기(size): 비트 수
  • 해석(interpretation): 부호 유무, 문자나 포인터 아니면 불리언을 나타내는지 여부

포인터

• 컴퓨터 아키텍처에 따라 결정되는 크기의 부호가 없는 정수
• 정숫값이 아닌 메모리 주소로 해석
• 값이 0, 즉 NULL은 일반적으로 주소로 인정하지 않음
• 일반적으로 컴퓨터의 워드 크기와 같은 경우가 많음
  • 한 사이클 안에 컴퓨터 내의 대상에 접근하기 위함

배열

• 일반적인 컴퓨터 개발 규정(프로그래밍 언어 문법)에서 배열 원소의 타입은 모두 같아야 한다고 규정
• 상대 주소 지정으로 보는 배열도 가능
  • 기저 주소(base address), 즉 0번째 원소의 주소로부터 떨어져 있는 정도(offset)로 지정

참조 지역성(locality of reference)

• 다른 행, 같은 열 순서로 탐색하는 것보다 같은 행, 다른 열 순서로 탐색하는 것이 지역성이 더 좋다.
• 열 인덱스가 바뀌는 것보다 행 인덱스가 바뀔 때 더 많은 이동 발생
  • 열 인덱스가 바뀌면 인접한 메모리 위치로 이동하지만 행 인덱스가 바뀌면 열 개수만큼 이동해야 하기 때문

비트맵

• 비트맵(bitmap): 비트의 배열
• 수행할 수 있는 기본 연산
  • 비트 설정하기(set): 1로 만들기
    • (원하는 인덱스의 비트) = (원하는 인덱스의 비트) OR 마스크
  • 비트 지우기(clear): 0으로 만들기
    • (원하는 인덱스의 비트) = (원하는 인덱스의 비트) AND (NOT 마스크)
  • 비트가 1인지 검사하기
    • (원하는 인덱스의 비트) AND 마스크 ≠ 0
  • 비트가 0인지 검사하기
    • (원하는 인덱스의 비트) AND 마스크 = 0

문자열

• 문자열(string): 여러 문자로 이뤄진 시퀀스
• 문자열은 길이를 알아야 하지만 가변(길이가 변하는) 문자열 데이터의 경우 어렵다.

문자열의 길이를 알아내는 방법

1. 문자열 안에 길이를 저장
   1. 길이가 255자로 제한된다는 단점 존재
   2. 어느 순간 길이를 저장하기 위한 바이트 수가 문자열 길이를 넘어가는 경우 발생
   3. 문자열은 바이트라서 메모리 정렬(alignment)가 달라지는데 길이를 저장하려면 이 정보는 반드시 올바른 메모리 정렬 경계에 있어야 함
2. C는 문자열 전용 데이터 타입을 제공하지 않고, 1차원 바이트 배열을 사용
   1. 문자 배열에 들어 있는 문자열 데이터 끝에 바이트를 하나 추가하고 여기에 NUL을 넣음
      1. NUL: 0, 문자열 터미네이터, 문자열 끝을 표시하는 문자
      2. 대부분의 기계는 주어진 값이 0인지 검사하는 명령어가 있기 때문에 NUL을 사용하는 게 효율적
   2. 저장이 쉽고 부가 비용이 들지 않다는 장점 존재
   3. 문자열 길이를 알기 위해 문자열 터미네이터를 발견할 때까지 문자 수를 세야 한다는 단점 존재
   4. 문자열 중간에 NUL 문자를 넣을 수 없다는 단점 존재

복합 데이터 타입

• 구조체(structure): 원하는 대로 데이터 타입을 만드는 방법
  • 멤버(member): 구조체 안의 원소
• 편의 문법(syntactic sugar): 프로그램을 문법적으로 더 알기 쉽고 이해하기 편하도록 표현하는 비필수적인 요소
• 패딩(padding): 멤버 순서와 메모리 정렬을 지키기 위해 추가하는 바이트
• 공용체(union)
  • 구조체 안의 모든 멤버는 각기 다른 메모리를 차지하지만 공용체의 멤버는 메모리를 공유 가능

단일 연결 리스트

• 연결 리스트(linked list): 목록에 들어갈 원소 개수를 모르는 경우 배열보다 효율적인 구조
  • 구조체를 사용해 만들 수 있다.
• 배열과의 차이
  • 배열의 각 원소는 메모리에서 연속적으로 위치하지만 리스트 원소는 아무 데나 위치할 수 있음
  • 리스트는 원소를 쉽게 추가할 수 있음

동적 메모리 할당

• 정적으로 할당된 데이터 영역 다음에 프로그램 런타임 라이브러리가 설정해주는 힙 영역 존재
  • 메모리 관리 유닛(MMU)이 없다면 이 힙 영역이 프로그램이 쓸 수 있는 모든 데이터 메모리
  • MMU가 있다면 런타임 라이브러리가 프로그램에 필요한 메모리를 운영체제에 요청
  • 프로그램의 브레이크: 프로그램이 사용할 수 있는 메모리의 끝
• 배열 등의 변수가 사용하는 메모리는 정적이며 할당된 주소는 바뀌지 않음
• 리스트 노드와 같은 구조가 사용하는 메모리는 동적이므로 힙 사용

더 효율적인 메모리 할당

• 문자열이 들어있는 연결 리스트의 경우 노드에 문자열을 가리키는 포인터를 포함하는 것보다 노드와 문자열을 동시에 함께 할당하면 더 효율적이다.

가비지 컬렉션

• 가비지 컬렉션(garbage collection): 자바와 자바스크립트에서 동적 메모리 할당을 위해서 사용하는 방법
  • 자바와 자바스크립트는 포인터가 없다.
• 단점
  • 프로그래머가 가비지 컬렉션 제어 불가
  • 불필요한 참조가 남는 경우 빈번

이중 연결 리스트

• 단일 연결 리스트에서 원소를 지우려면 그 앞 원소를 찾아야 해 매우 느리다.
• 이중 연결 리스트는 노드에 다음 원소와 이전 원소에 대한 포인터도 넣어 비용이 늘어나지만, 원소 삭제를 빠르게 할 수 있다.
  • 즉 리스트 전체를 방문하지 않아도 원하는 위치에 노드를 추가하거나 삭제할 수 있다.

계층적인 데이터 구조

• 배열, 연결 리스트는 모두 선형적인 데이터 구조이다.

2진 트리

• 노드가 최대 2개의 다른 노드와 연결 가능
• 트리는 단일 연결 리스트처럼 쭉 늘어선 모습이 아닌 균형 잡힌 모습을 유지해야 효율적
• 연결 리스트에서는 원소를 검색할 때 n번 비교해야 하지만 균형 잡힌 트리에서는 log n번만 하면 된다.
  • 트리의 균형을 맞추는 데 시간이 좀 걸리지만 log n이 n보다 훨씬 작기 때문에 괜찮다.

대용량 저장장치

• 블록: 디스크의 기본 단위
• 클러스터: 연속적인 블록

문제

데이터를 한 클러스터에 저장하기엔 무리가 있으므로, 고정된 크기의 블록을 여럿 확보해 데이터를 이 블록에 나눠 담아야 한다.

연결 리스트를 사용한다면?

순회에 시간이 너무 오래 걸리기 때문에 사용할 수 있는 디스크 블록, 이미 사용 중인 디스크 블록을 탐색하는데 적절하지 못하다.

파일 이름의 필요성

• 디스크의 데이터는 장기적으로 저장되기에 데이터를 읽기 위한 영구적인 존재, 즉 파일 이름이 필요
• 파일 이름을 사용하기 위해 다음이 필요하며 이를 아이노드가 처리한다.
  • 파일 이름을 디스크에 저장
  • 파일 이름과 파일의 데이터가 저장된 디스크 블록을 연결

아이노드(inode)란

• 유닉스(UNIX)에서 개발
  • 인덱스(index) + 노드(node), 즉 아이노드는 인덱스 노드
• 디스크 블록 중 일부를 아이노드로 지정해 사용
• 파일에 대한 정보를 갖는다.
  • 파일의 데이터가 들어 있는 블록에 대한 인덱스
  • 파일 이름, 파일 소유자, 파일 크기, 파일에 대한 허가 내역 등

아이노드의 직접 블록과 간접 블록

• 직접 블록
  • 보통 직접 블록 포인터가 12개 존재
    • 실제로는 포인터가 아니라 블록의 인덱스이다.
  • 직접 블록을 통해 데이터를 4096*12=49152바이트까지 보관 가능하다.
• 간접 블록
  • 파일이 크면 사용
  • 32비트 인덱스를 사용하면 한 블록에 4바이트짜리 인덱스가 1024개 존재하므로 최대 4MiB까지 지원
    • 한 블록은 4KiB이다.
  • 더 큰 파일에 대해서는 2중 간접 블록을 통해 4GiB, 3중 간접 블록을 통해 4PiB까지 지원 가능

아이노드와 디렉터리

• 아이노드 정보 중에는 블록에 데이터가 있는지 디렉터리 정보가 있는지에 대한 표시도 포함
• 디렉터리: 파일 이름과 파일 데이터를 가리키는 아이노드를 연결
  • 여러 파일 유형 중 하나이므로 디렉터리는 다른 디렉터리 참고 가능 ⇒ 트리 구조의 계층적 파일 시스템 탄생
• 심볼릭 링크: 디렉터리에 대해 링크
  • 링크: 아이노드가 블록을 참조하는 것
  • 심볼릭 링크를 허용하면 파일 시스템 그래프에 루프가 생길 수 있으므로 무한 루프를 감지하기 위한 코드 필요

가용 공간(free space) 추적

• 비트맵 방식
  • 각 블록을 1비트로 표현해서 가용 공간을 나타내는 방식
  • 간단하면서 효율적이다.
    • 1은 사용 중인 블록, 0은 사용 가능한 블록을 가리킨다면 모든 비트가 1이 아닌 워드를 탐색
  • 파일 시스템 그래프와 비트맵 사이 동기화가 깨질 수 있음
    • 디스크에 데이터를 기록하는 도중 전원이 나갈 수 있음

데이터베이스

• 트리는 크기가 작은 경향이 있어 디스크 섹터에 잘 들어맞지 않는다.
• 데이터베이스: 정해진 방식으로 조직화한 데이터 모음
• 데이터베이스 관리 시스템(DBMS): 데이터베이스에 정보를 저장하고 읽어올 수 있게 해주는 프로그램
  • 일반적으로 맨 아래의 데이터 저장 메커니즘을 감싼 여러 계층의 인터페이스로 구성

B 트리

• 데이터베이스가 일반적으로 이용하는 데이터 구조
• 균형 트리
  • 균형 2진 트리보다 공간 효율성은 떨어지지만 성능이 더 낫다.
• 가지의 수는 디스크 블록 하나를 정확히 채울 수 있는 숫자로 결정

인덱스

• 하나의 인덱스로 구성된 노드를 주 인덱스(primary index), 여럿인 경우 다중 인덱스라 한다.
• 인덱스는 데이터가 바뀔 때마다 갱신되어야 한다.
  • 데이터 변경보다 검색을 더 많이 하므로 감당할만한 손해이다.

데이터 이동

프로그램은 한 지점에서 다른 지점으로 데이터를 이동시킬 때 많은 시간이 들기 때문에 이를 효율적으로 처리해야 한다. 메모리 블록을 0으로 설정하는 과정을 가정하자.

• 루프 언롤링(loop unrolling): 인덱스를 유지하고 길이를 갱신하기 위한 시간을 최소화하는 방법
  • 메모리를 0으로 만드는데 더 많은 시간을 쓸 수 있다.
• 더프의 장치(Duff’s Device): 루프를 여덟 번 펼치고 남은 바이트 수에 따라 적당한 위치부터 펼친 루프의 단계를 시작하는 방법
  • 메모리를 0으로 설정하는 시간이 더 개선됨
  • 여덟 번은 최대한의 성능을 위해 설정된 횟수

벡터를 이용한 I/O

• 데이터의 효율적인 복사는 시스템 성능에 중요

방법

1. 크기와 데이터에 대한 포인터로 이루어진 벡터를 운영체제에 넘김
2. 운영체제는 벡터에 저장된 데이터를 이용해 순서대로 조합

• 수집(gathering): 벡터를 활용해 데이터를 쓰는 행위
  • 여러 위치에서 데이터를 모아서 쓴다는 의미
• 분산(scattering): 벡터를 사용해 데이터를 읽는 행위
  • 여러 위치로 데이터를 분산시킨다는 의미

객체 지향의 함정

• 객체에는 메서드(함수)와 프로퍼티(데이터)가 있다.
• 객체는 전역적으로 알려진 함수 대신 메서드에 대한 포인터를 가지고 다녀야 한다.
  • 따라서 객체 내의 데이터가 데이터만 저장하는 데이터 구조처럼 꽉 짜여 있지 않다.
• 성능이 중요할 때는 전통적인 배열을 활용하는 것이 낫다.

정렬

• 정렬 대상이 포인터 크기보다 크다면 데이터를 가리키는 포인터를 정렬해야 한다.
  • 데이터 자체가 움직이지 않도록 해야 한다.
• 정렬은 어떤 수가 다른 수보다 큰지, 같은지, 작은지에 따라 결정된다.

해시

• 일반적으로 검색에 사용할 키에 대해 이들을 균일하게 분포시키는 해시 함수를 적용한다.
  • 키에 대응하는 메모리를 해시 함수의 결괏값을 이용해 저장한다.
  • 해시 함수의 결괏값은 메모리 크기보다 작으면서 데이터를 적당히 분산시켜야 한다.
• 해시 테이블: 해시 함수의 결과를 배열 인덱스로 활용하는 방법
  • 이때 배열의 각 원소를 버킷이라 한다.
• 충돌(collision): 해시 함수 값이 같아 같은 버킷에 데이터가 들어가는 경우
  • 해시 체인 등의 방법으로 해결할 수 있다.
    • 해시 체인: 충돌이 일어나면 버킷에 들어가려는 데이터들을 체인과 같이 연결해서 버킷에 추가한다.
• 완전 해시: 각 키를 유일한 버킷에 연결하는 해시 함수

효율성과 성능

• 데이터베이스 샤딩(sharding): 데이터베이스를 각각 다른 기계에서 실행되는 여러 샤드로 나누는 방식
  • 수평 파티셔닝이라고도 한다.
  • 인터페이스를 통해 요청이 들어온 데이터베이스 연산을 모든 샤드에 전달하고, 컨트롤러가 결과를 하나로 모은다.
  • 작업을 여러 작업자가 병렬적으로 수행하기에 성능이 향상된다.