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

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

기본 데이터 타입

  - 크기 (size, 비트 수)

  - 해석 (부호 유무, 부동 소수점 수 여부, 문자 표현 여부, 포인터 표현 여부, 불리언 표현 여부)

배열

  - 인덱스 (아파트 호 수), 원소 (각각의 집)

비트맵

  - 비트맵: 비트의 배열

  - 마스크: 들여다볼 수 있는 구멍이 있는 비트 패턴

문자열

  - 문자열: 여러 문자로 이뤄진 시퀀스

    - 1) 문자열 안에 길이를 저장하기

    - 2) 문자열 터미네이터 사용

복합 데이터 타입

  - 구조체

  - 공용체

단일 연결 리스트

  - 연결 리스트: 목록에 들어갈 원소 개수를 모르는 경우 배열보다 효과적임

동적 메모리 할당

  - malloc을 이용해 가용 블록 리스트를 스캔하면서 두 가용 블록이 서로 인접한 경우

    둘을 합쳐서 더 큰 블록으로 만듦

더 효율적인 메모리 할당

  - 노드와 문자열을 동시에 할당

가비지 컬렉션

  - reference counting

이중 연결 리스트

  - 원소 삽입/삭제 시 전체 리스트 순회할 필요 없어짐

계층적인 데이터 구조

  - 2진 트리

  - 2진 트리 검색

대용량 저장장치

  - 디스크의 기본 단위는 블록, 클러스터는 연속적인 블록

  - 파일 이름

  - 아이노드: 디스크 블록에 대한 인덱스 + 노드

데이터베이스

  - B 트리 기반의 데이터베이스

인덱스

  - Primary Index

  - 데이터 변경 시마다 모든 인덱스를 갱신해야 하는 트레이드 오프가 있긴 하지만,

     데이터 변경보다 데이터 검색이 더 자주 일어나므로 괜찮음

데이터 이동

  - 루프 언롤링

벡터를 사용한 I/O

  - 분산/수집

객체 지향의 함정

  - 객체

    - 메서드

    - 프로퍼티

정렬

  - 퀵 정렬

해시

  - 해시 테이블

  - 해시 체인

효율성과 성능

  - 데이터베이스 샤딩 (수평 파티셔닝)

정리