# B Tree & B+ Tree



이진 νŠΈλ¦¬λŠ” ν•˜λ‚˜μ˜ λΆ€λͺ¨κ°€ 두 개의 μžμ‹λ°–μ— κ°€μ§€μ§ˆ λͺ»ν•˜κ³ , κ· ν˜•μ΄ λ§žμ§€ μ•ŠμœΌλ©΄ 검색 효율이 μ„ ν˜•κ²€μƒ‰ κΈ‰μœΌλ‘œ 떨어진닀. ν•˜μ§€λ§Œ 이진 트리 ꡬ쑰의 간결함과 κ· ν˜•λ§Œ λ§žλ‹€λ©΄ 검색, μ‚½μž…, μ‚­μ œ λͺ¨λ‘ O(logN)의 μ„±λŠ₯을 λ³΄μ΄λŠ” μž₯점이 있기 λ•Œλ¬Έμ— 계속 κ°œμ„ μ‹œν‚€κΈ° μœ„ν•œ λ…Έλ ₯이 이루어지고 μžˆλ‹€.


# B Tree


λ°μ΄ν„°λ² μ΄μŠ€, 파일 μ‹œμŠ€ν…œμ—μ„œ 널리 μ‚¬μš©λ˜λŠ” 트리 자료ꡬ쑰의 일쒅이닀.

이진 트리λ₯Ό ν™•μž₯ν•΄μ„œ, 더 λ§Žμ€ 수의 μžμ‹μ„ κ°€μ§ˆ 수 있게 μΌλ°˜ν™” μ‹œν‚¨ 것이 B-Tree


μžμ‹ μˆ˜μ— λŒ€ν•œ μΌλ°˜ν™”λ₯Ό μ§„ν–‰ν•˜λ©΄μ„œ, ν•˜λ‚˜μ˜ λ ˆλ²¨μ— 더 μ €μž₯λ˜λŠ” 것 뿐만 μ•„λ‹ˆλΌ 트리의 κ· ν˜•μ„ μžλ™μœΌλ‘œ λ§žμΆ°μ£ΌλŠ” λ‘œμ§κΉŒμ§€ κ°–μΆ”μ—ˆλ‹€. λ‹¨μˆœν•˜κ³  효율적이며, 레벨둜만 따지면 μ™„μ „νžˆ κ· ν˜•μ„ 맞좘 νŠΈλ¦¬λ‹€.

λŒ€λŸ‰μ˜ 데이터λ₯Ό μ²˜λ¦¬ν•΄μ•Ό ν•  λ•Œ, 검색 ꡬ쑰의 경우 ν•˜λ‚˜μ˜ λ…Έλ“œμ— λ§Žμ€ 데이터λ₯Ό κ°€μ§ˆ 수 μžˆλ‹€λŠ” 점은 μƒλ‹Ήνžˆ 큰 μž₯점이닀.

λŒ€λŸ‰μ˜ λ°μ΄ν„°λŠ” λ©”λͺ¨λ¦¬λ³΄λ‹€ λΈ”λŸ­ λ‹¨μœ„λ‘œ μž…μΆœλ ₯ν•˜λŠ” ν•˜λ“œλ””μŠ€ν¬ or SSD에 μ €μž₯ν•΄μ•Όν•˜κΈ° λ•Œλ¬Έ!

ex) ν•œ λΈ”λŸ­μ΄ 1024 λ°”μ΄νŠΈλ©΄, 2λ°”μ΄νŠΈλ₯Ό μ½μœΌλ‚˜ 1024λ°”μ΄νŠΈλ₯Ό μ½μœΌλ‚˜ λ˜‘κ°™μ€ μž…μΆœλ ₯ λΉ„μš© λ°œμƒ. λ”°λΌμ„œ ν•˜λ‚˜μ˜ λ…Έλ“œλ₯Ό λͺ¨λ‘ 1024λ°”μ΄νŠΈλ‘œ 꽉 μ±„μ›Œμ„œ μ‘°μ ˆν•  수 있으면 μž…μΆœλ ₯에 μžˆμ–΄μ„œ 효율적인 ꡬ성을 κ°–μΆœ 수 μžˆλ‹€.

β†’ B-TreeλŠ” μ΄λŸ¬ν•œ μž₯점을 ν† λŒ€λ‘œ λ§Žμ€ λ°μ΄ν„°λ² μ΄μŠ€ μ‹œμŠ€ν…œμ˜ 인덱슀 μ €μž₯ λ°©λ²•μœΌλ‘œ μ• μš©ν•˜κ³  있음

