[Database]- B-Tree , B+-Tree

📕Dymaic Multilevel Index는 B-Tree와 B+-Tree를 사용한다.

• 각각의 node는 하나의 부모와 0개 이상의 child nodes를 가진다.
• Leaf node : 0개의 자식을 가진 노드
  • 서로 다른 수준에서 리프 노드가 발생하는 경우 불균형 발생
• Nonleaf node called internal node
• unbalanced tree의 경우 각 leaf node마다 탐색 시간이 천차만별이기에 
  balancing tree를 만들어야 함.

 

📕Good tree?

• BST(BInary Search Tree) we have depth of T = O(log2 n)
  • 좋은 트리란 완벽하게 balancing 된 tree를 의미
• n= number of nodes in the tree
• n개의 노드가 있다면 깊이는 log 2 n
• A balanced tree 
  • 각 노드의 왼쪽 및 오른쪽 하위 트리에 동일한 수의 노드가 존재해야 함.
  • leaf nodes들의 높이는 같아야 한다.
  • 즉 자식이 없는 노드는 모두 한 층에 있어야 함.
• 트리에 삽입하기 전에 data set을 randomizing 하여 트리가 얕게 유지될 것으로 예상할 수 있습니다
  • randomizing 하는데 필요한 작업 : O(n)
• 그래서 balanced tree의 목적은 tree의 순서(또는 깊이)를 최소화하는 것이다

 

📕B-Tree

 

 

📕Search tree

• search tree of order p 
  • 각 노드는 p-1 search value와 p pointer를 포함한다.
    • <P1, <K1, Pr1>, P2, <K2, Pr2>, ,,,,, <Kq-1, Prq-1>,Pq > , where q<=p
  •  Pi : tree pointer to a child or null Pointer
  • Ki : a search value
  • Pri : Ki의 record를 들고있는 block을 가리키는 data pointer
  • 모든 search values는 unique하다.

 

위 그림은 4개의 search value를 가지기 때문에 P는 5이다.

 

📕조건

📕p=3인 search tree

• 이 그림에는 표시되지 않지만 트리의 모든 키 값은 데이터 파일의 레코드에 대한 포인터와 연결됩니다(pr 포인터 *).
•  각 노드가 가득 찰 필요는 없지만 절반 이상 채워야 합니다.
•  더 중요한 것은 검색 트리가 왼쪽에서 오른쪽으로 정렬된다는 것입니다.

 

📕formal definition of a B-Tree

• B tree form
  • <P1, <K1, Pr1>, P2,<K2,Pr2>, ,,,, <Kq-1, Prq-1>, Pq>
  • P1 : tree pointer , K1 : search value, Pri : data pointer
• Pi가 가리키는 하위 트리의 모든 검색 키 필드 값 X에 대해
  • X <Ki-1 => i =1 ; 
  • Ki-1 <X < Ki => 1 <i <q;
  • Ki-1 <X  => i=q
• 각각의 노드는 p tree pointers를 갖는다.
• 각각의 노드는 루트 노드와 리프 노드가 있다. 그들은 적어도 [p/2] tree pointers를 가진다.
  (internal nodes는 반드시 hal full 해야 함)
• q tree pointers, q <=p has q-1 search value(K) and thus q-1 data pointer(PR)

 

📕Calculating using a  B-Tree

• order p of the B-tree = 23
  • B-tree is 69% full
• 각 노드는 평균적으로 23*0.69 = 15.xxx->16 p
  • 16 pointers and 15 search key [key는 p-1개]
• average fan-out fo = 16

 

📕B-tree structure

• 왼쪽은 key value가 5보다 작은 sub tree
• 가운데는 5와 8 사이에 있는 sub tree
• 오른쪽은 8보다 큰 sub tree

📕B-tree as Primary file organization

• small number records, data는 각각의 node에 저장된다.
• 이러한 경우 data pointer 대신 record가 저장된다.
• 이러한 점이 B-Tree와 B+-tree의 차이점이다.
• records의 수가 많아지면 B+-tree를 사용하는 것이 훨씬 이득이다.
  • 실제 데이터는 리프 노드만을 가리킨다.

 

📕B-tree example

