목록전체 글 (60)

SunFly의 코딩 및 정보 블로그

B+tree 삽입(Insertion) 알고리즘 - 3(Type-2 삽입)

※ 맨 아래층이 아닌 인덱스 노드로의 삽입 : type-2 curr가 맨 아래층보다 위의 층의 노드이며 여기에 삽입하는 경우 B-tree의 삽입과 동일한 방식으로 일어남. 다만, 사용할 포인터 필드는 ptri 이다. (즉, index node에 대한 Pointer를 저장하는 필드.) Case 1: 빈자리가 있는 경우 : 순서에 맞춰 삽입하고 종료 Case 2: 빈자리가 없는 경우 : overflow 발생 ● Case 1: 빈공간이 있는 경우 ● Case 2: 빈공간이 없을 경우 ※ 삽입 과정에서 부모 주소의 관리 : Stack 이용 삽입과정에서 데이터노드를 찾아가는 과정에서 각 노드의 Pointer를 stack에 저장 인덱스 구조의 Root에서 시작 아래로 내려갈 때마다 그 직전에 노드의 주소를 stac..
알고리즘 2021. 10. 12. 02:53
B+Tree 삽입(Insertion) 알고리즘 - 2 (Type-1 삽입)

※ 정상상황에서의 삽입 ● 초기상황이 아닌 경우가 정상 상황(Root 노드의 ptrd[1] != NULL인 상황) ● Root에서 출발하여 삽입할 record가 들어가야 할 데이터 노드를 찾아야 한다. 삽입할 record의 key값이 new_key라고 하자. Root노드에서 출발하여 navigation을 반복하여 인덱스 구조의 leaf노드에 도달하도록 한다. "new_key
알고리즘 2021. 10. 12. 02:17
B+Tree 삽입(Insertion) 알고리즘 - 1

※ 첫 record 삽입 ● Root가 아직 NULL인 경우에 해당됨 ● 아직 하나의 record가 삽입되기 전 인덱스 노드 하나를 만들고 이를 Root가 가리키게 함. ptri[0]에 NULL을 넣음(이것은 이 노드가 index 구조의 leaf 노드임을 나타낸다.) 데이터 노드를 하나 만듬. record를 데이터 노드에 삽입. 인덱스 노드의 ptrd[0]가 이 데이터 노드를 가리키게 한다. 인덱스 노드의 ptri[1] 에 0을 넣는다. ≫ 초기상황(아직 B+Tree의 형태를 갖추지 못함.) 임을 나타냄. ※ 초기 상황(초반부) 삽입 ● Root가 NULL이 아닌 경우의 초반부 삽입 Sequence set에 데이터 노드 하나만 존재하는 경우 Root 인덱스 노드의 Pointer[1]이 NULL인지를 체크..
알고리즘 2021. 10. 12. 01:02
B+Tree 알고리즘이란?

■ 실제로 가장 널리 활용되는 구조 ■ 인덱스 구조와 시퀀스셋(data node set)으로 구성됨. ※ 인덱스 구조(Index) 각 노드가 record 대신 key값만 저장된 B-tree 구조 노드의 key값은 데이터 노드로 찾아가는데 이용하는 navigation에 이용 B-tree의 요구와 조건은 모두 충족시켜야함. ※ 시퀀스셋(data node set) 데이터 노드들의 연결리스트로 구성됨. 노드는 데이터 즉 record들을 가짐. (모든 레코드가 저장됨.) 모든 record는 key값 순서로 정렬되어 있음. ▶인덱스 구조의 루트 노드를 제외한 모든 노드들은 "at least half full(절반 이상)" 조건을 만족함. (단, 초기 상황은 예외) ※ B+tree의 장점 범위 탐색(Range Sea..
알고리즘 2021. 10. 11. 20:20
이진 탐색 트리(Binary Search Tree)란?

■ 탐색을 효육적으로 하기 위한 자료구조 ※ 특징 이진트리이며 모든 원소는 서로 다른 유일한 키(key)를 가진다. (왼쪽 sub-트리의 key값) 루트 노드의 키값) : 루트 노드의 오른쪽 sub-트리에 대해서 탐색연산 수행. ▷예시 코드 BinTree* searchBST(BunTree* b..
알고리즘 2021. 10. 11. 18:04
이전 Prev 1 ··· 8 9 10 11 12 Next 다음