observe_db

Why? 왜 m-way 탐색 트리를 사용하는가?산술 연산/논리연산보다 메모리 접근 비용이 더 크다.- 디스크 접근은 산술연산보다 10,000배 정도, 메모리 접근은 100정도 시간이 더 걸림프로세서 속도와 메모리 접근 시간의 차이로 cache 사용디스크에서 block 단위 데이터 전송index를 이용해서 그 시간을 감소시킬 수 있음. AVL, Red-Black Tree의 탐색 성능은 O(log_2(n))노드가 모든 다른 블럭에 있으면 최악의 성능.탐색 시간 대부분이 메모리 접근에 소비됨.메모리 접근 횟수는 Tree 높이와 연관. m-way 탐색 트리는 공백이거나 다음 성질을 만족-1) 루트는 최대 m개의 서브 트리를 가진다.구조: n, A0, (E1, A1)... (En, An)Ei는 원소를 의미각 원소..

최적 이원 탐색 트리(Optimal Binary Search Trees)static optimality problem: 노드가 정해져서 수정할 수 없음.dynamic optimality proble: 노드를 추가/삭제 할 수 있음. static Optimality Problem정적 원소들의 집합에 대한 이원 탐색트리 구조- 삽입/삭제 없이 탐색만 수행- iterSearch 이용element* iterSearch(treePointer tree, int key){ while (tree) { if (key == tree->data) return tree; if (key data) tree = tree->left_child; else ..

"Hash"는 다양한 맥락에서 다양한 일반적인 의비로 사용되는 넓은 용어"해시"는 입력 객체로 사용하여 문자열이나 숫자를 출력하는 해시 함수 h를 의미합니다. 입력 객체는 일반적으로 문자열, 정수 또는 사용자 정의 구조와 같은 다른 객체로 구성된 더 큰 데이터 유형의 구성원입니다. 출력은 일반적으로 숫자 또는 문자열입니다. 명사 "해시"는 종종 이 출력을 가리킵니다. 동사 "해시"는 종종 "해시 함수 적용"을 의미합니다.(위키피디아+번역) 문제의 정의- 배열에서 특정 값을 어떻게 찾을 것인가. in non-sorted 해싱의 정의- 데이터를 해시테이블(hash table)이라는 배열에 저장하는 것- 데이터의 키 값을 적절한 해시함수를 이용하여 해시테이블 주소로 변환하여 데이터를 찾는 방법- 키 값 비교(..

용어레코드(record): 여러 개의 field로 객체(object, 정보) 표현리스트(list): 레코드의 집합(set)키(key): 레코드를 구분하기 위한 필드순차 탐색(Sequential Search or Linear Search): 레코드 리스트를 순차적으로 검사하는 것안정성(Stability): 정렬의 각 pass를 수행할 때 key값에 대해 상대적으로 순서를 그대로 유지한다면 알고리즘은 stable하다고 함.- 여러 개의 키를 우선순위를 정해서 정렬하는 경우 알고리즘 선택에 중요한 관건이 됨.(다른 말로 단일 키엔 그닥 의미 없음) 순차 탐색seqSearch(element a[], int k, int n){/* a[1:n]탐색; a[i].key = k를 만족하는 최소의 i를 반환. 없으면 0을..