데이터 구조와 처리

개요

머리에 남아있진 않지만 메모리 시스템의 특성을 배웠으니, 이를 생각하면서 데이터를 효율적으로 다루기 위한 데이터 구조에 대해 알아보자

기본 데이터 타입

• 프로그래밍 언어는 int, double, char 같은 다양한 기본 데이터 타입을 제공한다.
• 포인터는 크기가 컴퓨터 아키텍처에 따라 결정되는 부호가 없는 정수로, 메모리 주소다.
• 일부 언어는 잘못된 포인터 사용을 방지하기 위해 참조라는 개념을 사용하기도 한다.

배열

• 배열은 연속된 인덱스를 가지는 데이터 구조로 각 인덱스(호수)에는 원소(집)가 있다.
• 일반적으로 프로그래밍 언어에서는 배열은 같은 타입의 원소만 저장한다.
• 0번 원소의 주소를 기저 주소라고 한다.
• 기저 주소로부터 얼마나 멀리 떨어져 있는지를 오프셋으로 지정할 수 있다.
• 배열의 차원이 늘어남에 따라서 선, 면, 입체 등을 표현할 수 있다.
• 다차원 배열에서는 같은 차원의 데이터부터 순서대로 읽어야 참조 지역성을 효율적으로 활용할 수 있다.

  // 한 층에 집이 3개인 5층 아파트
  int[][] apart = new int[5][3];
  
  // 참조 지역성이 좋지 못한 경우
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 5; j++) {
      int x = apart[j][i];
    }
  }
  
  // 참조 지역성이 좋은 경우
  for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 3; j++) {
      int x = apart[ㅑ][ㅓ];
    }
  }
  

비트맵

• 표현하려는 데이터가 너무 큰 경우 사용할 수 있는 비트의 배열이다.
• 비트맵의 기본 연산은 비트를 1로 만드는 set, 비트를 0으로 만드는 clear, 비트가 1인지 검사, 비트가 0인지 검사하는 네 가지 연산이 존재한다.
• 8비트 바이트 5개에서 17번 비트를 찾고 싶다면, 17을 8로 나누면 2번째 바이트에 17번 비트가 있다는 것을 알 수 있다.
• 비트 위치를 찾았으니, 2번째 바이트의 어디를 봐야 17번 비트가 있는지를 알 수 있는 마스크를 구해야 한다.
• 17(00010001) ADN 7(00000111) 연산을 통해 1(00000001)을 얻을 수 있다.
• 이 결과를 왼쪽 시프트해서 00000010을 얻을 수 있고, 해당 값이 마스크다.
• 비트 설정 : 인덱스 OR 마스크
• 비트 삭제 : 인덱스 AND (NOT 마스크)
• 비트 검사 : 비트 AND 마스크 != 0 혹은 비트 AND 마스크 == 0

문자열

• 여러 문자로 이뤄진 시퀀스
• 문자열 안에 길이를 저장하기 위해 첫 번째 바이트에 문자열 길이를 넣을 수 있다.
• 하지만 이 방법을 사용하면 문자열 길이가 255자로 제한된다.
• C에서는 문자열 타입을 제공하지 않고, 1차원 바이트 배열을 사용하고, 길이를 저장하지 않는다.
• 대신 문자 배열에 있는 문자열 데이터의 끝에 문자열 터미네이터 바이트를 하나 추가한다.
• 즉, 문자열 길이가 6이라도 실제로는 끝에 NUL을 추가해 7바이트를 사용한다.

복합 데이터 타입

• 원하는 데이터를 묶어서 관리할 수 있는 사용자 정의 타입으로 구조체라고 한다.
• 구조체 안에 있는 각 데이터들을 멤버라고 한다.
• 자바로 따지면 클래스 타입과 같다.
• 프로그래밍 언어는 프로그래머가 지정한 멤버 순서를 지키지만, 메모리 정렬도 지켜야한다.
• 까먹어서 다시 찾아봤는데 CPU는 데이터를 특정 크기(4바이트, 8바이트 등)로 읽고 쓰는 것이 빠르다.
• 그래서 패딩을 추가해 데이터가 경계에 걸치는 것을 방지한다.
• 모든 멤버 변수가 동일한 메모리 공간을 공유하는 공용체라는 것이 있다.
• 한 번에 하나의 멤버 변수만 값을 가질 수 있다.

단일 연결 리스트

