자료구조

데이터를 어떤 모양으로 담을지를 다루는 구역입니다. 같은 데이터라도 담는 모양을 바꾸면 넣고 꺼내는 데 드는 비용이 달라집니다. 그래서 이 구역에서는 모양마다 무엇이 싸지고 무엇이 비싸지는지를 견줍니다. 이 구역 안에 무엇이 있느냐는 물음의 답은 한 문장이 아니라 목록으로 열립니다.

쉽고 빠른 이해

담을 그릇의 모양을 고르는 구역입니다. 회원 백만 명을 번호순으로 한 줄에 늘어놓을지, 아이디로 칸을 계산해 던져 넣을지가 여기서 갈립니다.

모양을 안 고르면 무엇을 묻든 처음부터 끝까지 훑어야 합니다. 자주 할 물음을 싸게 만들려고 미리 모양을 정해 두는 것입니다.

무엇을 하나:

담을 데이터와 그 데이터에 물을 것을 정합니다
그 물음이 싸지는 모양을 고릅니다
고른 모양이 망가지지 않게 넣고 빼는 절차를 함께 씁니다

대가도 있습니다. 한 물음을 싸게 만들면 다른 물음이 비싸집니다. 칸을 계산해 던져 넣으면 아이디로 찾기는 빨라지지만 「가장 작은 값」을 묻기는 어려워집니다.

상세

이 구역의 물음은 하나입니다. 데이터를 어떤 모양으로 담을지입니다.

NIST(National Institute of Standards and Technology, 미국 국립표준기술연구소)가 유지하는 알고리즘·자료구조 사전은 자료구조를 정보의 조직이라고 정의합니다. 대개 메모리 안에 둔다고 적습니다. 알고리즘 효율을 더 낫게 하려고 조직한다고 덧붙입니다. 사람의 이름과 주소처럼 개념적으로 하나로 묶으려고 조직하는 경우도 같은 정의가 함께 적습니다.

정의 안에 이미 이웃 구역이 들어와 있습니다. 알고리즘은 답을 어떻게 낼지, 곧 이름 붙은 계산 절차와 그 비용을 다루는 구역입니다. 앞의 사전은 대부분의 자료구조가 탐색·삽입·균형 맞추기 같은 연산을 수행하는 절차를 딸려 가진다고 덧붙입니다. 그 절차가 자료구조의 성질을 유지한다고 적습니다.

그래서 이 구역에서 모양을 고르는 일은 비용을 고르는 일이기도 합니다. 담을 모양을 고르면 그 위에서 도는 절차가 정해지고, 그 절차의 비용이 따라서 정해집니다.

flowchart TD
    A[담을 모양을 고른다] --> B[그 위에서 도는 절차가 정해진다]
    B --> C[절차의 비용이 정해진다]

이 구역에서 무엇을 마주치는지는 학부 컴퓨터과학 학위 과정 교육과정 지침인 Computer Science Curricula 2013 이 목록으로 적어 둡니다. 배열과 레코드와 문자열과 연결 리스트가 거기 있습니다. 추상 자료형과 그 구현이라는 토픽 아래에 스택·큐·우선순위 큐·집합·맵을 둡니다. 참조와 별칭도 같은 토픽 목록에 있습니다.

같은 지침은 이 구역의 학습 성과를 셋 적습니다. 자료구조의 서로 다른 구현을 성능 면에서 견주는 것이 하나입니다. 동적 구현과 정적 구현의 비용과 이득을 견주는 것이 둘입니다. 주어진 문제를 모델링할 자료구조를 고르는 것이 셋입니다. 셋 모두 고르는 일을 말합니다.

모양이 비용을 바꾼다는 것은 같은 지침의 또 다른 학습 성과에도 적혀 있습니다. 트리의 균형이 여러 이진 탐색 트리 연산의 효율에 어떻게 영향을 주는지 설명하는 것이 그 하나입니다. 균형이 무너진 트리와 잡힌 트리는 담긴 값이 같아도 찾는 비용이 다릅니다.

비용을 재는 자는 이웃 구역과 같은 것을 씁니다. 앞의 사전은 빅오 표기법을 알고리즘 실행에 대한 이론적 척도라고 정의합니다. 문제 크기 n 이 주어졌을 때 대개 필요한 시간이나 메모리를 잰다고 적습니다. n 은 대개 항목의 개수라고 덧붙입니다. 이 자를 어떻게 쓰고 어떤 갈래가 있는지는 알고리즘 구역이 다룹니다.

경계

데이터베이스 인덱스에 쓰이는 B-tree 는 이 구역인가, 데이터베이스 구역인가. 담는 모양과 그 모양이 만드는 접근 비용을 따지는 동안은 이 구역입니다. 동시 접근과 잠금, 기록 순서가 붙는 순간 데이터베이스 구역입니다.

한쪽 근거는 이 구역의 사전이 이 자료구조를 어떻게 정의했느냐입니다. 앞의 사전은 B-tree 를 노드마다 자식 수의 아래위 한계를 정해 둔 균형 탐색 트리로 정의합니다. 그 한계를 정하는 정수를 차수라고 부릅니다. 트리의 상당 부분이 느린 메모리, 곧 디스크에 놓이는 경우를 같은 항목이 함께 짚습니다. 그 경우 차수를 크게 잡아 높이를, 따라서 접근 횟수를 하나나 둘까지 작게 유지할 수 있다고 적습니다. 정의에 들어간 것은 모양과 접근 횟수, 그리고 트리가 어느 메모리에 놓이느냐까지입니다.