• 가정
  • Block size (B) : 512B
  • Record Pointer(Pr) : 7B
  • Tree pointer : (P) : 6B
  • Search key value (V) : 9B
  • Number of records (R) : 30,000
  • The tree is at least 69% full
• order p 계산
  • p * P + (p-1) * V + (p-1) * Pr <= 512
    • 이유 p개의 tree pointer와 p-1개의 Record pointer와 key value를 가짐.
    • p * 6 +  (p-1) * 9 + (p-1) * 7 <= 512
    • 22p <= 528(512 + 16)
    • p  = 24
• 최소 69 % 채워야 하기에  p = 24 * 0. 69 = 16.56,,, 
• 따라서 각각의 노드의 order p = 17이다.

 

📕B+- Tree

• Data pointers는 오직 leaf nodes에 저장된다.
  • search field의 모든 값에 대한 entry를 가짐.
• search field가 key인 경우 record에 대한 data pointer를 저장
• non key인 경우  data file records에 대한 pointer를 포함하는 block pointer를 저장

• internal nodes
  • search의 방향 지시
  • 검색을 안내하기 위해 반복된 리프 노드의 일부 검색 필드 값 
  • Pr pointers(data pointers)를 가지지 않는다.
  • 모든 Pr pointers는 leaf node에 위치한다.
  • data records가 저장되지 않는다.
    • B-tree는 internal nodes에서도 실제 data record를 저장

 

• Multiple level index의 대부분의 구현은 B+ 트리라고 불리는 B 트리의 변형을 사용한다.
  • 데이터 포인터는 트리의 리프 노드에만 저장됩니다.
  • 리프 노드의 구조는 내부 노드의 구조와 다르다.
  • 일반적으로 리프 노드는 검색 필드에서 순서대로 액세스 할 수 있도록 함께 연결됩니다

 

 

📕B+ -Tree 구조

 

📗특징

 

• 맨 왼쪽 노드에서 시작하여 연결된 목록으로 리프 노드를 통과할 수 있습니다.
• 유사한 B 트리에 비해 더 많은 항목을 B+ 트리의 내부 노드에 패킹할 수 있습니다.
  •  B+ 트리의 내부 노드에 데이터 포인터가 없음
•  이제 각 노드는 2/3이 채워져야 합니다!
• 말단의 leafnode record까지 탐색해야 함.

 

📕B+ -Tree example

• 가정
  • Block size (B) : 512B
  • Record Pointer (PR ) : 7B
  • Tree Pointer (P) : 6B
  • Search key value (V) : 9B
  • Number of Records (R) : 30,000
• step 1 : the order of the B+- tree
  • ( p * P ) + (( P-1 * V) <= B 
  •  p * 6 + (p-1) * 9 <= 512
  • 15p <= 521
  • p = 34 ( B- tree 26)
    • -> 34 pointer and 33 search key value
• step 2 : order p for leaf nodes
  • p(leaf) * (Pr+v) + P <= B
  • p(leaf) * (7+9) + 6 <=512
  • 16 * p <= 506
  • p(leaf)= 31
  • Each leaf node  Pleaf = 31 key value/ data pointer

📕B+- Tree example 2

• 가정
  • Block size (B) : 512B
  • Record Pointer(PR) : 7B
  • Tree Pointer (P) : 6B
  • Seach key Value(V) : 9B
  • Number of records(R) : 30,000
  • at least 69% full
• How many data records can a 4 level B+- Tree hold?
  • 4 levels = (root, level 1, level 2, leaf)
• Internal node have 34 * 0.69 = 23 -> 23 tree pointer, 22 key value
• Each leaf node p(leaf) 31 * 0.69 = 21 -> 21 record pointers

 

 

📕B+-Trees in Practice

• Typical order : 100. (Typical fill-factor : 67%) => node가 평균적으로 채워지는 정도
  • order = minimum search values(or q-1)
  • Average fanout = 133(search cost 감소량)
• Typical capacities
  • Height 4: 133^4 = 312,900,700 records
  • Height 3: 133^3 = 2,352,637 records
• buffer pool에서의 최상위 레벨 유지
  • Level 1 = 1Page = 8 Kbytes
  • Level 2 = 133 pages = 1 Mbyte
  • Level 3 = 17,689pages = 133 Mbyte