• 구조체를 사용해 연결 리스트를 만들 수 있다.
• 각 구조체는 다음 데이터를 가리키는 포인터와 자신의 데이터를 갖는다.
• 리스트의 맨 처음은 헤드, 마지막은 테일이다.
• 배열과는 다르게 메모리에서 연속적으로 위치하지 않고 흩어져 있다.
• 원소 추가 및 삽입은 새로운 데이터 구조체를 추가하고, 새로운 구조체는 다음 구조체를 가리키고, 이전 구조체는 새로운 구조체를 가리키게 바꾸면 된다.
• 삭제는 삭제 대상 이전의 구조체가 삭제 대상 다음 구조체를 가리키게 바꿔주면 된다.

동적 메모리 할당

• 배열 등의 변수가 사용하는 메모리는 정적이라 할당된 주소가 바뀌지 않는다.
• 리스트의 노드와 같은 존재는 동적이라 필요에 따라 생기고 사라진다.
• 이런 동적 대상에 사용할 메모리는 힙 영역에서 얻는다.
• 힙 영역은 런타임 라이브러리가 설정한다.
• 프로그램은 힙을 관리할 수 있어야 하고, C에서는 이를 위해 malloc과 free 함수를 제공한다.
• 프로그램이 메모리를 요청하면 malloc이 충분한 크기의 블록을 찾아 포인터를 돌려준다.
• 프로그램이 free로 메모리를 해제하면 메모리가 다시 연결 리스트에 추가된다.

더 효율적인 메모리 할당

• malloc 부가 비용을 줄이기 위해 노드와 문자열을 동시에 할당할 수도 있다.
• (노드 + 문자열 + 패딩) 만큼의 크기의 공간을 할당한다.
• 이러면 free도 한 번만 호출하면 된다.

가비지 컬렉션

• 자바나 자바스크립트 같은 경우는 malloc이나 free를 사용하지 않고도 동적 메모리 할당을 지원한다.
• 자바는 포인터를 추상화한 참조를 사용하고, 이는 실제 메모리 주소를 노출하지 않는다.
• new 연산자는 데이터 요소를 만들면서 메모리도 할당한다.
• 언어의 런타임 환경이 변수 사용을 추적해 사용하지 않는 메모리를 자동으로 해제한다.
• 프로그래머는 가비지 컬렉션 시스템을 제어할 수 없다.

이중 연결 리스트

• 단일 연결 리스트는 삭제를 위해 이전 원소를 찾아야해서 느렸다.
• 이중 연결 리스트는 메모리를 더 사용해 노드에 이전 원소에 대한 포인터도 저장한다.
• 공간/시간의 트레이드 오프를 통해 단일 연결 리스트의 단점을 해결했다.
• 리스트의 순회 없이 노드 삭제와 삽입이 가능해졌다.

계층적인 데이터 구조

• 선형적인 데이터 구조만으로도 데이터를 저장하는 것은 충분하지만 조회도 효율적이게 하고 싶다면 계층적인 데이터 구조를 사용할 수도 있다.
• 트리 같은 경우가 대표적인 계층적인 데이터 구조다.
• 트리는 계층의 수만큼만 탐색을 진행한다.
• 그래서 균형 잡힌 상태를 유지해야 탐색 횟수가 줄어든다.

대용량 저장장치

• 디스크의 기본 단위는 블록이고, 연속적인 블록을 클러스터라고 한다.
• 데이터는 사용 가능한 섹터가 있으면 위치와 관계없이 저장된다.
• 운영체제의 장치 드라이버에 의해 데이터가 연속적으로 저장된 것처럼 보일 뿐이다.
• 블록 중 일부를 아이노드로 따로 지정한다.
• 아이노드 = 디스크 블록의 인덱스와 노드(파일 정보)
• 아이노드에는 직접 블록, 간접 블록 포인터가 존재한다.
• 직접 블록 포인터는 보통 12개가 있고, 이를 통해 최대 49,152 바이트를 저장할 수 있다.
• 파일이 더 큰 경우에는 간접 블록을 사용해 4MiB를 저장할 수 있다.
• 더 큰 파일을 저장해야 하면 2중, 3중 간접 블록을 통해 4GiB ~ 4Pib까지 저장할 수 있다.
• 디렉터리는 다른 디렉터리를 참조할 수 있고, 이를 통해 트리 구조의 계층적 파일 시스템이 생겼다.
• 같은 블록을 여러 아이노드가 참조할 수 있다. (참조를 링크라고도 한다.)
• 디렉터리에 링크를 하는 것은 심볼릭 링크라고 한다.
• 심볼릭 링크를 허용하면 파일 시스템 그래프에 사이클이 생겨 무한 루프를 감지해야 한다.
• 가용 공간 추적 방법은 각 블록을 1비트로 표현하는 비트맵을 사용할 수 있다.
• 비트맵 방법은 전체 디스크의 0.01% 정도의 공간을 필요로 한다.
• 파일 시스템 그래프와 비트맵 사이 동기화가 깨질 수 있는 문제가 있다.
• 파일 시스템 그래프를 조회하며 가용 블록 데이터와 비교해주는 fsck도 있다.
• 최근에는 저널링 파일 시스템이 널리 사용되고 있다.

