분류 전체보기156 [파일구조] - B+ 트리 1. 개요 B+ 트리의 개념은 B 트리와 같다. 그러나 B 트리는 entry sequenced file을 이용하여 데이터 파일을 표현하지만, B+ 트리는 indexed sequential file을 이용한다. Indexed sequential file의 장점과 구현 방법은 이전의 글에서 설명하였다. B+ 트리는 인덱스로 indexed sequential file의 separator를 이용한다. Indexed sequential file의 separator는 유일하게 결정되는 것이 아니라, 같은 파일이더라도 다양한 separator가 정의될 수 있으므로, B+ 트리의 개념을 설명하기 위해 실제 key 값의 가장 짧은 prefix를 separator로 이용하는 simple prefix B+ 트리를 예로 들어.. 2016. 6. 12. [파일구조] - Indexed Sequential File 1. 개요 B 트리에서 사용되는 entry sequenced file과 반대되는 것으로 indexed sequential file이 있다. Indexed sequential file은 인덱스를 통해 데이터 파일의 각 레코드에 접근할 수 있으며, 데이터 파일의 레코드가 정렬된 순서로 저장되어 있는 구조를 갖고 있다. Indexed sequential file은 인덱스를 통해 각 레코드에 접근할 수 있다는 점이 entry sequenced file과 같지만, 데이터 파일의 레코드가 정렬되어 있다는 점이 다르다. 그러나 데이터 파일을 정렬된 순서로 유지하는 것은 하드디스크 상에서 데이터가 삽입될 위치를 찾고, 그 뒤에 있는 데이터를 모두 shift 해야 하기 때문에 막대한 비용이 소모된다. Indexed se.. 2016. 6. 12. [파일구조] - Virtual B 트리 1. 개요 B 트리 구조를 이용하여 인덱스를 저장한 데이터 파일을 읽기 위해서는 항상 B 트리의 root node가 저장된 페이지를 하드디스크에서 읽어야 한다. 그러나 하드디스크에서 데이터를 읽는 것은 막대한 비용이 소모되기 때문에 파일 시스템의 성능을 저하시키는 요인으로 작용한다.이러한 문제를 해결하기 위해 B 트리의 root node가 저장된 페이지를 메모리에 유지하는 keep-the-root strategy가 고안되었다. Virtual B 트리는 keep-the-root-strategy를 확장하여 B 트리를 구성하는 정보가 저장된 몇 개의 페이지를 메모리 상의 버퍼에 저장하여 하디드스크 접근을 최소화하는 B 트리의 변형이다. 2. Page Replacement 알고리즘 Virtual B 트리는 제한.. 2016. 6. 12. [파일구조] - B 트리의 연산 1. Insert 연산 Insert 연산은 인자로 전달받은 key를 B 트리에 추가하는 연산으로써, B 트리의 insert 연산은 다른 종류의 트리에 비해 매우 복잡하다. B 트리의 insert 연산은 아래와 같은 과정으로 수행된다. 1) 새로운 key 값이 입력될 leaf node를 탐색한다. B 트리에서 leaf node를 탐색하는 과정은 이진 탐색 트리(binary search tree)에서 주어진 값에 대한 노드를 찾는 과정과 유사하다.2) 선택된 leaf node의 모든 key 값 중에서 새로운 key 값이 가장 크다면, 선택된 leaf node의 가장 큰 key 값에 대한 정보를 모두 새로운 key 값으로 변경한다. 이러한 변경은 B 트리 전체에서 발생한다.3) 새로운 key 값을 선택된 le.. 2016. 6. 12. [파일구조] - B 트리 1. 개요 B 트리는 대용량의 파일을 효율적으로 관리하기 위한 자료구조로써, 산업 분야에서 데이터베이스 시스템에 전반적으로 사용되고 있는 de facto 표준이다. 가끔 이진 탐색 트리(binary search tree)와 B 트리를 혼동하는 경우가 있는데, 두 종류의 트리는 완전히 다른 구조와 연산을 갖고 있다. 인덱스를 이용하는 파일 시스템에서 가장 큰 문제는 '어떻게 하면 메모리에 올릴 수 없을 정도로 큰 용량의 인덱스에 효율적으로 접근할 것인가?'이다. 파일 시스템에서 인덱스를 이용하는 가장 근본적인 이유는 파일 전체를 이진 탐색(binary search)하여 레코드를 찾는 것보다 인덱스를 이용하는 것이 더 빠르기 때문이다. 따라서, B 트리는 아래의 두 가지 요구사항을 반드시 충족해야 한다. 인.. 2016. 6. 11. [파일구조] - 트리 구조를 이용한 인덱스 관리 1. 트리 구조를 이용한 인덱스 관리 이전의 배열이나 inverted list를 이용한 인덱스 체계의 문제점을 극복하고자 인덱스를 트리 구조로 관리하는 것에 대한 많은 연구가 이루어졌다. 인덱스를 관리하기 위한 자료 구조를 고안할 때는 반드시 아래와 같은 사항을 고려해야 한다. 인덱스를 정렬된 상태로 유지할 수 있어야 하며, 인덱스를 정렬하는 비용을 최소화해야 한다.인덱스의 추가(insertion), 삭제(deletion)을 효율적으로 수행할 수 있어야 한다.인덱스를 효율적으로 검색할 수 있어야 한다.이러한 세 가지 요구 사항을 만족시킬 수 있는 자료 구조로는 이진 탐색 트리가 있다. 이진 탐색 트리는 아래의 그림과 같이 모든 데이터를 정렬된 상태로 보관하며, 각 노드는 2개 이하의 자식 노드만 가질 수.. 2016. 6. 11. [파일구조] - 인덱스 파일의 구현 II 이 글의 소스 코드는 File Structures: An Object-Oriented Approach with C++ 3rd Edition의 내용을 수정하여 작성한 것 입니다. 1. 인덱스 파일의 구조 인덱스 파일은 앞에서 정의한 TextIndex를 저장하는 파일이다. 인덱스 파일은 고정 길이 필드, 고정 길이 레코드로 구성된다. 인덱스 파일은 파일은 파일 자체를 나타내는 BufferFile과 메모리 상에 인덱스를 저장하고 있는 TextIndex, 그리고 TextIndex를 버퍼 단위로 파일입출력하기 위한 TextIndexBuffer로 구성된다. 2. Class TextIndexedFile TexIndexedFile은 데이터 파일만 하드디스크에 저장하는 것이 아니라, 인덱스 파일도 같이 저장한다. Tex.. 2016. 6. 10. [파일구조] - 인덱스 파일의 구현 I 이 글의 소스 코드는 File Structures: An Object-Oriented Approach with C++ 3rd Edition의 내용을 수정하여 작성한 것 입니다. 1. Class TextIndex 인덱스 파일을 구현하기에 앞서, TextIndex라는 인덱스를 저장하는 자료구조를 정의한다. TextIndex는 일정 수의 인덱스들을 저장하는 자료구조로써, 인덱스의 추가, 제거, 검색 등의 연산을 갖는다. TextIndex의 class 정의는 아래와 같다. class TextIndex { public: TextIndex(int maxKeys = 100, bool unique = true); ~TextIndex(); int Insert(const char *key, int recAddr); int.. 2016. 6. 10. [파일구조] - 인덱싱(Indexing) 1. Entry Sequenced File Entry sequenced file은 레코드가 입력되는 순서대로 저장되는 파일이다. 레코드가 입력되는 순서대로 파일에 저장되기 때문에 파일에 저장된 레코드들은 정렬되어있지 않다. 파일에 저장된 레코드들이 정렬되어있지 않기 때문에 어떤 레코드를 찾기 위해서는 파일의 앞쪽부터 순차적으로 레코드를 읽어야한다. Entry sequenced file은 데이터를 관리한다는 측면에서는 매우 비효율적인 구조이다. Entry sequenced file의 이러한 문제점을 해결하기 위해 레코드가 입력될 때마다 레코드들을 정렬하는 sorted file을 생각할 수 있지만, sorted file에는 아래와 같은 치명적인 문제점이 존재한다. 레코드가 입력될 때 파일을 정렬한다면, 레코.. 2016. 6. 8. 큐(Queue) 1. 개요 큐(queue)는 먼저 입력된 자료가 먼저 출력되는 First In First Out(FIFO)구조로 동작하는 자료구조를 의미한다. 나중에 입력된 자료가 먼저 출력되는 스택(stack)과는 반대되는 구조이다. 운영체제에서 스택은 프린터 작업 처리, 프로세스 관리 등 데이터나 요청이 입력된 순서대로 작업을 처리해야하는 상황에 주로 이용된다. 큐에는 선형 큐(linear queue), 환형 큐(circular queue), 링크드 큐(linked queue) 등이 있다. 일반적으로, 큐는 선형 큐를 의미하며 선형 큐의 문제점을 극복하기 위해 환형 큐, 링크드 큐 등이 고안되었다. 선형 큐의 문제점은 아래에서 자세하게 설명한다. 2. 선형 큐(Linear Queue) 선형 큐는 큐의 가장 단순한 형.. 2016. 5. 22. 스택 (Stack) 1. 개요 스택 (stack)은 한쪽 끝에서만 자료를 추가하거나 꺼낼 수 있는 자료구조이다. 스택은 Last In First Out (LIFO)의 구조로 동작하기 때문에 스택에 접근할 때는 가장 최근에 추가된 자료부터 읽는다. 스택에 자료를 추가하는 연산을 push, 자료를 꺼내는 연산을 pop이라고 한다. [그림 1] 스택의 동작 스택은 많은 프로그램에서 광범위하게 사용되고 있는 자료구조로써, 가장 대표적인 활용으로는 시스템 스택이 있다. 다소 복잡해보일 수도 있는 함수 호출이나 재귀적 실행을 스택이라는 자료구조를 통해 간단히 구현할 수 있다. 아래의 [코드 1]은 main에서 func1을 호출하고 func1에서는 func2를, func2에서는 func3를 호출하도록 동작한다. 그러나 실질적인 프로그램.. 2016. 5. 21. [머신러닝] - Overfitting (과적합) 1. 개요 머신 러닝 (machine learning)에서 overfitting은 학습데이터를 과하게 잘 학습하는 것을 뜻한다. 일반적으로 학습 데이터는 실제 데이터의 부분집합인 경우가 대부분이다. 따라서, 아래의 그래프처럼 학습 데이터에 대해서는 오차가 감소하지만, 실제 데이터에 대해서는 오차가 증가하는 지점이 존재할 수 있다. Overfitting을 이러한 관점에서 본다면 overfitting은 학습 데이터에 대해 과하게 학습하여 실제 데이터에 대한 오차가 증가하는 현상이다. 예를 들어, 노란색 고양이를 보며 고양이의 특성을 학습한 사람이 검은색이나 흰색 고양이를 보고는 그것을 고양이라고 인식하지 못 하는 현상이 overfitting과 유사한 경우이다. 2. Overfitting과 딥러닝 앞에서 설명.. 2016. 5. 7. 이전 1 ··· 6 7 8 9 10 11 12 13 다음
