์ด์ง ํธ๋ฆฌ๋ ํ๋์ ๋ถ๋ชจ๊ฐ ๋ ๊ฐ์ ์์๋ฐ์ ๊ฐ์ง์ง ๋ชปํ๊ณ , ๊ท ํ์ด ๋ง์ง ์์ผ๋ฉด ๊ฒ์ ํจ์จ์ด ์ ํ๊ฒ์ ๊ธ์ผ๋ก ๋จ์ด์ง๋ค. ํ์ง๋ง ์ด์ง ํธ๋ฆฌ ๊ตฌ์กฐ์ ๊ฐ๊ฒฐํจ๊ณผ ๊ท ํ๋ง ๋ง๋ค๋ฉด ๊ฒ์, ์ฝ์ , ์ญ์ ๋ชจ๋ O(logN)์ ์ฑ๋ฅ์ ๋ณด์ด๋ ์ฅ์ ์ด ์๊ธฐ ๋๋ฌธ์ ๊ณ์ ๊ฐ์ ์ํค๊ธฐ ์ํ ๋ ธ๋ ฅ์ด ์ด๋ฃจ์ด์ง๊ณ ์๋ค.
๋ฐ์ดํฐ๋ฒ ์ด์ค, ํ์ผ ์์คํ ์์ ๋๋ฆฌ ์ฌ์ฉ๋๋ ํธ๋ฆฌ ์๋ฃ๊ตฌ์กฐ์ ์ผ์ข ์ด๋ค.
์ด์ง ํธ๋ฆฌ๋ฅผ ํ์ฅํด์, ๋ ๋ง์ ์์ ์์์ ๊ฐ์ง ์ ์๊ฒ ์ผ๋ฐํ ์ํจ ๊ฒ์ด B-Tree
์์ ์์ ๋ํ ์ผ๋ฐํ๋ฅผ ์งํํ๋ฉด์, ํ๋์ ๋ ๋ฒจ์ ๋ ์ ์ฅ๋๋ ๊ฒ ๋ฟ๋ง ์๋๋ผ ํธ๋ฆฌ์ ๊ท ํ์ ์๋์ผ๋ก ๋ง์ถฐ์ฃผ๋ ๋ก์ง๊น์ง ๊ฐ์ถ์๋ค. ๋จ์ํ๊ณ ํจ์จ์ ์ด๋ฉฐ, ๋ ๋ฒจ๋ก๋ง ๋ฐ์ง๋ฉด ์์ ํ ๊ท ํ์ ๋ง์ถ ํธ๋ฆฌ๋ค.
๋๋์ ๋ฐ์ดํฐ๋ฅผ ์ฒ๋ฆฌํด์ผ ํ ๋, ๊ฒ์ ๊ตฌ์กฐ์ ๊ฒฝ์ฐ ํ๋์ ๋
ธ๋์ ๋ง์ ๋ฐ์ดํฐ๋ฅผ ๊ฐ์ง ์ ์๋ค๋ ์ ์ ์๋นํ ํฐ ์ฅ์ ์ด๋ค.
๋๋์ ๋ฐ์ดํฐ๋ ๋ฉ๋ชจ๋ฆฌ๋ณด๋ค ๋ธ๋ญ ๋จ์๋ก ์
์ถ๋ ฅํ๋ ํ๋๋์คํฌ or SSD์ ์ ์ฅํด์ผํ๊ธฐ ๋๋ฌธ!
ex) ํ ๋ธ๋ญ์ด 1024 ๋ฐ์ดํธ๋ฉด, 2๋ฐ์ดํธ๋ฅผ ์ฝ์ผ๋ 1024๋ฐ์ดํธ๋ฅผ ์ฝ์ผ๋ ๋๊ฐ์ ์
์ถ๋ ฅ ๋น์ฉ ๋ฐ์. ๋ฐ๋ผ์ ํ๋์ ๋
ธ๋๋ฅผ ๋ชจ๋ 1024๋ฐ์ดํธ๋ก ๊ฝ ์ฑ์์ ์กฐ์ ํ ์ ์์ผ๋ฉด ์
์ถ๋ ฅ์ ์์ด์ ํจ์จ์ ์ธ ๊ตฌ์ฑ์ ๊ฐ์ถ ์ ์๋ค.
โ B-Tree๋ ์ด๋ฌํ ์ฅ์ ์ ํ ๋๋ก ๋ง์ ๋ฐ์ดํฐ๋ฒ ์ด์ค ์์คํ
์ ์ธ๋ฑ์ค ์ ์ฅ ๋ฐฉ๋ฒ์ผ๋ก ์ ์ฉํ๊ณ ์์
- ๋ ธ๋์ ์๋ฃ์๊ฐ N์ด๋ฉด, ์์ ์๋ N+1์ด์ด์ผ ํจ
- ๊ฐ ๋ ธ๋์ ์๋ฃ๋ ์ ๋ ฌ๋ ์ํ์ฌ์ผํจ
- ๋ฃจํธ ๋ ธ๋๋ ์ ์ด๋ 2๊ฐ ์ด์์ ์์์ ๊ฐ์ ธ์ผํจ
- ๋ฃจํธ ๋ ธ๋๋ฅผ ์ ์ธํ ๋ชจ๋ ๋ ธ๋๋ ์ ์ด๋ M/2๊ฐ์ ์๋ฃ๋ฅผ ๊ฐ์ง๊ณ ์์ด์ผํจ
- ์ธ๋ถ ๋ ธ๋๋ก ๊ฐ๋ ๊ฒฝ๋ก์ ๊ธธ์ด๋ ๋ชจ๋ ๊ฐ์.
- ์ ๋ ฅ ์๋ฃ๋ ์ค๋ณต ๋ ์ ์์
๋ฐ์ดํฐ์ ๋น ๋ฅธ ์ ๊ทผ์ ์ํ ์ธ๋ฑ์ค ์ญํ ๋ง ํ๋ ๋น๋จ๋ง ๋ ธ๋(not Leaf)๊ฐ ์ถ๊ฐ๋ก ์์
(๊ธฐ์กด์ B-Tree์ ๋ฐ์ดํฐ์ ์ฐ๊ฒฐ๋ฆฌ์คํธ๋ก ๊ตฌํ๋ ์์ธ๊ตฌ์กฐ)
B-Tree์ ๋ณํ ๊ตฌ์กฐ๋ก, index ๋ถ๋ถ๊ณผ leaf ๋ ธ๋๋ก ๊ตฌ์ฑ๋ ์์ฐจ ๋ฐ์ดํฐ ๋ถ๋ถ์ผ๋ก ์ด๋ฃจ์ด์ง๋ค. ์ธ๋ฑ์ค ๋ถ๋ถ์ key ๊ฐ์ leaf์ ์๋ key ๊ฐ์ ์ง์ ์ฐพ์๊ฐ๋๋ฐ ์ฌ์ฉํจ.
๋ธ๋ญ ์ฌ์ด์ฆ๋ฅผ ๋ ๋ง์ด ์ด์ฉํ ์ ์์ (key ๊ฐ์ ๋ํ ํ๋๋์คํฌ ์ก์ธ์ค ์ฃผ์๊ฐ ์๊ธฐ ๋๋ฌธ)
leaf ๋ ธ๋๋ผ๋ฆฌ ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ก ์ฐ๊ฒฐ๋์ด ์์ด์ ๋ฒ์ ํ์์ ๋งค์ฐ ์ ๋ฆฌํจ
B-tree์ ๊ฒฝ์ฐ ์ต์ ์ผ์ด์ค์์๋ ๋ฃจํธ์์ ๋๋ ์ ์์ง๋ง, B+tree๋ ๋ฌด์กฐ๊ฑด leaf ๋ ธ๋๊น์ง ๋ด๋ ค๊ฐ๋ด์ผ ํจ
B-tree๋ ๊ฐ ๋ ธ๋์ ๋ฐ์ดํฐ๊ฐ ์ ์ฅ๋จ
B+tree๋ index ๋ ธ๋์ leaf ๋ ธ๋๋ก ๋ถ๋ฆฌ๋์ด ์ ์ฅ๋จ
(๋ํ, leaf ๋ ธ๋๋ ์๋ก ์ฐ๊ฒฐ๋์ด ์์ด์ ์์์ ๊ทผ์ด๋ ์์ฐจ์ ๊ทผ ๋ชจ๋ ์ฑ๋ฅ์ด ์ฐ์ํจ)
B-tree๋ ๊ฐ ๋ ธ๋์์ key์ data ๋ชจ๋ ๋ค์ด๊ฐ ์ ์๊ณ , data๋ disk block์ผ๋ก ํฌ์ธํฐ๊ฐ ๋ ์ ์์
B+tree๋ ๊ฐ ๋ ธ๋์์ key๋ง ๋ค์ด๊ฐ. ๋ฐ๋ผ์ data๋ ๋ชจ๋ leaf ๋ ธ๋์๋ง ์กด์ฌ
B+tree๋ add์ delete๊ฐ ๋ชจ๋ leaf ๋ ธ๋์์๋ง ์ด๋ฃจ์ด์ง
์ฐธ๊ณ ์๋ฃ : ๋งํฌ