목록알고리즘 (13)

SunFly의 코딩 및 정보 블로그

B-tree 탐색(searching or Retrieval) 알고리즘

m-원 탐색 트리와 알고리즘은 동일하다. (이진 탐색을 사용한다.) ※ Searhing 알고리즘 (1) Pointer curr를 Tree의 Root노드에 지정한다. (2) curr 노드에서 왼쪽부터 오른쪽으로 record를 스캔한다. => if curr==NULL, retrun with fail(만약 curr노드가 NULL이면 실패한다.) (3) i=0; (3-1) if (i >= fill_cnt) { curr = P[i]; goto 2; } // 더이상 비교하지 않고 마지막 포인터를 사용한다. (3-2) (Case1) rec.key < skey : i = i++; go to (3-1) //다음 record를 스캔한다. (Case2) rec.key == skey : return with success /..
알고리즘 2021. 10. 11. 14:32
B-tree 삽입(insertion) 알고리즘

※ 전체 과정 (삽입될 record가 변수 in_rec에 들어있다고 가정한다.(key값은 in_key에 있다.) ) 먼저 in_rec를 leaf 노드에 넣고자 시도한다. leaf 노드를 탐색하기 위해 B-tree의 루트 노드에서 출발하여 pointer를 따라 leaf 노드에 도달할 때까지 내려간다. 도달한 leaf 노드를 Pointer curr 가 가리키게 한다. 쌍 를 curr가 가리키는 노드 내에 적당한 위치 에 넣어야 한다. Case 1: curr 노드에 빈 공간이 존재한다 를 적당한 위치에 삽입하고 알고리즘을 종료한다. Case 2: curr 노드에 빈 공간이 존재하지 않는다. Big node(bnode)를 사용한다. bnode(정상 node보다 record와 pointer가 하나씩 더 많은 노드..
알고리즘 2021. 10. 10. 23:54
B-tree 알고리즘이란?

다방향 탐색 트리를 이르는 말. 데이터 레코드의 순차적 처리와 직접적 처리를 모두 지원하는 다단계 트리 구조라고 정의되어 있다. ※ B-tree의 특징 삽입 및 삭제 알고리즘은 Tree가 Balance 되는 것을 보장한다. 즉, 삽입과 삭제가 일어나도 B-tree의 기본 구조를 지켜서 진행된다. (Balance : 모든 leaf 노드가 (거의) 같은 level에 속해야 한다.) Branching factor가 2 이상의 큰 값일 수 있다. ( -> 빠른 탐색 시간을 보장한다.) m-원 탐색 트리 성질을 만족해야 한다. (1. 탐색의 효율성을 증가 2. record들을 정렬된 순서로 출력한다.) 데이터의 저장 및 탐색이 가장 많이 이용되는 데이터 구조 중의 하나이다. ※B-tree의 정의(Definitio..
알고리즘 2021. 10. 10. 22:13
이전 Prev 1 2 Next 다음