μ΄μ§ νΈλ¦¬λ νλμ λΆλͺ¨κ° λ κ°μ μμλ°μ κ°μ§μ§ λͺ»νκ³ , κ· νμ΄ λ§μ§ μμΌλ©΄ κ²μ ν¨μ¨μ΄ μ ν κ²μ κΈμΌλ‘ λ¨μ΄μ§λ€. νμ§λ§ μ΄μ§ νΈλ¦¬ ꡬ쑰μ κ°κ²°ν¨κ³Ό κ· νλ§ λ§λ€λ©΄ κ²μ, μ½μ , μμ λͺ¨λ O(logN)μ μ±λ₯μ 보μ΄λ μ₯μ μ΄ μκΈ° λλ¬Έμ κ³μ κ°μ μν€κΈ° μν λ Έλ ₯μ΄ μ΄λ£¨μ΄μ§κ³ μλ€.
-
λ°μ΄ν° λ² μ΄μ€, νμΌ μμ€ν μμ λ리 μ¬μ©λλ νΈλ¦¬ μλ£κ΅¬μ‘°μ μΌμ’ μ΄λ€.
-
μ΄μ§ νΈλ¦¬λ₯Ό νμ₯ν΄μ, λ λ§μ μμ μμμ κ°μ§ μ μκ² μΌλ°ν μν¨ κ²μ΄ B Tree.
-
μμ μμ λν μΌλ°νλ₯Ό μ§ννλ©΄μ, νλμ λ 벨μ λ μ μ₯λλ κ² λΏλ§ μλλΌ νΈλ¦¬μ κ· νμ μλμΌλ‘ λ§μΆ°μ£Όλ λ‘μ§κΉμ§ κ°μΆμλ€. λ¨μνκ³ ν¨μ¨μ μ΄λ©°, λ 벨λ‘λ§ λ°μ§λ©΄ μμ ν κ· νμ λ§μΆ νΈλ¦¬μ΄λ€.
-
Ex)
-
λλμ λ°μ΄ν°λ₯Ό μ²λ¦¬ν΄μΌ ν λ, κ²μ ꡬ쑰μ κ²½μ° νλμ λ Έλμ λ§μ λ°μ΄ν°λ₯Ό κ°μ§ μ μλ€λ μ μ μλΉν ν° μ₯μ μ΄λ€.
-
λλμ λ°μ΄ν°λ λ©λͺ¨λ¦¬λ³΄λ€ λΈλ λ¨μλ‘ μ μΆλ ₯νλ νλλμ€ν¬ or SSDμ μ μ₯ν΄μΌ νκΈ° λλ¬Έ!
-
ν λΈλμ΄ 1024 λ°μ΄νΈμ΄λ©΄, 2λ°μ΄νΈλ₯Ό μ½μΌλ 1024λ°μ΄νΈλ₯Ό μ½μΌλ λκ°μ μ μΆλ ₯ λΉμ©μ΄ λ°μνλ€.
-
λ°λΌμ νλμ λ Έλλ₯Ό λͺ¨λ 1024λ°μ΄νΈλ‘ κ½ μ±μμ μ‘°μ ν μ μμΌλ©΄ μ μΆλ ₯μ μμ΄μ ν¨μ¨μ μΈ κ΅¬μ±μ κ°μΆ μ μλ€.
-> B-Treeλ μ΄λ¬ν μ₯μ μ ν λλ‘ λ§μ λ°μ΄ν°λ² μ΄μ€ μμ€ν μ μΈλ±μ€ μ μ₯ λ°©λ²μΌλ‘ μ μ©νκ³ μλ€.
-
κ·μΉ
- λ Έλμ μλ£μκ° Nμ΄λ©΄, μμ μλ N+1μ΄μ΄μΌ νλ€.
- κ° λ Έλμ μλ£λ μ λ ¬λ μνμ¬μΌ νλ€.
- λ£¨νΈ λ Έλλ μ μ΄λ 2κ° μ΄μμ μμμ κ°μ ΈμΌ νλ€.
- λ£¨νΈ λ Έλλ₯Ό μ μΈν λͺ¨λ λ Έλλ μ μ΄λ M/2κ°μ μλ£λ₯Ό κ°μ§κ³ μμ΄μΌ νλ€.
- μΈλΆ λ Έλλ‘ κ°λ κ²½λ‘μ κΈΈμ΄λ λͺ¨λ κ°λ€.
- μ λ ₯ μλ£λ μ€λ³΅λ μ μλ€.
- λ°μ΄ν°μ λΉ λ₯Έ μ κ·Όμ μν μΈλ±μ€ μν λ§ νλ λΉλ¨λ§ λ Έλκ° μΆκ°λ‘ μλ€.
- κΈ°μ‘΄μ B-Treeμ λ°μ΄ν°μ μ°κ²°λ¦¬μ€νΈλ‘ ꡬνλ μμΈκ΅¬μ‘°.
- B-Treeμ λ³ν κ΅¬μ‘°λ‘ index λΆλΆκ³Ό leaf λ Έλλ‘ κ΅¬μ±λ μμ°¨ λ°μ΄ν° λΆλΆμΌλ‘ μ΄λ£¨μ΄μ§λ€. μΈλ±μ€ λΆλΆμ key κ°μ leafμ μλ key κ°μ μ§μ μ°Ύμκ°λλ° μ¬μ©νλ€.
μ₯μ
- λΈλ μ¬μ΄μ¦λ₯Ό λ λ§μ΄ μ΄μ©ν μ μλ€. (Key κ°μ λν νλλμ€ν¬ μ‘μΈμ€ μ£Όμκ° μκΈ° λλ¬Έ)
- Leaf λ ΈλλΌλ¦¬ μ°κ²° 리μ€νΈλ‘ μ°κ²°λμ΄ μμ΄μ λ²μ νμμ λ§€μ° μ 리νλ€.
λ¨μ
- B-Treeμ κ²½μ° μ΅μ μΌμ΄μ€μμλ 루νΈμμ λλ μ μμ§λ§, B+Treeλ 무쑰건 leaf λ ΈλκΉμ§ λ΄λ €κ°λ΄μΌ νλ€.
- B-Tree : κ° λ
Έλμ λ°μ΄ν°κ° μ μ₯λλ€.
- κ° λ Έλμμ keyμ data λͺ¨λ λ€μ΄κ° μ μκ³ , dataλ disk blockμΌλ‘ ν¬μΈν°κ° λ μ μλ€.
- B+ Tree : index λ
Έλμ leaf λ
Έλλ‘ λΆλ¦¬λμ΄ μ μ₯λλ€.
- κ° λ Έλμμ keyλ§ λ€μ΄κ°λ€. λ°λΌμ dataλ leaf λ Έλμλ§ μ‘΄μ¬νλ€.
- add, delete μ°μ° λͺ¨λ leaf λ Έλμμλ§ μ΄λ£¨μ΄μ§λ€.
- λν, leaf λ Έλλ μλ‘ μ°κ²°λμ΄ μμ΄μ μμ μ κ·Όμ΄λ μμ°¨ μ κ·Ό λͺ¨λ μ±λ₯μ΄ μ°μνλ€.