이번 글에서는, 2-3 트리를 일반화한 B-트리에 대해 살펴볼 것이다. 빅 데이터는 메모리 용량으로 부족하기 때문에, 외부 저장소(e.g., 하드 디스크)에 저장한다. 때문에, 빅 데이터의 특정 데이터(=instance)를 사용(read/write)하기 위해서는, 그 데이터가 속해 있는 page를 외부 저장소에서 메모리로 가져와야 한다. 여기서 발생하는 대부분의 비용은 해당 page를 메모리로 가져올 때까지 발생하는 page I/O 횟수이다. B-트리는 page I/O 횟수 획기적으로 줄여준다. Definition of B-Tree B-tree는 2가지 종류의 노드(=page)를 가지고 있는 트리다. external node(=leaf node): (정렬 순서를 유지한) M-1개의 실제 데이터 key(c..

저번 글에서 살펴본, BST는 무작위 삽입 순서일 경우에만, $\lg N$ 성능을 보여줄 뿐, 모든 삽입 순서에 대해 $\lg N$ 성능을 보장해주지 않는다. 이번 글에서는, 모든 삽입 순서에 대해 $\lg N$ 성능을 보장해주는 Balanced Search Tree에 대해 살펴볼 것이다. Balanced Search Tree에는 대표적으로 2-3 트리와 b-트리가 있다. 1. 2-3 Tree Definition 2-3 트리는 2가지 종류의 노드를 가지고 있는 트리다. 2-node: 1 key, 2 children 3-node: 2 key, 3 children 왼쪽 서브 트리의 모든 key는 부모 노드의 key보다 작다. 가운데 서브 트리의 모든 key는 부모 노드의 key 사이에 있다. 오른쪽 서브 트..

탐색(search)는 수 많은 applications의 중요 기능 중 하나다. 이번 글에서는, search 연산을 제공해주는 symbol table에 대해 살펴볼 것이다. Symbol Table Definition A symbol table is data structure for key-value pairs that supports two operations: insert (put) a new pair into the table and search for (get) the value associated with given key. Symbol table은 key-value 쌍의 집합을 가지고 있는 동시에, 추가/탐색 연산을 지원하는 ADT다. 이때, key는 비교 연산(e.g., 등호 혹은 부등호 연산)..

이전에 배운 collection의 ADT(e.g., stack, queue)는 삽입 순서에 기반해 객체를 삭제했다. 이번 글에서는, 객체 값에 기반해 객체를 삭제하는 collection의 ADT(=PQ)를 살펴볼 것이다. PQ에는 2가지 방식이 존재한다. 1). 가장 높은 값을 가진 객체를 삭제하는 방식과 2). 가장 낮은 값을 가진 객체를 삭제하는 방식이 존재한다. PQ를 통해 다음과 같은 과정을 쉽고 빠르게 수행할 수 있다. 수집한 객체들 중 가장 큰 객체 5개를 찾는다. 기존 객체들에 10개의 새로운 객체를 추가한 후, 가장 큰 객체 3개를 찾는다. Priority Queue Priority Queue는 객체의 집합을 가지고 있는 동시에, 추가/제거 연산을 지원하는 ADT다. 이때, 제거 연산은 가..

수 많은 applications은, 객체들의 집합(=collection of objects)를 사용한다. 뿐만 아니라 집합의 기본 연산들(e.g., 새로운 객체 추가, 기존 객체 제거)도 사용한다. 이번 글에서는, 이러한 요구사항에 맞게 설계된 기본적인 data types(e.g., stack, queue)에 대해 살펴볼 것이다. stack과 queue의 차이점은 객체 제거 방식이다. stack은 가장 최근에 추가된 객체를 제거하고, queue는 가장 늦게 추가된 객체를 제거한다. 더보기 Modular programming 모듈화 프로그램(modular programming)의 개념은 인터페이스(interface)와 구현(implementation)을 완전히 분리시키는 것이다. implementation..

이번 글에서는 알고리즘 분석(=실행 시간 및 메모리 사용량 예측)에 대해 살펴볼 것이다. 알고리즘 분석을 하는 대표적인 이유는 "알고리즘 성능을 예측하여, 클라이언트에게 확신을 주기 위함"이다. "Scienific method"을 사용해 알고리즘을 분석할 것이다. Scienitic method Observe: 프로그램 실행 시간(=event)의 특징(=feature)을 관찰한다. (computer = natural world) Hypothesize: 실행 시간(=data)과 일치하는(or 비슷한) 가설을 설계(=modeling)한다. Predict: 가설을 사용해, (입력값이 다른) 프로그램 실행 시간(=another event)을 예측한다. Verify: 더 많은 events을 예측해본다. Valida..