데이터베이스

• 데이터베이스는 균현 2진 트리와 비교해 공간은 덜 효율적이지만 성능이 더 좋은 B 트리를 사용한다.
• 디스크에 데이터를 저장할 때 균형 2진 트리보다 훨씬 성능이 좋다.
• B 트리 노드는 디스크 블록 하나를 정확히 꽉 채울 수 있는만큼 자식을 가진다.
• 내부 노드가 균형이 잡혀 있어 검색 시간을 미리 예측할 수 있다.
• 사용할 수 있는 자식 링크가 없으면 각 노드의 담당 범위를 조정해 쉽게 균형을 맞출 수 있다.
• 디스크에서 데이터를 읽을 때는 한 블록을 통째로 읽어오기 때문에 이러한 방법을 사용할 수 있다.

인덱스

• 정렬된 데이터는 효율적으로 접근할 수 있다.
• 인덱스는 필요한 데이터에 맞게 추가해 정렬을 유지할 수 있다.
• 대신 데이터가 바뀔 때마다 모든 인덱스를 갱신해야 한다.

데이터 이동

• 루프 언롤링 : 반복을 확장해 한 번에 더 많은 처리를 하게 만드는 기법으로 반복문의 제어 흐름 오버헤드를 줄일 수 있다.
• 더프의 장치 : 루프 언롤링과 스위치문을 결합한 기법으로 반복문의 실행 횟수를 더 줄일 수 있다.

벡터를 사용한 I/O

• 크기와 포인터로 이뤄진 벡터를 운영체제에 넘기는 방식이다.
• 운영체제는 벡터에 저장된 데이터를 사용해 순서대로 오디오 프레임을 조합한다.
• 벡터를 활용해 여러 위치에서 데이터를 모아서 쓰는 작업을 수집이라 부른다.
• 데이터를 읽는 행위는 여러 위치로 데이터를 분산시켜 분산이라 부른다.
• 패킷 통신 방식과 비슷하다.

객체 지향의 함정

• 객체는 메서드와 프로퍼티가 들어 있다.
• 정수값 등 크기가 작은 데이터를 저장하는 프로퍼티는 객체 구조체 안에 들어간다.
• 메모리 할당이 더 필요한 프로퍼티는 포인터를 통해 참조된다.
• 구조체가 너무 커지면 메서드를 별도의 구조체에 나눠 담을 수도 있다. (시간/공간 트레이드 오프)
• 객체는 전역적으로 알려진 함수 대신 자신이 사용할 메서드에 대한 포인터를 가지고 다녀야만 한다.

정렬

• 정렬 대상이 포인터 크기보다 크면 데이터를 직접 정렬하지 않고, 포인터를 재배열해서 정렬해야 한다.
• 큰 데이터가 움직이는 것은 비효율적이기 때문이다.

해시

• 검색에 사용할 키에 대해 해시 함수를 적용해서 균일하게 퍼뜨린다.
• 저장장치에 데이터를 저장하는 방식 중 해시 함수의 결과를 배열 인덱스로 활용하는 해시 테이블 방식이 있다.
• 해시 함수의 값이 같은 경우가 발생하는 것을 해시 충돌이라고 한다.
• 해시 체인을 사용해 이러한 충돌을 해결할 수 있다.

효율성과 성능

• 샤딩(수평 파티셔닝) : 데이터베이스를 각각 다른 기계에서 실행되는 여러 샤드로 나누는 방식이다.
• 하나의 요청에 해당하는 데이터베이스 연산을 모든 샤드에 전달하고, 컨트롤러가 결과를 하나로 모은다.
• 하나의 작업을 여러 작업자로 나누어 병렬 처리 할 수 있기 때문에 성능이 향상된다.
• 맵리듀스 : 입력 데이터를 분할해 각 조각을 독립적으로 처리 후, 각 조각을 맵 함수에 전달해 중간 결과를 생성하고, 출력 데이터를 정렬해 파티셔닝 후 리듀스 함수로 전달해, 리듀스 함수가 데이터를 집계해 최종 결과를 도출한다.

소감

이게 책이지…