전통적인 Data Structure vs AI 시대 비교 & 다양한 데이터 표현 방식
전통적인 전산학 자료구조가 CPU 상의 포인터 조작과 정확한 값 탐색(Exact Search)에 최적화되었다면, AI·LLM 시대의 자료구조는 GPU Tensor Core의 대규모 행렬 곱셈과 고차원 벡터 공간에서의 의미적 근접성(Semantic Similarity)을 극대화하는 방향으로 진화했습니다. 놀라운 점은 이 과정에서 고전의 Trie(접두사 트리), Graph, Block Paging 같은 핵심 자료구조가 LLM 엔진 심장부에서 더 정교하게 부활하고 있다는 사실입니다.
전통적인 Data Structure
- 선형 구조 (Array · Linked List · Stack · Queue): 연속 메모리 또는 포인터 연결을 통한 순차/FIFO/LIFO 접근
- 탐색 트리 (Binary Tree · B+Tree · Trie · Heap): 정렬된 키 기반
O(log N)범위 검색과 DB 인덱싱 - 해시 & 관계 (Hash Table · Adjacency List): 정확한 키 일치(
O(1)) 조회 및 이산 경로 탐색 - 목표: CPU 캐시 적중률 및 결정론적 정확 검색·정렬 최적화
AI 시대의 Data Structure
- 다차원 텐서 (Tensors · Strided / 2:4 Sparse): GPU VRAM 연속 배치 및 행렬 타일링에 맞춘 다차원 숫자 배열
- 시맨틱 벡터 & HNSW 그래프: B+트리가 무너지는 1,536차원+ 임베딩을 다층 근접 그래프(HNSW)로 고속 탐색
- Paged KV Cache & Radix Trie: LLM 추론 상태를 비연속 블록 테이블과 접두사 트리로 관리해 재계산 제거
- 목표: GPU 메모리 대역폭 극대화 + 의미 기반 근사 검색(ANN)
| 비교 기준 | 전통적인 자료구조 | AI · LLM 시대의 자료구조 |
|---|---|---|
| 데이터 형태 | 정수 · 문자열 · 구조체 레코드 (이산 기호) | 고차원 부동소수/양자화 텐서 · 임베딩 벡터 (연속 수치) |
| 검색 목표 | 100% 정확한 키 일치(Exact Match) · 범위 조건 | 의미적 거리 기반 근사 최근접 이웃(ANN · 코사인 유사도) |
| 주요 연산 장치 | CPU (분기 예측 · 포인터 추적 중심) | GPU Tensor Core · NPU (분기 없는 대규모 SIMD 행렬곱) |
| 대표 인덱싱 구조 | B+Tree · HashMap · Red-Black Tree | HNSW 근접 그래프 · IVF-PQ · RadixAttention Trie · GraphRAG |
| 저장 정밀도 관점 | 무손실(Lossless) 완벽 보존 필수 | 양자화(BF16 · FP8 · INT4 · PQ) 기반 정확도-메모리 트레이드오프 |
AI·컴퓨팅에서의 다양한 데이터 표현 방식 5가지
다차원 Strided 배열 & 블록 희소 행렬
이미지[B, H, W, C], 비디오, LLM 가중치를 Stride 메타데이터와 함께 GPU 연속 메모리에 배치하고, BF16 · FP8 · 2:4 Sparse 압축으로 연산 밀도를 극대화합니다.
BPE 서브워드 토큰 ID & Radix 접두사 트리
텍스트·코드·오디오를 정수 토큰 ID 시퀀스로 인코딩하며, LLM 서빙 시 공통 앞부분 프롬프트의 KV 캐시를 트라이(Radix Tree) 노드로 공유합니다.
고밀도 임베딩 & 곱 양자화(PQ) 코드
문장과 이미지의 의미를 1,024~4,096차원 좌표로 투영합니다. 수억 건 저장 시에는 이진 양자화(Binary) 및 PQ(Product Quantization)로 32배 이상 압축 표현합니다.
Apache Arrow & Parquet · SafeTensors
전통적인 행(Row) 단위 대신 같은 컬럼 데이터를 메모리에 연속 적재해 CPU 역직렬화 없이(Zero-Copy) GPU 학습 파이프라인으로 고속 스트리밍합니다.
지식 그래프(Property Graph) · 구문 트리(AST) · 계층 요약 트리(RAPTOR)
단순 벡터 청크가 놓치는 엔티티 간 다중 홉(Multi-hop) 관계, 소스코드의 문법 계층 구조(AST), 그리고 거대 문서를 상향식 클러스터 요약 트리로 묶는 RAPTOR 구조는 AI 추론의 논리적 뼈대를 제공합니다.
최신 AI와 LLM에서 최신 Data Structure의 5대 구조와 미래
현대의 LLM 성능과 인프라 단가는 단순히 신경망 수식이 아니라 "수십억 벡터와 KV 캐시, 수테라바이트 데이터셋을 어떤 최신 자료구조에 담아 움직이는가"에 의해 결정됩니다. Deep Research 관점에서 현대 AI와 미래를 이끄는 5대 핵심 자료구조 혁신을 해부합니다.
Paged KV Cache 블록 테이블 & RadixAttention 접두사 트리(Trie)
기존 LLM 추론 엔진은 요청마다 최대 길이만큼 연속 GPU VRAM 배열을 미리 잡아야 해 메모리의 60% 이상이 낭비되었습니다. vLLM의 PagedAttention은 Key-Value 캐시를 OS 가상 메모리처럼 고정 크기 KV Block Table로 쪼개 비연속 저장함으로써 배치 처리량을 수 배 끌어올렸습니다. 한 걸음 더 나아가 SGLang의 RadixAttention은 모든 요청의 과거 토큰 KV 블록들을 고전 자료구조인 Radix Tree(압축 접두사 트리)로 조직하고 LRU 정책으로 관리해, 수십 번 반복되는 시스템 프롬프트 · CoT 트리 탐색 · 에이전트 다중 턴 대화의 계산을 Zero-Copy로 즉시 재사용합니다.
HNSW(계층 탐색 작은 세상 그래프) & DiskANN
관계형 DB의 B+Tree는 1차원 숫자 정렬에는 완벽하지만, 1,536차원이 넘는 의미 벡터 공간에서는 차원의 저주(Curse of Dimensionality)로 인해 전체 스캔이나 다름없이 느려집니다. 이를 해결한 것이 HNSW(Hierarchical Navigable Small World)입니다. HNSW는 고전의 Skip List(다층 지름길)와 근접 그래프(Proximity Graph)를 결합해, 최상위 성긴 레이어에서 굵직한 방향을 점프로 좁힌 뒤 최하위 촘촘한 그래프에서 몇 홉 만에 가장 유사한 의미 벡터를 찾아냅니다. 초대형 규모에서는 SSD/NVMe 디스크와 Vamana 그래프를 결합한 DiskANN과 이진/PQ 양자화로 RAM 비용을 획기적으로 낮춥니다.
Apache Arrow (컬럼 지향 IPC) · Lance · SafeTensors (mmap)
수십 TB의 멀티모달 학습 데이터를 JSON/CSV 행 구조나 Python Pickle로 읽으면 GPU는 노는데 CPU 파싱이 병목이 됩니다. 최신 AI 파이프라인(Ray Data, HuggingFace Datasets, Polars, LanceDB)은 메모리 내 컬럼 정렬 포맷인 Apache Arrow와 랜덤 액세스 벡터/멀티모달 저장소인 Lance를 채택해 프로세스 간 복사 없는(Zero-Copy) 데이터 스트리밍을 실현합니다. 모델 가중치 포맷 역시 보안 취약점이 있던 Pickle 대신 헤더 메타데이터 + 순수 연속 텐서 버퍼를 OS mmap으로 즉시 매핑하는 SafeTensors가 표준이 되었습니다.
GraphRAG(지식 그래프) · RAPTOR(계층 요약 트리) · MCTS 추론 트리
문서를 단순 500자 단위로 쪼개 1차원 벡터 목록으로만 보관하는 기존 RAG는 "이 데이터셋 전체의 핵심 주제는?", "A와 C를 잇는 숨은 인과 사슬은?" 같은 전역·다중 홉 질의에 무력합니다. 이를 돌파하기 위해 문서를 커뮤니티 그래프와 개체 관계로 엮는 GraphRAG, 클러스터링으로 상향식 요약 나무를 세우는 RAPTOR Tree, 그리고 추론 과정 자체를 분기·백트래킹 가능한 트리로 관리하는 Tree-of-Thoughts / MCTS 트리 자료구조가 LLM 인지 아키텍처의 표준으로 자리 잡았습니다.
미분 가능한 잠재 메모리(Neural Memory) & CXL 클러스터 통합 메모리
미래 AI의 자료구조는 두 방향으로 진화하고 있습니다. 첫째는 정적 텍스트 토큰(Token)이나 수동 그래프를 넘어 신경망 자체가 테스트 타임에 실시간으로 가중치/잠재 메모리를 갱신하며 기억을 압축하는 미분 가능한 신경 메모리(Neural Long-Term Memory · Titans / Test-Time Training)입니다. 둘째는 GPU VRAM의 물리 한계를 넘어 초고속 CXL(Compute Express Link) 랙 스케일 공유 메모리 풀 위에 수십 TB 규모의 분산 Radix KV 캐시와 하이브리드 벡터-그래프 인덱스를 직접 올려 여러 에이전트가 무복사로 공유하는 시대가 열리고 있습니다.
AI 개발자들에게 LLM 시대 최신 Data Structure가 가지는 5대 실무 의미
최신 LLM 응용과 AI 인프라를 개발하는 엔지니어에게 자료구조 선택은 곧 응답 속도, RAG 정확도, GPU 비용을 결정짓는 가장 강력한 아키텍처 레버입니다.
Radix Prefix Cache 친화적 프롬프트 배치
현대 추론 엔진(vLLM/SGLang/API Caching)은 접두사 트리(Radix Trie)로 KV 캐시를 재사용합니다. 변하지 않는 시스템 지침·도구 명세·정적 문서를 항상 앞부분에, 실시간 타임스탬프나 사용자 질의를 맨 뒷부분에 배치해야 캐시 적중률이 90% 이상 올라 비용·지연을 대폭 절감할 수 있습니다.
BM25(역색인) + B-Tree(메타데이터) + HNSW(벡터) 하이브리드
벡터 검색(HNSW)만 믿으면 고유 제품번호·법조문 번호 같은 정확 일치를 놓칩니다. 고전의 역색인(Inverted Index/BM25) 및 B-Tree 필터링과 최신 HNSW 의미 검색을 RRF(Reciprocal Rank Fusion)로 결합해야 실무 RAG 품질이 완성됩니다.
에이전트 기억을 '줄글'이 아닌 구조화 그래프·상태 트리로 관리
긴 대화 내역을 비정형 텍스트 덩어리로 쌓으면 문맥이 흐려집니다. 사용자 선호나 코드베이스 의존성은 지식 그래프(Knowledge Graph) · 코드 AST · JSON 상태 스키마라는 명시적 자료구조로 분리 관리할 때 에이전트 정확도가 비약적으로 상승합니다.
메모리 레이아웃(Arrow/SafeTensors/PQ) 기반 인프라 최적화
벡터 1억 개를 1536차원 Float32로 두면 600GB가 넘지만 Binary/PQ 양자화와 DiskANN을 적용하면 수십 GB 내로 10배 이상 저렴하게 서빙할 수 있습니다. Zero-Copy Arrow와 mmap SafeTensors 이해는 MLOps 필수 역량입니다.
리누스 토발즈의 격언이 AI 시대에도 통한다: "좋은 자료구조가 추론을 지배한다"
프롬프트 문구 몇 줄을 고치는 것보다, 데이터를 계층적 요약 트리(RAPTOR), 다중 홉 그래프(GraphRAG), 인덱스된 AST 블록 등 AI가 탐색하기 좋은 자료구조로 잘 조직해 주는 편이 훨씬 극적인 정확도 향상을 가져옵니다. LLM 시대의 뛰어난 AI 엔지니어는 곧 '인간과 AI 모두가 잘 탐색하는 데이터 구조를 설계하는 아키텍트'입니다.
원전 정의 · 참고 사이트 · 용어 · 대학 공개 강의 (원본 보존)
자료구조 (Data Structure) 는 전산학에서 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게한다. 대개 추상적 자료구조의 선택에서 시작하며, 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다.... 위키백과 : 자료구조