# κ·œμΉ™

  • λ…Έλ“œμ˜ μžλ£Œμˆ˜κ°€ N이면, μžμ‹ μˆ˜λŠ” N+1이어야 함
  • 각 λ…Έλ“œμ˜ μžλ£ŒλŠ” μ •λ ¬λœ μƒνƒœμ—¬μ•Όν•¨
  • 루트 λ…Έλ“œλŠ” 적어도 2개 μ΄μƒμ˜ μžμ‹μ„ 가져야함
  • 루트 λ…Έλ“œλ₯Ό μ œμ™Έν•œ λͺ¨λ“  λ…Έλ“œλŠ” 적어도 M/2개의 자료λ₯Ό 가지고 μžˆμ–΄μ•Όν•¨
  • μ™ΈλΆ€ λ…Έλ“œλ‘œ κ°€λŠ” 경둜의 κΈΈμ΄λŠ” λͺ¨λ‘ κ°™μŒ.
  • μž…λ ₯ μžλ£ŒλŠ” 쀑볡 될 수 μ—†μŒ


# B+ Tree


λ°μ΄ν„°μ˜ λΉ λ₯Έ 접근을 μœ„ν•œ 인덱슀 μ—­ν• λ§Œ ν•˜λŠ” 비단말 λ…Έλ“œ(not Leaf)κ°€ μΆ”κ°€λ‘œ 있음

(기쑴의 B-Tree와 λ°μ΄ν„°μ˜ μ—°κ²°λ¦¬μŠ€νŠΈλ‘œ κ΅¬ν˜„λœ 색인ꡬ쑰)


B-Tree의 λ³€ν˜• ꡬ쑰둜, index λΆ€λΆ„κ³Ό leaf λ…Έλ“œλ‘œ κ΅¬μ„±λœ 순차 데이터 λΆ€λΆ„μœΌλ‘œ 이루어진닀. 인덱슀 λΆ€λΆ„μ˜ key 값은 leaf에 μžˆλŠ” key 값을 직접 μ°Ύμ•„κ°€λŠ”λ° μ‚¬μš©ν•¨.


# μž₯점

λΈ”λŸ­ μ‚¬μ΄μ¦ˆλ₯Ό 더 많이 μ΄μš©ν•  수 있음 (key 값에 λŒ€ν•œ ν•˜λ“œλ””μŠ€ν¬ μ•‘μ„ΈμŠ€ μ£Όμ†Œκ°€ μ—†κΈ° λ•Œλ¬Έ)

leaf λ…Έλ“œλΌλ¦¬ μ—°κ²° 리슀트둜 μ—°κ²°λ˜μ–΄ μžˆμ–΄μ„œ λ²”μœ„ 탐색에 맀우 μœ λ¦¬ν•¨

# 단점

B-tree의 경우 μ΅œμƒ μΌ€μ΄μŠ€μ—μ„œλŠ” λ£¨νŠΈμ—μ„œ 끝날 수 μžˆμ§€λ§Œ, B+treeλŠ” 무쑰건 leaf λ…Έλ“œκΉŒμ§€ 내렀가봐야 함




# B-Tree & B+ Tree

B-treeλŠ” 각 λ…Έλ“œμ— 데이터가 μ €μž₯됨

B+treeλŠ” index λ…Έλ“œμ™€ leaf λ…Έλ“œλ‘œ λΆ„λ¦¬λ˜μ–΄ μ €μž₯됨

(λ˜ν•œ, leaf λ…Έλ“œλŠ” μ„œλ‘œ μ—°κ²°λ˜μ–΄ μžˆμ–΄μ„œ μž„μ˜μ ‘κ·Όμ΄λ‚˜ μˆœμ°¨μ ‘κ·Ό λͺ¨λ‘ μ„±λŠ₯이 μš°μˆ˜ν•¨)


B-treeλŠ” 각 λ…Έλ“œμ—μ„œ key와 data λͺ¨λ‘ λ“€μ–΄κ°ˆ 수 있고, dataλŠ” disk block으둜 포인터가 될 수 있음

B+treeλŠ” 각 λ…Έλ“œμ—μ„œ key만 듀어감. λ”°λΌμ„œ dataλŠ” λͺ¨λ‘ leaf λ…Έλ“œμ—λ§Œ 쑴재

B+treeλŠ” add와 deleteκ°€ λͺ¨λ‘ leaf λ…Έλ“œμ—μ„œλ§Œ 이루어짐


# [참고자료]

μ΅œμ’… μˆ˜μ • : 12/17/2022, 7:23:59 AM