# 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 λ Έλμμλ§ μ΄λ£¨μ΄μ§
# [μ°Έκ³ μλ£]
β - νΈλΌμ΄(Trie) - μ΄μ체μ λ? β