Bayer 와 McCreight 의 원 논문도 더 멀리 가지 않습니다. 색인을 디스크나 드럼 같은 유사 임의 접근 보조 저장 장치에 두어야 한다고 가정한다고 적습니다. 그 위에서 색인 크기에 대해 키의 조회·삽입·삭제를 로그에 비례하는 시간에 할 수 있게 하는 색인 조직을 제시한다고 적습니다. 로그의 밑은 장치에 따라 정해지는 자연수라고 적습니다. 그 값에서 이 방식의 성능이 최적에 가까워진다고 덧붙입니다.

다른 쪽 근거는 실제 데이터베이스가 같은 이름 아래 무엇을 적어 두었느냐입니다. PostgreSQL 의 nbtree 접근 방식 README 는 자기가 Lehman 과 Yao 의 고동시성 B-tree 관리 알고리즘을 구현한 것이라고 적습니다. 고전적인 B-tree 와 견주어 각 페이지에 오른쪽 형제 페이지를 가리키는 링크를 더한다고 적습니다. 그 페이지에 놓일 수 있는 키의 상한인 하이 키도 더한다고 적습니다. 이 둘이 동시 페이지 분할을 감지할 수 있게 만든다고 적습니다. 그래서 읽기 잠금 없이 트리를 탐색할 수 있다고 적습니다. 같은 문서는 포스팅 리스트 분할에 필요한 WAL(Write-Ahead Logging, 미리 쓰기 로그)의 양을 줄이는 이야기도 함께 합니다. 동시 분할 감지와 잠금과 기록량은 모양과 접근 횟수의 이야기가 아닙니다.

선을 긋는 근거는 데이터베이스 쪽이 자기 범위를 스스로 적은 대목입니다. Computer Science Curricula 2013 의 정보 관리 지식영역은 데이터베이스 시스템의 구성 요소와 핵심 기능 설계를 자기 토픽으로 적습니다. 질의 메커니즘, 트랜잭션 관리, 버퍼 관리, 접근 방식을 예로 듭니다. 같은 지침은 알고리즘과 복잡도와 정보 관리를 18개 지식영역 안의 서로 다른 칸으로 세워 둡니다.

이견

이 구역 안의 것을 무엇이라 부르는지가 문서마다 갈립니다.

스택과 큐를 무엇이라 부르는지가 첫 갈림입니다. 앞의 사전은 추상 자료형을 어떤 구현과도 무관하게 정밀히 명세된 데이터 값과 연산의 집합이라고 정의합니다. 그리고 사전·스택·큐·우선순위 큐·집합·백을 추상 자료형의 종류로 적습니다. Computer Science Curricula 2013 의 소프트웨어 개발 기초 지식영역도 같은 선을 긋습니다. 추상 자료형과 그 구현이라는 토픽 아래에 스택·큐·우선순위 큐·집합·맵을 두고, 배열·레코드·문자열·연결 리스트는 그 바깥에 따로 둡니다.

같은 것을 부르는 낱말 자체도 문서마다 다릅니다. C++ 표준 작업 초안의 컨테이너 라이브러리 절은 자기가 기술하는 것을 C++ 프로그램이 정보의 모음을 조직하는 데 쓸 수 있는 구성 요소라고 적습니다. 그리고 기본 시퀀스 컨테이너 종류로부터 스택이나 큐 같은 추상 자료형을 손쉽게 구성하게 해 주는 컨테이너 어댑터를 함께 제공한다고 적습니다. 이 문서에서 스택과 큐는 컨테이너가 아니라 컨테이너 위에 세우는 추상 자료형입니다.

세 번째 낱말은 Java SE(Standard Edition, 표준 에디션) 21 의 공식 문서에 있습니다. 그 API(Application Programming Interface, 응용 프로그램 인터페이스) 문서는 같은 것을 컬렉션이라 부릅니다. Collection 을 컬렉션 계통의 최상위 인터페이스로 적습니다. 컬렉션이 원소라 불리는 객체의 무리를 나타낸다고 적습니다. 어떤 컬렉션은 중복 원소를 허용하고 어떤 컬렉션은 허용하지 않는다고 적습니다. 순서가 있는 컬렉션과 순서가 없는 컬렉션도 나란히 적습니다. Python 3 공식 튜토리얼은 아예 장 제목을 자료구조로 답니다. 리스트를 스택으로 쓰는 법과 큐로 쓰는 법을 그 장 안의 절로 둡니다.

상세

경계

이견

관련 항목

데이터를 담는 모양

이것을 가리키는 다른 이름

해시테이블을 이루는 부품

그래프·트리를 담을 때 갈리는 선택

담는 모양 위에서 도는 절차

담는 모양의 값을 재는 지표

이것과 경계를 나누는 데이터베이스 개념

커리큘럼에서 이웃하는 다른 지식영역

이것을 정의하거나 구현한 문서·언어