ಬಿ-ಟ್ರೀ

Binary tree ಶೀರ್ಷಿಕೆಯೊಂದಿಗೆ ಗೊಂದಲಕ್ಕೀಡಾಗಬಾರದು.

ಚಿತ್ರ:B-tree.png

2 [1]ನೆಯ ಶ್ರೇಣಿಯ ಅಥವಾ 5 [2] ಶ್ರೇಣಿಯ ಒಂದು ಬಿ-ಟ್ರೀ.

ಕಂಪ್ಯೂಟರ್ ಸೈನ್ಸ್‌ನಲ್ಲಿ, ಬಿ-ಟ್ರೀ ಯು ಒಂದು ಟ್ರೀ ಡಾಟಾ ಸ್ಟ್ರಕ್ಚರ್ ಆಗಿದೆ, ಇದು ಡಾಟಾವನ್ನು ವರ್ಗೀಕರಿಸುತ್ತದೆ ಮತ್ತು ಸರ್ಚ್ ಮಾಡಲು ಸಹಕರಿಸುತ್ತದೆ, ಅನುಕ್ರಮವಾದ, ಒಳಸೇರಿಸುವಿಕೆ, ಮತ್ತು ಲಾಗರಿದಮ್‌ಗೆ ಸಂಬಂಧಿಸಿದಂತೆ ಸಮಯ ಪರಭಾರೆ ಮಾಡದಂತೆ ಅಳಿಸುವುದು ಇವುಗಳ ಪ್ರವೇಶಕ್ಕೆ ಸಹಕರಿಸುತ್ತದೆ. ಬಿ-ಟ್ರೀಯು ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀಯ ಸಾಮಾನ್ಯೀಕರಣವಾಗಿದೆ, ಅದರಲ್ಲಿ ಸಿಂಗಲ್ ನೋಡ್‌ನಿಂದ ಎರಡಕ್ಕಿಂತಲೂ ಹೆಚ್ಚು ದಾರಿಗಳು ದಿಕ್ಚ್ಯುತಿಗೊಳ್ಳುತ್ತವೆ. (Comer, p. 123) ಸೆಲ್ಫ್-ಬ್ಯಾಲೆನ್ಸಿಂಗ್ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀಗಳಂತಲ್ಲದೆ, ಬಿ-ಟ್ರೀಯು ದೊಡ್ಡ ಪ್ರಮಾಣದ ಡಾಟಾವನ್ನು ಓದಲು ಮತ್ತು ಬರೆಯಲು ಸಿಸ್ಟಂಗಳಿಗೆ ಅನುಕೂಲತೆಯನ್ನು ಕಲ್ಪಿಸುತ್ತದೆ. ಇದು ಸಾಮಾನ್ಯವಾಗಿ ಡಾಟಾಬೇಸ್‌ಗಳು ಮತ್ತು ಫೈಲ್‌ಸಿಸ್ಟಂಗಳಲ್ಲಿ ಬಳಸಲಾಗುತ್ತದೆ.

ಸ್ಥೂಲ ಅವಲೋಕನ

ಬಿ-ಟ್ರೀಗಳಲ್ಲಿ ಇಂಟರ್ನಲ್ (ನಾನ್-ಲೀಫ್) ನೋಡ್‌ಗಳು ಕೆಲವು ಪ್ರಿ-ಡಿಫೈನ್ಡ್ ಶ್ರೇಣಿಯಲ್ಲಿ ಹಲವಾರು ಸಂಖ್ಯೆಯ ಚೈಲ್ಡ್ ನೋಡ್‌ಗಳನ್ನು ಹೊಂದಿರಬಹುದು. ಒಂದು ನೋಡ್‌ನಿಂದ ಡಾಟಾವನ್ನು ಒಳಸೇರಿಸಿದರೆ ಅಥವಾ ಹೊರತೆಗೆದರೆ, ಅದರ ಚೈಲ್ಡ್ ನೋಡ್‌ಗಳ ಸಂಖ್ಯೆಯು ಬದಲಾಗುತ್ತದೆ. ಪ್ರಿ-ಡಿಫೈನ್ಡ್ ಶ್ರೇಣಿಯನ್ನು ನಿರ್ವಹಿಸುವ ಸಲುವಾಗಿ, ಇಂಟರ್ನಲ್ ನೋಡ್‌ಗಳನ್ನು ಸೇರಿಸಬಹುದು ಅಥವಾ ತೆಗೆದು ಹಾಕಬಹುದು. ಏಕೆಂದರೆ ಚೈಲ್ಡ್ ನೋಡ್‌ಗಳ ಶ್ರೇಣಿಯು ಅನುಮತಿ ಪಡೆದಿದ್ದು, ಬಿ-ಟ್ರೀಗಳು ಇತರೆ ಸೆಲ್ಫ್-ಬ್ಯಾಲೆನ್ಸಿಂಗ್ ಸರ್ಚ್ ಟ್ರೀಗಳಂತೆ ರಿ-ಬ್ಯಾಲೆನ್ಸಿಂಗ್ ಮಾಡುವ ಅಗತ್ಯ ಇಲ್ಲ, ಆದರೆ ಕೆಲ ಜಾಗ ನಿರುಪಯುಕ್ತವಾಗಬಹುದು, ಏಕೆಂದರೆ ಸಿಂಗಲ್ ನೋಡ್‌ಗಳು ಪೂರ್ಣ ಪ್ರಮಾಣದಲ್ಲಿ ಭರ್ತಿಯಾಗಿರುವುದಿಲ್ಲ ಒಂದು ನಿರ್ಧಿಷ್ಟವಾದ ಕಾರ್ಯ ನೆರವೇರುವಿಕೆಗಾಗಿ ಚೈಲ್ಡ್ ನೋಡ್‌ಗಳ ಕೆಳಗಿನ ಮತ್ತು ಮೇಲಿನ ಬೌಂಡ್‌ಗಳು ಮಾದರಿಯಂತೆ ಸ್ಥಿರವಾಗಿರುತ್ತವೆ. ಉದಾಹರಣೆಗೆ, ಒಂದು 2-3 ಬಿ-ಟ್ರೀ (ಅನೇಕ ವೇಳೆ ಸರಳವಾಗಿ 2-3 ಟ್ರೀ ಎಂದು ಅನ್ವಯಿಸಲಾಗುತ್ತದೆ)ಯಲ್ಲಿ, ಪ್ರತಿಯೊಂದು ಇಂಟರ್ನಲ್ ನೋಡ್ 2 ಅಥವಾ 3 ಚೈಲ್ಡ್ ನೋಡ್‌ಗಳನ್ನು ಹೊಂದಿರಬಹುದು.

ಬಿ-ಟ್ರೀಯ ಪ್ರತಿಯೊಂದು ಇಂಟರ್ನಲ್ ನೋಡ್ ಹಲವಾರು ಸಂಖ್ಯೆಯ ಕೀಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಸಾಮಾನ್ಯವಾಗಿ, ಹಲವಾರು ಸಂಖ್ಯೆಯ ಕೀಗಳು $d$ ಮತ್ತು $2d$ರ ಮಧ್ಯೆ ಮಾರ್ಪಾಡಾಗುವಂತೆ ಆಯ್ಕೆಮಾಡಲಾಗುತ್ತದೆ. ರೂಢಿಯಲ್ಲಿರುವಂತೆ, ಕೀಗಳು ನೋಡ್‌ನ ಹೆಚ್ಚು ಸ್ಥಳವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. 2ರ ಫ್ಯಾಕ್ಟರ್ ನೋಡ್‌ಗಳು ಬೇರೆಯಾಗುವುದಕ್ಕೆ ಮತ್ತು ಸೇರಿಕೊಳ್ಳುವುದನ್ನು ಖಚಿತಪಡಿಸುತ್ತದೆ. ಒಂದು ವೇಳೆ ಇಂಟರ್ನಲ್ ನೋಡ್ $2d$ ಕೀಗಳನ್ನು ಹೊಂದಿದ್ದರೆ, ಆ ನೋಡ್‌ಗೆ ಒಂದು ಕೀಯನ್ನು ಸೇರಿಸಿದರೆ $2d$ ಕೀ ನೋಡ್ ಅನ್ನು ಎರಡು $d$ ಕೀ ನೋಡ್‌ಗಳಾಗಿ ವಿದಳನಗೊಳ್ಳುವುದನ್ನು ಪೂರೈಸುತ್ತದೆ ಮತ್ತು ಅದರೆ ಪೇರೆಂಟ್ ನೋಡ್‌ಗಿ ಒಂದು ಕೀಯನ್ನು ಸೇರಿಸುತ್ತದೆ. ವಿದಳನಗೊಂಡ ಪ್ರತಿ ನೋಡ್ ಕನಿಷ್ಟ ಸಂಖ್ಯೆಯ ಕೀಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಅದೇರೀತಿಯಾಗಿ, ಒಂದು ಇಂಟರ್ನಲ್ ನೋಡ್ ಮತ್ತು ಅದರ ಪಕ್ಕದ್ದು $d$ ಕೀಗಳನ್ನು ಹೊಂದಿದ್ದರೆ, ಇಂಟರ್ನಲ್ ನೋಡ್ ಅನ್ನು ಅದರ ಪಕ್ಕದ್ದರ ಜೊತೆ ಸೇರಿಸುವುದರಿಂದ ಒಂದು ಕೀಯನ್ನು ಅಳಿಸಬಹುದು. ಕೀಯನ್ನು ಅಳಿಸುವುದರ ಮೂಲಕ ಇಂಟರ್ನಲ್ ನೋಡ್ ಅನ್ನು $d-1$ ಕೀಗಳನ್ನು ಹೊಂದುವಂತೆ ಮಾಡಬಹುದು; ಪಕ್ಕದ್ದನ್ನು ಸೇರಿಸುವುದರಿಂದ $d$ ಕೀಗಳು ಸೇರಬಹುದು ಹಾಗೂ ಪಕ್ಕದ್ದರ ಪೇರೆಂಟ್‌ನಿಂದ ಒಂದು ಕೀಯನ್ನು ಕೆಳಗೆ ತರಬೇಕಾಗುತ್ತದೆ. ಇದರ ಪರಿಣಾಮ $2d$ ಕೀಗಳ ಪರಿಪೂರ್ಣ ನೋಡ್.

ಒಂದು ನೋಡ್‌ನ ಬ್ರಾಂಚ್‌ಗಳ (ಅಥವಾ ಚೈಲ್ಡ್ ನೋಡ್‌ಗಳು) ಸಂಖ್ಯೆಯು, ನೋಡ್‌ನಲ್ಲಿ ಶೇಖರವಾಗಿರುವ ಕೀಗಳ ಸಂಖ್ಯೆಗಿಂತಲೂ ಹೆಚ್ಚಾಗಿರುತ್ತದೆ. 2-3 ಬಿ-ಟ್ರೀಯಲ್ಲಿ, ಇಂಟರ್ನಲ್ ನೋಡ್‌ಗಳು ಒಂದು ಕೀ (ಎರಡು ಚೈಲ್ಡ್ ನೋಡ್‌ಗಳ ಜೊತೆ) ಅಥವಾ ಎರಡು ಕೀಗಳನ್ನು (ಮೂರು ಚೈಲ್ಡ್ ನೋಡ್‌ಗಳ ಜೊತೆ) ಸಂಗ್ರಹಿಸುತ್ತವೆ. ಒಂದು ಬಿ-ಟ್ರೀಯನ್ನು ಕೆಲವುಬಾರಿ $(d+1)$ — $(2d+1)$ ಮಾನದಂಡಗಳಲ್ಲಿ ಅಥವಾ ಸರಳವಾಗಿ ಹೆಚ್ಚಿನ ಬ್ರ್ಯಾಂಚಿಂಗ್ ಶ್ರೇಣಿ $(2d+1)$ ಯಲ್ಲಿ ವಿವರಿಸಲಾಗುತ್ತದೆ .

ಎಲ್ಲಾ ಲೀಫ್ ನೋಡ್‌ಗಳನ್ನು ಒಂದೇ ಆಳದಲ್ಲಿ ಇಡುವುದರ ಮೂಲಕ ಒಂದು ಬಿ-ಟ್ರೀಯನ್ನು ಸಮತೋಲನ ಮಾಡಿ ಇಡಲಾಗುವುದು. ಈ ಆಳವು ನಿಧಾನವಾಗಿ ಎಲಿಮೆಂಟ್‌ಗಳು ಟ್ರೀಗೆ ಸೇರಿದಂತೆ ಹೆಚ್ಚಾಗುತ್ತಾ ಹೋಗುವುದು, ಆದರೆ ಸಮಗ್ರ ಆಳದ ಹೆಚ್ಚಳವು ವಿರಳ, ಮತ್ತು ಎಲ್ಲಾ ಲೀಫ್ ನೋಡ್‌ಗಳಲ್ಲಿನ ಫಲಿತಾಂಶವು ರೂಟ್‌ನಿಂದ ಒಂದು ನೋಡ್‌ನಷ್ಟು ಅಳತೆಯ ದೂರದಲ್ಲಿರುವುದು.

ಬಿ-ಟ್ರೀಗಳು ಪರ್ಯಾಯ ಸಲಕರಣೆಗಳಿಗಿಂತ ಹಲವಾರು ಪಟ್ಟು ಹೆಚ್ಚು ಪ್ರಯೋಜನಗಳನ್ನು ಹೊಂದಿದ್ದು, ಇವು ನೋಡ್ ಆಕ್ಸೆಸ್ ಸಮಯಗಳು ನೋಡ್‌ಗಳೊಳಗಿನ ಆಕ್ಸೆಸ್ ಸಮಯಗಳಿಗಿಂತ ಹೆಚ್ಚಿರುವ ಪರಿಸ್ಥಿತಿಗಳಿಗೆ ಅನ್ವಯಿಸುತ್ತವೆ. ಇದು ಸಾಮಾನ್ಯವಾಗಿ ನೋಡ್‌ಗಳು ಡಿಸ್ಕ್ ಡ್ರೈವ್ಗಳಂತಹ ಸೆಕೆಂಡರಿ ಸ್ಟೋರೇಜ್ಗಳಲ್ಲಿದ್ದಾಗ ನಡೆಯುತ್ತದೆ. ಪ್ರತಿ ಇಂಟರ್ನಲ್ ನೋಡ್ನೊಳಗಿನ ಚೈಲ್ಡ್ ನೋಡ್ಗಳ ಸಂಖ್ಯೆಯನ್ನು ಅತ್ಯಧಿಕವಾಗಿರುವಂತೆ ಮಾಡುವುದರಿಂದ ಟ್ರೀಯ ಎತ್ತರವು ಕಡಿಮೆಯಾಗುತ್ತದೆ ಮತ್ತು ದುಬಾರಿ ನೋಡ್ ಆಕ್ಸೆಸ್‍ಗಳ ಸಂಖ್ಯೆಯು ಕಡಿಮೆಯಾಗುವುದು. ಇದರ ಜತೆಗೇ ಟ್ರೀಯನ್ನು ಮರುಸಂತುಲಿತಗೊಳಿಸುವುದು ಕಡಿಮೆಯಾಗುತ್ತದೆ. ಚೈಲ್ಡ್ ನೋಡ್‌ಗಳ ಅತ್ಯಧಿಕ ಸಂಖ್ಯೆಯು ಪ್ರತಿ ಚೈಲ್ಡ್ ನೋಡ್‌ಗಾಗಿ ಸಂಗ್ರಹ ಮಾಡಬೇಕಾದ ಮಾಹಿತಿ ಮತ್ತು ಒಂದು ಸಂಪೂರ್ಣ ಡಿಸ್ಕ್ ಬ್ಲಾಕ್ನ ಗಾತ್ರ ಇಲ್ಲವೇ ಸೆಕೆಂಡರಿ ಸ್ಟೋರೇಜ್‌ನಲ್ಲಿ ಒಂದು ಸಮಾನ ಗಾತ್ರದ ಮೇಲೆ ಅವಲಂಬಿತವಾಗಿದೆ. 2-3 ಬಿ-ಟ್ರೀಗಳನ್ನು ವಿವರಿಸುವುದು ಸುಲಭವೇ ಆದರೂ, ಸೆಕೆಂಡರಿ ಸ್ಟೋರೇಜ್ ಅನ್ನು ಬಳಸುವ ಪ್ರಾಯೋಗಿಕ, ವ್ಯಾವಹಾರಿಕ ಬಿ-ಟ್ರೀಗಳ‍ ಕಾಯನಿರ್ವಹಣೆಯನ್ನು ಉತ್ತಮಗೊಳಿಸಲು ಅತ್ಯಧಿಕ ಸಂಖ್ಯೆಯ ಚೈಲ್ಡ್ ನೋಡ್‌‍ಗಳು ಬೇಕಾಗುತ್ತವೆ.

ಮಾರ್ಪಾಟುಗಳು

ಬಿ-ಟ್ರೀ ಪದವು ವಿಶೇಷ ವಿನ್ಯಾಸ ಅಥವಾ ಒಂದು ಸಾಮಾನ್ಯ ವರ್ಗದ ವಿನ್ಯಾಸಗಳನ್ನು ಆಧಾರಿಸಿರಬಹುದು. ಸೂಕ್ಷ್ಮವಾಗಿ ಹೇಳಬೇಕೆಂದರ್, ಒಂದು ಬಿ-ಟ್ರೀಯು ತನ್ನ ಇಂಟರ್ನಲ್ ನೋಡ್‌ಗಳಲ್ಲಿ ಕೀಗಳನ್ನು ಸಂಗ್ರಹಿಸುತ್ತದೆ ಆದರೆ ಆ ಕೀಗಳನ್ನು ಅದರ ಎಲೆಗಳ ದಾಖಲೆಗಳಲ್ಲಿ ಸಂಗ್ರಹಿಸುವುದಿಲ್ಲ. ಸಾಮಾನ್ಯ ವರ್ಗವು ಬಿ⁺-ಟ್ರೀ ಮತ್ತು ಬಿ^*-ಟ್ರೀಯಂತಹ ಬದಲಾವಣೆಗಳನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ.

• B⁺-ಟ್ರೀಯಲ್ಲಿ, ಇಂಟರ್ನಲ್ ನೋಡ್‌ಗಳಲ್ಲಿ ಕೀಗಳ ನಕಲುಗಳು ಸಂಗ್ರಹವಾಗಿರುತ್ತವೆ; ಕೀಗಳು ಮತ್ತು ದಾಖಲೆಗಳು ಎಲೆಗಳಲ್ಲಿ ಸಂಗ್ರಹವಾಗಿರುತ್ತವೆ; ಜೊತೆಯಲ್ಲಿ, ಸೀಕ್ವೆನ್ಷಿಯಲ್ ಆಕ್ಸೆಸ್ ಅನ್ನು ವೇಗಗೊಳಿಸುವ ಸಲುವಾಗಿ ಒಂದು ಲೀಫ್ ನೋಡ್ ಮುಂದಿನ ಲೀಫ್ ನೋಡ್‌ಗೆ ಒಂದು ಪಾಯಿಂಟರ್ ಅನ್ನು ಕೂಡ ಒಳಗೊಂಡಿರಬಹುದು. (Comer, p. 129)
• ಬಿ^*-ಟ್ರೀಯು ಇಂಟರ್ನಲ್ ನೋಡ್‌ಗಳನ್ನು ಹೆಚ್ಚು ಸಾಂದ್ರವಾಗಿ ಜೋಡಿಸುವ ಸಲುವಾಗಿ ಹೆಚ್ಚುಹೆಚ್ಚು ನೆರೆಹೊರೆಯ ಇಂಟರ್ನಲ್ ನೋಡ್‌‌ಗಳನ್ನು ಸಂತುಲಿತಗೊಳಿಸುತ್ತದೆ. (Comer, p. 129) ಉದಾಹರಣೆಗೆ, ಬಿ-ಟ್ರೀಯೊಂದರ ನಾನ್-ರೂಟ್ ನೋಡ್ ಅರ್ಧಭಾಗ ಮಾತ್ರ ತುಂಬಿರಬೇಕು, ಆದರೆ ಬಿ^*-ಟ್ರೀ ನಾಲ್ಕನೇ ಮೂರರಷ್ಟು ತುಂಬಿರಬೇಕು.
• ಎಣಿಸಲಾದ ಬಿ-ಟ್ರೀಸ್ ಭಂಡಾರ, ಟ್ರೀಯೊಳಗೆ ಪ್ರತಿಯೊಂದು ಪಾಯಿಂಟರ್ ಅನ್ನು ಹೊಂದಿದ್ದು, ಆ ಪಾಯಿಂಟರ್‌ನ ಕೆಳಗೆ ಸಬ್‌ಟ್ರೀಯೊಳಗಿನ ನೋಡ್‌ಗಳ ಸಂಖ್ಯೆಯನ್ನು ಹೊಂದಿರುವುದು. ಇದು ಕೀ ಆರ್ಡರ್‌ನಲ್ಲಿ ಎನ್‌ತ್ ರೆಕಾರ್ಡ್‌ಗೆ ತ್ವರಿತ ಹುಡುಕಾಟಗಳಿಗೆ ಅವಕಾಶವೀಯುತ್ತದೆ, ಇಲ್ಲವೇ ಯಾವುದೇ ಎರಡು ರೆಕಾರ್ಡ್‌ಗಳ ನಡುವಿನ ರೆಕಾರ್ಡ್‌ಗಳ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸಲು ಮತ್ತು ಹಲವಾರು ಇತರ ಸಂಬಂಧಿಸಿದ ಕಾರ್ಯಾಚರಣೆಗಳಿಗೆ ಎಡೆಮಾಡಿಕೊಡುತ್ತದೆ.

ಪದಮೂಲ ತಿಳಿದಿಲ್ಲ

ರುಡಾಲ್ಫ್ ಬಾಯರ್ ಎಡ್ ಮೆಕ್‍ಕ್ರೇಯ್ಟ್ 1971ರಲ್ಲಿ Boeing Research Labsನಲ್ಲಿ ಕೆಲಸ ಮಾಡುತ್ತಿದ್ದಾಗ ಬಿ-ಟ್ರೀಯನ್ನು ಕಂಡುಹಿಡಿದರು, ಆದರೆ ಬಿ ಎನ್ನುವುದು ಏನನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ ಎಂಬುದರ ಬಗ್ಗೆ ಯಾವ ರೀತಿಯ ವಿವರಣೆಯನ್ನೂ ನೀಡಲಿಲ್ಲ. ಡಗ್ಲಸ ಕಮರ್ ವಿವರಿಸುತ್ತಾರೆ:

"ಬಿ-ಟ್ರೀ"ಯ ಮೂಲವನ್ನು ಅದರ ಲೇಖಕರು ಇಂದಿನವರೆಗೂ ವಿವರಿಸಿಲ್ಲ. ನಾವು ಕಂಡಂತೆ ಈ ನಿಟ್ಟಿನಲ್ಲಿ, "ಸಮತೋಲನದಲ್ಲಿರುವ," "ವಿಶಾಲ," ಇಲ್ಲವೇ "ದಟ್ಟ" ಎಂಬುದು ಅನ್ವಯಿಸಬಹುದು. ಇತರರು ಸೂಚಿಸಿದಂತೆ "ಬಿ" ಎನ್ನುವುದು ಬೋಯಿಂಗ್ ಅನ್ನು ಬಿಂಬಿಸುತ್ತದೆ. ಆತನ ಕೊಡುಗೆಗಳಿಂದಾಗಿ ಬಿ-ಟ್ರೀಗಳನ್ನು "ಬಾಯರ್"- ಟ್ರೀಗಳೆಂದು ಕರೆಯುವುದು ಹೆಚ್ಚು ಸೂಕ್ತವಾದುದೆನಿಸುತ್ತದೆ. (Comer 1979, p. 123 footnote 1)

ಡಾಟಾಬೇಸ್ ಸಮಸ್ಯೆ

ಸಾರ್ಟೆಡ್ ಫೈಲ್ ಒಂದನ್ನು ಹುಡುಕುವ ಸಮಯ

ಸಾಮಾನ್ಯವಾಗಿ, ಸಾರ್ಟಿಂಗ್ ಮತ್ತು ಸರ್ಚಿಂಗ್ ಆಲ್ಗಾರಿದಮ್‌ಗಳ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಆರ್ಡರ್ ರೊಟೇಶನ್‌ ಅನ್ನು ಬಳಸಿ ನಡೆಸಬೇಕಾದ ಹೋಲಿಕೆಯ ಕಾರ್ಯಾಚರಣೆಗಳಿಂದ ನಿರ್ಧರಿಸಲಾಗುವುದು. $N$ರೆಕಾರ್ಡ್‌ಗಳುಳ್ಳ ಒಂದು ಸಾರ್ಟೆಡ್ ಟೇಬಲ್ಲಿನ ಬೈನರಿ ಸರ್ಚ್ ಅನ್ನು, ಉದಾಹರಣೆಗೆ, $O(\log _{2}N)$ ಹೋಲಿಕೆಗಳನ್ನು ಮಾಡುವುದರ ಮೂಲಕ ನಡೆಸಬಹುದು. ಅಕಸ್ಮಾತ್ ಟೇಬಲ್ 1,000,000 ದಾಖಲೆಗಳನ್ನು ಹೊಂದಿದ್ದಲ್ಲಿ, ಅಗ ಸುಮಾರು ೨೦ ಹೋಲಿಕೆಗಳೊಂದಿಗೆ ಒಂದು ನಿಖರವಾದ ದಾಖಲೆಯನ್ನು ಕಂಡುಹಿಡಿಯಬಹುದು: $\log _{2}1,000,000=19.931...$.

ದೊಡ್ಡ ದತ್ತಸಂಚಯಗಳನ್ನು ಐತಿಹಾಸಿಕವಾಗಿ ಡಿಸ್ಕ್ ಡ್ರೈವ್‌ಗಳಲ್ಲಿ ಯಾವಾಗಲೂ ಇಡಲಾಗುವುದು. ಡಿಸ್ಕ್ ಡ್ರೈವ್‌ನಲ್ಲಿನ ಒಂದು ದಾಖಲೆಯನ್ನು ಓದಲು ತಗುಲುವ ಸಮಯವು, ಆ ದಾಖಲೆಯು ಲಭ್ಯವಾದಾಗ ಕೀಗಳನ್ನು ಹೋಲಿಸಲು ತಗುಲುವ ಸಮಯಕ್ಕಿಂತ ಹೆಚ್ಚಾಗಬಹುದು. ಒಂದು ಡಿಸ್ಕ್ ಡ್ರೈವ್‌ನಲ್ಲಿನ ದಾಖಲೆಯನ್ನು ಓದಲು ತಗುಲುವ ಸಮಯವು ಒಂದು ಸೀಕ್ ಟೈಮ್ ಮತ್ತು ರೊಟೇಶನಲ್ ಡಿಲೇಗ ಳನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ಸೀಕ್ ಟ್ಸೈಮ್ 0ರಿಂದ 20 ಇಲ್ಲವೇ ಹೆಚ್ಚು ಮಿಲಿಸೆಕೆಂಡ್‌ಗಳಷ್ಟಾಗುತ್ತದೆ, ಮತ್ತು ರೊಟೇಶನಲ್ ಡಿಲೇಯು ರೊಟೇಶನಲ್ ಅವಧಿಯ ಸರಾಸರಿ ಅರ್ಧದಷ್ಟಾಗುತ್ತದೆ. ಒಂದು 7200 RPM ಡ್ರೈವ್‌ಗೆ ಇರುವ ರೊಟೇಶನಲ್ ಅವಧಿಯು 8.33 ಮಿಲಿಸೆಕೆಂಡುಗಳು. Seagate ST3500320NSನಂತಹ ಡ್ರೈವ್‌ಗೆ, ಟ್ರಾಕ್-ಟು-ಟ್ರಾಕ್ ಸೀಕ್ ಅವಧಿಯು 0.8 ಮಿಲಿಸೆಕೆಂಡುಗಳಾಗಿದ್ದು, ಸರಾಸರಿ ರೀಡಿಂಗ್ ಸಮಯವು 8.5 ಮಿಲಿಸೆಕೆಂಡ್‌ಗಳಾಗಿದೆ.. ಸರಳವಾಗಿ ಹೇಳಬೇಕೆಂದರೆ, ಡಿಸ್ಕ್‌ನಿಂದ ರೀಡ್ ಮಾಡಲು ಸುಮಾರು 10 ಮಿಲಿಸೆಕೆಂಡುಗಳು ತಗುಲುತ್ತವೆಂದು ಊಹಿಸಿಕೊಳ್ಳೋಣ.

ಆಗ, ಸ್ವಾಭಾವಿಕವಾಗಿ, ಮಿಲಿಯನ್ ದಾಖಲೆಗಳೊಳಗಿಂದ ಒಂದು ದಾಖಲೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ತಗುಲುವ ಸಮಯವು ಪ್ರತಿ ಡಿಸ್ಕ್ ರೀಡ್‌ಗೆ 10 ಮಿಲಿಸೆಕೆಂಡುಗಳಂತೆ 20 ಡಿಸ್ಕ್ ರೀಡ್‌ಗಳ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ, ಮತ್ತು ಇದು 0.2 ಸೆಕೆಂಡ್‌ಗಳಷ್ಟಾಗುತ್ತದೆ..

ಈ ಸಮಯವು ಅಷ್ಟೇನೂ ಕೆಟ್ಟದಾಗಿರುವುದಿಲ್ಲ ಏಕೆಂದರೆ ವೈಯುಕ್ತಿಕ ದಾಖಲೆಗಳು ಒಂದು ಡಿಸ್ಕ್ ಬ್ಲಾಕ್ ನೊಳಗೆ ಗುಂಪುಗೂಡಿಸಲ್ಪಟ್ಟಿರುತ್ತವೆ. ಒಂದು ಡಿಸ್ಕ್ ಬ್ಲಾಕ್ ಸುಮಾರು 16 ಕಿಲೋಬೈಟ್‍ಗಳಷ್ಟಿರುತ್ತದೆ. ಪ್ರತಿ ದಾಖಲೆಯೂ 160 ಬೈಟ್‌ಗಳಷ್ಟಿದ್ದರೆ, ಅಗ ಪ್ರತಿಯೊಂದು ಬ್ಲಾಕ್‌ನಲ್ಲಿ 100 ದಾಖಲೆಗಳನ್ನು ಸಂಗ್ರಹಿಸಬಹುದು. ಮೇಲಿನ ಡಿಸ್ಕ್ ರೀಡ್ ಸಮಯವು ನಿಜವಾಗಿ ಒಂದು ಸಂಪೂರ್ಣ ಬ್ಲಾಕ್‌ಗಾಗಿಯಾಗಿತ್ತು. ಡಿಸ್ಕ್ ಹೆಡ್ ಒಂದು ಸಾರಿ ಸರಿಯಾದ ಸ್ಥಾನದಲ್ಲಿ ಸ್ಥಿತವಾದಾಗ, ಬಹಳ ಕದಿಮೆ ಅಡ್ಡಿಗಳೊಂದಿಗೆ ಒಂದು ಅಥವಾ ಹೆಚ್ಚಿನ ಡಿಸ್ಕ್ ಬ್ಲ್ಲಾಕ್‌ಗಳನ್ನು ರೀಡ್ ಮಾಡಬಹುದು. ಪ್ರತಿ ಬ್ಲಾಕ್‌ಗೆ 100 ದಾಖಲೆಗಳಂತೆ, ಕಳೆದ ಸುಮಾರು 6ರಷ್ಟು ಹೋಲಿಕೆಗಳು ಯಾವುದೇ ಡಿಸ್ಕ್ ರೀಡ್‌ಗಳನ್ನು ಮಾಡಬೇಕಿಲ್ಲ-ಎಲ್ಲಾ ಹೋಲಿಕೆಗಳೂ ಹಿಂದಿನ ಡಿಸ್ಕ್ ಬ್ಲಾಕ್ ರೀಡ್‌ನ ಒಳಗೆ ಇರುತ್ತವೆ.

ಹುಡುಕಾಟದ ವೇಗವನ್ನು ವರ್ಧಿಸಲು, ಮೊದಲನೆ 13ರಿಂದ 14 ಹೋಲಿಕೆಗಳನ್ನು (ಪ್ರತಿಯೊಂದಕ್ಕೂ ಡಿಸ್ಕ್ ಆಕ್ಸೆಸ್ ಅವಶ್ಯಕತೆಯಿದ್ದಂತಹ) ವೇಗವಾಗಿ ಮುಗಿಸಬೇಕಾಗುತ್ತದೆ.

ಒಂದು ಇಂಡೆಕ್ಸ್ ಸರ್ಚ್‌ನ ವೇಗವನ್ನು ಹೆಚ್ಚಿಸುತ್ತದೆ

ಇಂಡೆಕ್ಸ್ನಿಂದ ಒಂದು ಉತ್ತಮ ಸುಧಾರಣೆಯನ್ನು ಹೊಂದಬಹುದು. ಮೇಲಿನ ಉದಾಹರಣೆಯಲ್ಲಿ,ಮೊದಲ ಡಿಸ್ಕ್ ರೀಡ್‌ಗಳು ಹುಡುಕಾಟದ ಶ್ರೇಣಿಯನ್ನು ಒಂದೆರಡು ಅಪವರ್ತನಗಳಷ್ಟು ಕಿರಿದಾಗಿಸಿ ಓದುತ್ತದೆ. ಇದನ್ನು ಗಣನೀಯ ಪ್ರಮಾಣದಲ್ಲಿ ಅಭಿವೃದ್ಧಿಪಡಿಸಬೇಕೆಂದರೆ ಪ್ರತಿ ಡಿಸ್ಕ್ ಬ್ಲಾಕ್‌ನಲ್ಲಿಯ ಮೊದಲನೆ ದಾಖಲೆಯನ್ನು ಹೊಂದಿರುವ ಒಂದು ಪೂರಕ ಸೂಚಿಯನ್ನು ರೂಪಿಸಬೇಕು (ಕೆಲವೊಮ್ಮೆ ಇದನ್ನು ಸ್ಪಾರ್ಸ್ ಇಂಡೆಕ್ಸ್ ಎನ್ನಲಾಗುವುದು). ಪೂರಕ ಸೂಚಿಯು ಮೂಲ ದತ್ತಾಂಶದ 1%ನಷ್ಟಿರುವುದದರೂ, ಅದನ್ನು ಹೆಚ್ಚು ವೇಗವಾಗಿ ಹುಡುಕಬಹುದು. ಪೂರಕ ಸೂಚಿಯಲ್ಲಿ ಎಂಟ್ರೀಯನ್ನು ಕಂಡುಕೊಳ್ಳುವುದರಿಂದ ನಮಗೆ ಮುಖ್ಯ ದತ್ತಸಂಚಯದಲ್ಲಿ ಯಾವ ಬ್ಲಾಕ್‌ನಲ್ಲಿ ಹುಡುಕಬೇಕು ಎಂಬುದು ತಿಳಿದುಬರುವುದು; ಪೂರಕ ಸೂಚಿಯಲ್ಲಿ ಹುಡುಕಿದ ನಂತರ, ಮುಖ್ಯ ದತ್ತಸಂಚಯದ ಅ ಒಂದು ಬ್ಲಾಕ್ ಅನ್ನು ಮಾತ್ರ - ಒಂದೇಒಂದು ಡಿಸ್ಕ್ ರೀಡ್‌ನ ವೆಚ್ಚದಲ್ಲಿ ಹುಡುಕಬೇಕಾಗುವುದು. ಸೂಚಿಯು ಸುಮಾರು 10,000 ಎಂಟ್ರಿಗಳನ್ನು ಹಿಡಿದಿಟ್ಟುಕೊಳ್ಳುವುದು, ಅದ್ದರಿಂದ ಇದಕ್ಕಾಗಿ ಕಡೆಪಕ್ಷ 14 ಹೋಲಿಕೆಗಳು ತಗಲುವವು. ಮುಖ್ಯ ದತ್ತಸಂಚಯದಂತೆ, ಪೂರಕ ಸೂಚಿಯಲ್ಲಿನ ಕೊನೆಯ ಸುಮಾರು 6 ಹೋಲಿಕೆಗಳು ಅದೇ ಡಿಸ್ಕ್ ಬ್ಲಾಕಿನಲ್ಲಿಯೂ ಇರುತ್ತವೆ. ಸೂಚಿಯನ್ನು ಸುಮಾರು 8 ಡಿಸ್ಕ್ರ್ ರೀಡ್‌ಗಳ ಮೂಲಕ ಹುಡುಕಬಹುದು, ಮತ್ತು ಅವಶ್ಯಕವಿರುವ ದಾಖಲೆಯನ್ನು ಡಿಸ್ಕ್ ರೀಡ್‌ಗಳಲ್ಲಿ ಪಡೆದುಕೊಳ್ಳಬಹುದು.

ಪೂರಕ ಸೂಚಿಗೆ ಒಂದು ಪೂರಕ ಸೂಚಿಯನ್ನು ರಚಿಸುವ ಸಲುವಾಗಿ, ಪೂರಕ ಸೂಚಿಯನ್ನು ರೂಪಿಸುವ ತಂತ್ರವನ್ನು ಪುನರಾವರ್ತಿಸಬಹುದು. ಇದರಿಂದಾಗಿ ಒಂದು ಡಿಸ್ಕ್ ಬ್ಲಾಕ್‌ನೊಳಗೆ ಸೇರಿಕೊಳ್ಳುವ, ಕೆವಲ 100 ಎಂಟ್ರೀಗಳ ಅವಶ್ಯಕತೆಯಿರುವ ಒಂದು ಪೂರಕ-ಪೂರಕ ಸೂಚಿಯನ್ನು ರಚಿಸಿದಂತಾಗುತ್ತದೆ.

ಅವಶ್ಯಕತೆಯಿರುವ ದಾಖಲೆಯನ್ನು ಪಡೆದುಕೊಳ್ಳಲು 14 ಡಿಸ್ಕ್ ಬ್ಲಾಕ್‌ಗಳನ್ನು ಓದುವ ಬದಲು, ನಾವು ಬರೆ 3 ಬ್ಲಾಕ್‌ಗಳನ್ನು ಮಾತ್ರ ಓದುವ ಅವಶ್ಯಕತೆಯಿರುವುದು.  ಪೂರಕ-ಪೂರಕ ಸೂಚಿಯ ಮೊದಲ(ಮತ್ತು ಕೇವಲ) ಬ್ಲಾಕ್ ಅನ್ನು ಓದುವುದು ಮತ್ತು ಹುಡುಕುವುದರಿಂದ ಪೂರಕ ಸೂಚಿಯ ತಕ್ಕುದಾದ ಬ್ಲಾಕ್ ಅನ್ನು ಗುರುತುಹಿಡಿಯಲು ಸಹಾಯವಾಗುತ್ತದೆ.   ಈ ಪೂರಕ ಸೂಚಿಯ ಬ್ಲಾಕ್ ಅನ್ನು ಓದುವುದು ಮತ್ತು ಹುಡುಕುವುದರಿಂದ, ಮುಖ್ಯ ದತ್ತಸಂಚಯದ ತಕ್ಕುದಾಗಿರುವ ಬ್ಲಾಕ್ ಅನ್ನು ಗುರುತುಹಿದಿಯಬಹುದು.  150 ಮಿಲಿಸೆಕೆಂಡ್‌ಗಳ ಬದಲಾಗಿ, ದಾಖಲೆಯನ್ನು ಪಡೆದುಕೊಳ್ಳಲು ಕೇವಲ 30 ಮಿಲಿಸೆಕೆಂಡುಗಳು ಮಾತ್ರ ತಗುಲುವವು.

ಪೂರಕ ಸೂಚಿಗಳಿಂದಾಗಿ ಬೈನರಿ ಸರ್ಚ್‌ನಿಂದ ಆಗುವ ಹುಡುಕಾಟದ ತೊಂದರೆಯು ಸುಮಾರು $\log _{2}N$ರಷ್ಟು ಡಿಸ್ಕ್ ರೀಡ್‌ಗಳ ಅವಶ್ಯಕತೆಯಿರುವ ಬದಲಾಗಿ $b$ ಅಡ್ಡಿಯ ಅಂಶವಾಗಿರುವ, ಕೇವಲ $\log _{b}N$ ಡಿಸ್ಕ್ ರೀಡ್‌ಗಳ ಅವಶ್ಯಕತೆ ಉಂಟಾಗುವುದು.

ಅನುಷ್ಠಾನ ಮಾಡುವಾಗ, ಮುಖ್ಯ ದತ್ತಸಂಚಯದಲ್ಲಿ ಅಗಾಗ ಹುಡುಕಾಟ ನಡೆಯುತ್ತಿದ್ದಲ್ಲಿ, ಪೂರಕ-ಪೂರಕ ಸೂಚಿ ಮತ್ತು ಪೂರಕ ಸೂಚಿಯ ಹೆಚ್ಚಿನ ಭಾಗವನ್ನು ಒಂದು ಡಿಸ್ಕ್ ಕ್ಯಾಶೆಯಲ್ಲಿ ಇರಿಸುವುದರಿಂದ ಇದ್ದಕ್ಕಿದ್ದಂತೆ ಡಿಸ್ಕ್ ರೀಡ್ ಅಗದಂತೆ ತಪ್ಪಿಸಬಹುದು.

ಅಳವಡಿಸುವಿಕೆಗಳು ಮತ್ತು ಅಳಿಸುವಿಕೆಗಳು ತೊಂದರೆ ಉಂಟುಮಾಡುತ್ತವೆ

ದತ್ತಸಂಚಯವು ಬದಲಾಗದಿದ್ದರೆ, ಆಗ ಸೂಚಿಯನ್ನು ಸಂಕಲಿಸುವುದು ಬಹಳ ಸುಲಭ, ಮತ್ತು ಅದನ್ನು ಬದಲಾಯಿಸುವ ಅವಶ್ಯಕತೆಯೂ ಇರದು.  ಆದರೆ ಬದಲಾವಣೆಗಳು ಆಗುತ್ತವೆ ಎಂದಾದಲ್ಲಿ ದತ್ತಸಂಚಯವನ್ನು ಮತ್ತು ಅದರ ಸೂಚಿಯನ್ನು ನಿರ್ವಹಿಸುವುದು ಹೆಚ್ಚು ಕ್ಲಿಷ್ಟವಾಗುತ್ತದೆ.

ದತ್ತಸಂಚಯದಿಂದ ದಾಖಲೆಗಳನ್ನು ತೆಗೆದುಹಾಕುವುದರಿಂದ ಹೆಚ್ಚಿನ ತೊಂದರೆಯೇನೂ ಅಗದು. ಸೂಚಿಯನ್ನು ಮೊದಲಿದ್ದ ರೀತಿಯೇ ಉಳಿಸಿಕೊಂಡು, ದಾಖಲೆಯನ್ನು ಅಳಿಸಿಹಾಕಲಾಗಿದೆ ಎಂದು ಗುರುತುಮಾಡಬಹುದು. ದತ್ತ ಸಂಚಯವು ವರ್ಗೀಕೃತ ವ್ಯವಸ್ಥೆಯಲ್ಲಿಯೇ ಉಳಿದುಕೊಳ್ಳುವುದು. ಬಹಳ ಹೆಚ್ಚು ಅಳಿಸುವಿಕೆಗಳಿದ್ದಲ್ಲಿ, ಆಗ ಹುಡುಕಾಟ ಮತ್ತು ಸಂಗ್ರಹಗಳ ದಕ್ಷತೆ ಕಡಿಮೆಯಾಗುವುದು.

ವರ್ಗೀಕೃತ ಅನುಕ್ರಮ ಫೈಲ್ ಒಂದರಲ್ಲಿ ಹೊಸ ಅಳವಡಿಕೆಗಳಿಂದ ಪ್ರಮಾದವುಂಟಾಗುತ್ತದೆ, ಏಕೆಂದರೆ ಅಳವಡಿಸಲಾದ ದಾಖಲೆಗಾಗಿ ಹೆಚ್ಚುವರಿ ಜಾಗವನ್ನು ಮಾಡಬೇಕಾಗುತ್ತದೆ. ಫೈಲ್‌ನಲ್ಲಿರುವ ಮೊದಲನೆಯ ರೆಕಾರ್ಡ್(ದಾಖಲೆ)ಗಿಂತ ಮೊದಲು ಇನ್ನೊಂದು ದಾಖಲೆಯನ್ನು ಒಳತೂರಿಸುವುದರಿಂದ ಎಲ್ಲಾ ದಾಖಲೆಗಳನ್ನು ಇರುವುದಕ್ಕಿಂತ ಒಂದು ಸ್ಥಾನ ಕೆಳಗೆ ತಳ್ಳಬೇಕಾಗುವುದು. ಇಂತಹ ಕಾರ್ಯಾಚರಣೆಯು ಬಹಳ ದುಬಾರಿ ಮಾತ್ರವಲ್ಲದೆ ಅವಾಸ್ತವಿಕ ಕೂಡಾ ಆಗಿರುವುದು.

ಒಂದು ಉಪಾಯವೆಂದರೆ, ಈ ರೀತಿಯ ಭವಿಷ್ಯದ ಅಳವಡಿಸುವಿಕೆಗಾಗಿಯೇ ಕೆಲವಷ್ಟು ಸ್ಥಳಾವಕಾಶವನ್ನು ಮೊದಲೇ ತೆರವು ಮಾಡಿಟ್ಟಿರುವುದು. ಒಂದು ಬ್ಲಾಕ್‌ನೊಳಗೆ ಎಲ್ಲಾ ರೆಕಾರ್ಡ್‌ಗಳನ್ನು ಒತ್ತೊತ್ತಾಗಿ ತುಂಬುವ ಬದಲು, ನಂತರದ ಅಳವಡಿಕೆಗಳಿಗಾಗಿ ಬ್ಲಾಕ್‌ನಲ್ಲಿ ಕೊಂಚ ಮುಕ್ತ ಸ್ಥಳಾವಕಾಶವನ್ನು ಮೀಸಲಾಗಿರಿಸಬಹುದು. ಅಂತಹ ರೆಕಾರ್ಡ್‌ಗಳನ್ನು "ಅಳಿಸಲಾದ" ರೆಕಾರ್ಡ್‌ಗಳಂತೆಯೆ ಗುರುತುಮಾಡಲಾಗುವುದು.

ಹೀಗೆ ಮಾಡಿದಲ್ಲಿ, ಒಂದು ಬ್ಲಾಕ್‌ನಲ್ಲಿ ಸ್ಥಳಾವಕಾಶವಿರುವ ತನಕ ಅಳವಡಿಸುವಿಕೆ ಮತ್ತು ಅಳಿಸುವಿಕೆಗಳು ವೇಗವಾಗಿ ನಡೆಯುತ್ತವೆ. ಅಕಸ್ಮಾತ್ ಒಂದು ಅಳವಡಿಕೆಯು ಬ್ಲಾಕ್‌ಗೆ ಸರಿಹೊಂದದೇ ಹೋದಲ್ಲಿ, ಆಗ ಹತ್ತಿರದ ಯಾವುದಾದರೂ ಬ್ಲಾಕ್‌ನ ಮುಕ್ತ ಸ್ಥಳಾವಕಾಶವನ್ನು ಹುಡುಕಿ ಪೂರಕ ಇಂಡೈಸಸ್ ಅನ್ನು ಸರಿಹೊಂದಿಸಬೇಕಾಗುವುದು. ಸಾಕಷ್ಟು ಸ್ಥಳಾವಕಾಶ ಹತ್ತಿರವೇ ಇದೆ ಮತ್ತು ಹೆಚ್ಚಿನ ಸಂಖ್ಯೆಯ ಬ್ಲಾಕ್‌ಗಳನ್ನು ಪುನರ್ವ್ಯವಸ್ಥಿತಗೊಳಿಸಬೇಕಾಗಿಲ್ಲ ಎಂಬುದು ಆಶಾದಾಯಕವಾದ ವಿಷಯ. ಪರ್ಯಾಯವಾಗಿ, ಕೆಲವು ಅವರ್ಗೀಕೃತ ಡಿಸ್ಕ್ ಬ್ಲಾಕ್‌ಗಳನ್ನು ಕೂಡಾ ಬಳಸಬಹುದು.

ಬಿ-ಟ್ರೀಯು ಈ ಎಲ್ಲಾ ಉಪಾಯಗಳನ್ನು ಬಳಸುತ್ತದೆ

ಬಿ-ಟ್ರೀಯು ಮೇಲಿನ ಎಲ್ಲಾ ಉಪಾಯಗಳನ್ನು ಬಳಸಿಕೊಳ್ಳುತ್ತದೆ. ಅದು ದಾಖಲೆಗಳನ್ನು ಕ್ರಮಾನುಗತವಾಗಿ ಆಚೀಚೆ ಸರಿಸಲು ಅನುಕೂಲವಾಗುವಂತೆ ವರ್ಗೀಕೃತ ವ್ಯವಸ್ಥೆಯಲ್ಲಿಟ್ಟಿರುತ್ತದೆ. ಅದು ಡಿಸ್ಕ್ ರೀಡ್‌ಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕಡಿಮೆಗೊಳಿಸುವ ಸಲುವಾಗಿ ಒಂದು ಶ್ರೇಣೀಕೃತ ಸೂಚಿಯನ್ನು ಬಳಸುತ್ತದೆ. ಈ ಸೂಚಿಯನ್ನು ಒಂದು ರಿಕರ್ಸಿವ್ ಅಲ್ಗಾರಿದಮ್‌ನ ಜತೆಗೆ ನಾಜೂಕಾಗಿ ಹೊಂದಿಸಲಾಗಿರುತ್ತದೆ. ಬಿ-ಟ್ರೀಯು ಅಳವಡಿಕೆಗಳು ಮತ್ತು ಅಳಿಸುವಿಕೆಗಳು ತ್ವರಿತಗತಿಯಲ್ಲಿ ನಡೆಯುವಂತೆ ಮಾಡಲು ಕೆಲಭಾಗ ಮಾತ್ರ ತುಂಬಿರುವ ಬ್ಲಾಕ್‌ಗಳ ಬಳಕೆಯನ್ನು ಮಾಡುತ್ತದೆ. ಜತೆಗೇ, ಒಂದು ಬಿ-ಟ್ರೀ ತನ್ನ ಇಂಟೀರಿಯರ್ ನೋಡ್‌ಗಳು ಅರ್ಧದಷ್ಟಾದರೂ ತುಂಬಿರುವುದೆಂದು ಖಾತ್ರಿಪಡಿಸಿಕೊಳ್ಳುವುದರ ಮೂಲಕ ಪೋಲಾಗುವುದನ್ನು ಕಡಿಮೆಗೊಳಿಸುತ್ತದೆ. ಒಂದು ಬಿ-ಟ್ರೀಯು ಅಂಕೆಯಿಲ್ಲದಷ್ಟು ಸಂಖ್ಯೆಯ ಅಳವಡಿಕೆಗಳು ಮತ್ತು ಅಳಿಸುವಿಕೆಗಳನ್ನು ನಿಭಾಯಿಸಬಲ್ಲುದು.

ತಾಂತ್ರಿಕ ವಿವರಣೆ

ಶಾಬ್ದಿಕ ನಿರ್ದಿಷ್ಟಾರ್ಥ[ಪರಿಭಾಷಾ ಶಾಸ್ತ್ರ]

ಬಿ-ಟ್ರೀಗಳಲ್ಲಿ ಬಳಸಲಾಗುವ ಪಾರಿಭಾಷಿಕ ಪದಗಳು ಸಾಹಿತ್ಯದಲ್ಲಿ ಮಾರ್ಪಾಡು ಹೊಂದುತ್ತಲೆ ಇರುತ್ತವೆ:

ದುರದೃಷ್ಟಾವಶಾತ್, ಬಿ-ಟ್ರೀಗಳ ಬಗೆಗಿನ ಸಾಹಿತ್ಯವು ಬಿ-ಟ್ರೀಗಳಿಗೆ ಸಂಬಂಧಿಸಿದ ಪದಗಳ ಬಗೆಗಿನ ಸಾಹಿತ್ಯವು ಏಕರೂಪತೆಯನ್ನು ಹೊಂದಿಲ್ಲ. (Folk & Zoellick 1992, p. 362)

Bayer & McCreight (1972), Comer (1979), ಮತ್ತಿತರರು ಬಿ-ಟ್ರೀಯ ಆರ್ಡರ್ ಅನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುತ್ತ ಒಂದು ನಾನ್-ರೂಟ್ ನೋಡ್‌ನಲ್ಲಿನ ಕೀಗಳ ಕನಿಷ್ಟ ಸಂಖ್ಯೆ ಎಂದಿದ್ದಾರೆ. Folk & Zoellick (1992) ಸೂಚಿಸುವಂತೆ ಪರಿಭಾಷೆಯು ಸಂದಿಗ್ಧತೆಯಿಂದ ಕೂಡಿದೆ, ಎಕೆಂದರೆ ಕೀಗಳ ಗರಿಷ್ಟ ಸಂಖ್ಯೆಯನ್ನು ಸ್ಪಷ್ಟಪಡಿಸಲಾಗಿಲ್ಲ. ಒಂದು ಆರ್ಡರ್ 3 ಬಿ-ಟ್ರೀಯು ಗರಿಷ್ಟ 6 ಇಲ್ಲವೇ 7 ಕೀಗಳನ್ನು ಹೊಂದಿರಬಹುದು. Knuth (1993b) ಅಗುವ ತೊಂದರೆಯನ್ನು ತಪ್ಪಿಸಿಕೊಳ್ಳಲು ಆರ್ಡರ್ ಅನ್ನು ಚಿಲ್ಡ್ರನ್‍ಗಳ ಗರಿಷ್ಟ ಸಂಖ್ಯೆಯೆಂದು ವ್ಯಾಖ್ಯಾನಿಸುತ್ತದೆ (ಇದು ಕೀಗಳ ಗರಿಷ್ಟ ಸಂಖ್ಯೆಗಿಂತ ಒಂದು ಹೆಚ್ಚಾಗಿರುತ್ತದೆ).

ಲೀಫ್  ಎಂಬ ಪದವೂ ಕೂಡ ಅಸಮಂಜಸತೆಯಿಂದ ಕೂಡಿದೆ. Bayer & McCreight (1972) ಲೀಫ್ ಮಟ್ಟವನ್ನು ಕೀಗಳಲ್ಲಿ ಅತ್ಯಂತ ಕೆಳಗಿನ ಮಟ್ಟವೆಂದು ಪರಿಗಣಿಸಿದ್ದರು, ಅದರೆ Knuth (1993b) ಲೀಫ್ ಮಟ್ಟವನ್ನು ಅತ್ಯಂತ ಕೆಳಮಟ್ಟದ ಕೀಗಳಿಗಿಂತ ಒಂದು ಮಟ್ಟ ಮೆಲಿರುವುದಾಗಿ ಪರಿಗಣಿಸಿದ್ದರು. (Folk & Zoellick 1992, p. 363) ಇದನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಲು ಹಲವಾರು ಆಯ್ಕೆಗಳು ಸಾಧ್ಯವಿವೆ. ಕೆಲವು ವಿನ್ಯಾಸಗಳಲ್ಲಿ, ಲೀಫ್‌ಗಳು ಸಂಪೂರ್ಣ ದತ್ತಾಂಶ ದಾಖಲೆಗಳನ್ನು ಹಿಡಿದಿಟ್ಟುಕೊಂದಿರಬಹುದು; ಇನ್ನು ಕೆಲವು ವಿನ್ಯಾಸಗಳಲ್ಲಿ ಲೀವ್ಸ್ ದತ್ತಾಂಶ ದಾಖಲೆಗಳಿಗೆ ಬರೆ ಪಾಯಿಂಟರ್ಸ್ ಅನ್ನು ಮಾತ್ರ ಹೊಂದಿರಬಹುದು. ಈ ಆಯ್ಕೆಗಳು ಬಿ-ಟ್ರೀಯ ಕಲ್ಪನೆಗೆ ಆಧಾರತತ್ವಗಳೇನಲ್ಲ. Bayer & McCreight (1972)ರವರು ಈ ವಿಷಯವನ್ನು ತಪ್ಪಿಸುತ್ತ ಒಂದು ಇಂಡೆಕ್ಸ್ ಎಲಿಮೆಂಟ್ ಎಂಬುದು $(x,a)$ನ (ಭೌತಿಕವಾಗಿ ಪಾರ್ಶ್ವದಲ್ಲಿರುವ) ಜೋಡಿಯಾಗಿದ್ದು, ಇಲ್ಲಿ $x$ ಕೀ ಅಗಿರುವುದು ಮತ್ತು $a$ ಎಂಬುದು ಸಂಬಂಧಿಸಿದ ಯಾವುದೋ ಮಾಹಿತಿಯಾಗಿದೆ.  ಸಂಬಂಧಿತ ಮಾಹಿತಿಯು ಒಂದು ರೆಕಾರ್ಡ್ ಇಲ್ಲವೆ ಹಲವು ರೆಕಾರ್ಡ್‌ಗಳಿಗೆ ರ‍್ಯಾಂಡಮ್ ಆಕ್ಸೆಸ್‌ನಲ್ಲಿ ಪಾಯಿಂಟರ್ ಆಗಿರಬಹುದು, ಆದರೆ  ಏನಾಗಿರುವುದೆಂಬುದು ನಿಜವಾಗಿ ಮಹತ್ವದ ವಿಷಯವಲ್ಲ. Bayer & McCreight (1972)ರ ಹೇಳಿಕೆಯ ಪ್ರಕಾರ, " ಸಂಬಂಧಿತ ಮಾಹಿತಿಯು ಈ ಲೇಖನಕ್ಕೆ ಯಾವುದೇ ಹಿತಾರ್ಥವನ್ನು ಹೊಂದಿಲ್ಲ."

ಇಲ್ಲಿ ಕೆಲವು ದುರದೃಷ್ಟಪೂರ್ಣ ಅಯ್ಕೆಗಳೂ ಇವೆ, ಉದಾಹರಣೆಗೆ $k$ ಅನ್ನು ಕೀಗಳ ಸಂಖ್ಯೆಯೆಂದು ಪರಿಗಣಿಸಿ ಗೊಂದಲವುಂಟಾಗುವ ಸಾಧ್ಯತೆಯಿದ್ದರೂ ಚಿಲ್ಡ್ರನ್‌ಗಳ ಸಂಖ್ಯೆಯನ್ನು ಪ್ರತಿನಿಧಿಸಲು ವೇರಿಯಬಲ್ $k$ನ ಬಳಕೆ ಮಾಡಲಾಗುವುದು.

ಸರಳಗೊಳಿಸುವ ಸಲುವಾಗಿ, ಹೆಚ್ಚಿನ ಆಥರ್‌‍ಗಳು ಒಂದು ನೋಡ್‌ನೊಳಗೆ ಸರಿಹೊಂದುವ ಕೀಗಳ ಸಂಖ್ಯೆಯು ನಿರ್ದಿಷ್ಟವಾಗಿರುವುದೆಂದು ಭಾವಿಸುತ್ತಾರೆ.  ಕೀಯ ಗಾತ್ರ ಮತ್ತು ನೋಡ್‌ನ ಗಾತ್ರವು ನಿರ್ದಿಷ್ಟವಾಗಿರುವುದೆಂಬುದು ಮೂಲ ಭಾವನೆ. ಪ್ರಾಯೋಗಿಕವಾಗಿ, ವ್ಯತ್ಯಾಸಸಾಧ್ಯ ಉದ್ದಗಳ ಕೀಗಳನ್ನು ಬಳಸಬಹುದು. (Folk & Zoellick 1992, p. 379)

ವ್ಯಾಖ್ಯಾನ

ಆರ್ಡರ್ m ನ ಬಿ-ಟ್ರೀಯೊಂದು (ಪ್ರತಿ ನೋಡ್‌ಗೂ ಗರಿಷ್ಟ ಸಂಖ್ಯೆಯ ಚಿಲ್ಡ್ರನ್) ಈ ಕೆಳಗಿನ ಲಕ್ಷಣಗಳಿಗೆ ಸರಿಹೊಂದುವ ಬಿ-ಟ್ರೀಯಾಗಿದೆ:

1. ಪ್ರತಿ ನೋಡ್‌ನಲ್ಲಿಯೂ ಅಧಿಕತಮ m ಚಿಲ್ಡ್ರನ್ ಇರಬೇಕು.
2. ಪ್ರತಿ ನೋಡ್ (ರೂಟ್ ಮತ್ತು ಲೀವ್ಸ್ ಹೊರತುಪಡಿಸಿ) ಕನಿಷ್ಟವೆಂದರೂ m⁄2 ಚಿಲ್ಡ್ರನ್ ಅನ್ನು ಹೊಂದಿದೆ.
3. ರೂಟ್ ಒಂದು ಲೀಫ್ ನೋಡ್ ಆಗಿರದಿದ್ದ ಪಕ್ಷದಲ್ಲಿ ಕನಿಷ್ತ ಎರಡು ಚಿಲ್ಡ್ರನ್ ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ.
4. ಎಲ್ಲಾ ಲೀವ್ಸ್ ಒಂದೇ ಮಟ್ಟದಲ್ಲಿ ಕಂಡುಬರುತ್ತವೆ ಮತ್ತು ಮಾಹಿತಿಯನ್ನು ಒಯ್ಯುತ್ತವೆ.
5. k ಚಿಲ್ಡ್ರನ್ ಅನ್ನು ಹೊಂದಿರುವ ಒಂದು ನಾನ್-ಲೀಫ್ ನೋಡ್ k −1 ಕೀಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ.

ಪ್ರತಿ ಇಂಟರ್ನಲ್ ನೋಡ್‌ನ ಘಟಕಗಳು ಅದರ ಸಬ್‌ಟ್ರೀಗಳನ್ನು ವಿಭಾಗಿಸುವ ಸಪರೇಶನ್ ವ್ಯಾಲ್ಯೂಗಳಂತೆ ವರ್ತಿಸುತ್ತವೆ. ಉದಾಹರಣೆಗೆ, ಒಂದು ಇಂಟರ್ನಲ್ ನೋಡ್‌ನಲ್ಲಿ ಮೂರು ಚೈಲ್ಡ್ ನೋಡ್‌ಗಳಿದ್ದರೆ (ಅಥವಾ ಸಬ್‌ಟ್ರೀಗಳು), ಅದು a ₁ ಮತ್ತು a ₂ ಎಂಬ ಎರಡು ಸಪರೇಶನ್ ವ್ಯಾಲ್ಯೂಗಳು ಅಥವಾ ಘಟಕಗಳನ್ನು ಹೊಂದಿರಬೇಕು. ಎಡತುದಿಯಲ್ಲಿರುವ ಸಬ್‌ಟ್ರೀಯ ಎಲ್ಲಾ ವ್ಯಾಲ್ಯೂಗಳೂ a ₁ಗಿಂತ ಕಡಿಮೆಯಿರುವುದು, ಮಧ್ಯದಲ್ಲಿರುವ ಸಬ್‌ಟ್ರೀಯ ಎಲ್ಲಾ ವ್ಯಾಲ್ಯೂಗಳೂ a ₁ ಮತ್ತು a ₂ ನಡುವೆ ಇರುವುದು, ಮತ್ತು ಅತ್ಯಂತ ಬಲಭಾಗದಲ್ಲಿರುವ ಸಬ್‌ಟ್ರೀಯ ಎಲ್ಲಾ ವ್ಯಾಲ್ಯೂಗಳೂ a ₂ಗಿಂತ ಹೆಚ್ಚಾಗಿರುವುದು.

ಬಿ-ಟೀಯೊಂದರ ಇಂಟರ್ನಲ್ ನೋಡ್‌ಗಳು - ಲೀಫ್ ನೋಡ್‌ಗಳಲ್ಲದ ನೋಡ್‌ಗಳು - ಸಾಮಾನ್ಯವಾಗಿ ಘಟಕಗಳು ಮತ್ತು ಚೈಲ್ಡ್ ಪಾಯಿಂಟರ್‌ಗಳ ವ್ಯವಸ್ಥಿತ ಗುಂಪುಗಳಾಗಿ ಪ್ರತಿನಿಧಿಸಲ್ಪಡುತ್ತವೆ. ಪ್ರತಿ ಇಂಟರ್ನಲ್ ನೋಡ್ ಗರಿಷ್ಟ U ಚಿಲ್ಡನ್ ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ ಮತ್ತು – ರೂಟ್ ಅಲ್ಲದೆ – ಕನಿಷ್ಟ L ಚಿಲ್ಡ್ರನ್ ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ. ರೂಟ್ ಅಲ್ಲದ ಎಲ್ಲಾ ಇಂಟರ್ನಲ್ ನೋಡ್‌ಗಳಿಗೆ, ಘಟಕಗಳ ಸಂಖ್ಯೆಯು ಚೈಲ್ಡ್ ಪಾಯಿಂಟರ್‌ಗಳ ಸಂಖ್ಯೆಗಿಂತ ಒಂದು ಕಡಿಮೆಯಿರುತ್ತದೆ; ಘಟಕಗಳ ಸಂಖ್ಯೆಯು L −1 ಮತ್ತು U −1ಗಳ ನಡುವಿನಲ್ಲಿರುತ್ತದೆ. U ಗಳ ಸಂಖ್ಯೆಯು 2L ಅಥವಾ 2L −1ನಷ್ಟಿರಬೇಕು; ಹೀಗಾಗಿ ಪ್ರತಿಯೊಂದು ಇಂಟರ್ನಲ್ ನೋಡ್ ಅರ್ಧದಷ್ಟಾದರೂ ತುಂಬಿರಬೇಕು. U ಮತ್ತು L ಗಳ ನಡುವಿನ ಈ ಸಂಬಂಧದ ಅರ್ಥವೇನೆಂದರೆ, ಎರಡು ಅರ್ಧ-ತುಂಬಿದ ನೋಡ್‌ಗಳನ್ನು ಕೂಡಿಸಿ ಒಂದು ಲೀಗಲ್ ನೋಡ್ ಅನ್ನು ಮಾಡಬಹುದು, ಮತ್ತು ಒಂದು ಫುಲ್ ನೋಡ್ ಅನ್ನು ಎರಡು ಲೀಗಲ್ ನೋಡ್‌ಗಳಾಗಿ ವಿಭಾಗಿಸಬಹುದು (ಪೇರೆಂಟ್‌ನೊಳಗೆ ಒಂದು ಘಟಕವನ್ನು ಮೇಲೆ ನುಗ್ಗಿಸುವಷ್ತು ಸ್ಥಳಾವಕಾಶವಿದ್ದಲ್ಲಿ). ಈ ಲಕ್ಷಣಗಳಿಂದಾಗಿ ಬಿ-ಟ್ರೀಯಲ್ಲಿ ಹೊಸ ವ್ಯಾಲ್ಯೂಗಳನ್ನು ಸೇರಿಸುವುದು ಇಲ್ಲವೇ ಅಳಿಸಿಹಾಕುವುದು ಸಾಧ್ಯವಾಗುತ್ತದೆ ಮತ್ತು ಬಿ-ಟ್ರೀ ಲಕ್ಷಣಗಳನ್ನು ಉಳಿಸಿಕೊಳ್ಳಲು ಟ್ರೀಯನ್ನು ಹೊಂದಿಸಲು ಸಾಧ್ಯವಾಗುತ್ತದೆ.

ಲೀಫ್ ನೋಡ್‌ಗಳೂ ಕೂಡಾ ಘಟಕಗಳ ಸಂಖ್ಯೆಯ ಬಗ್ಗೆ ಇದೇ ರೀತಿಯ ನಿರ್ಬಂಧಗಳಿದ್ದರೂ ಕೂಡಾ ಅವು ಚಿಲ್ಡ್ರನ್ ಮತ್ತು ಚೈಲ್ಡ್ ಪಾಯಿಂಟರ್‌ಗಳನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲ.

ರೂಟ್ ನೋಡ್ ಇನ್ನೂ ಚಿಲ್ಡ್ರನ್ ಸಂಖ್ಯೆಯಲ್ಲಿ ಗರಿಷ್ಟ ಮಿತಿಯನ್ನು ಹೊಂದಿರುವುದು, ಆದರೆ ಯಾವುದೇ ಕನಿಷ್ಟ ಮಿತಿಯು ಇರುವುದಿಲ್ಲ. ಉದಾಹರಣೆಗೆ, ಇಡೀ ಟ್ರೀಯಲ್ಲಿ L −1ಕ್ಕಿಂತ ಕಡಿಮೆ ಘಟಕಗಳಿದ್ದಾಗ, ರೂಟ್ ಟ್ರೀಯ ಏಕೈಕ ನೋಡ್ ಆಗಿರುವುದು, ಮತ್ತು ಅದು ಯಾವುದೇ ಚಿಲ್ಡ್ರನ್ ಅನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲ.

n +1ರಷ್ಟು ಆಳದ ಒಂದು ಬಿ-ಟ್ರೀಯು n ರಷ್ಟು ಆಳದ ಬಿ-ಟ್ರೀಗಿಂತ U  ಪಟ್ಟು ಹೆಚ್ಚು ಅಂಶಗಳನ್ನು ಹಿಡಿದಿಟ್ಟುಕೊಳ್ಳಬಲ್ಲದು, ಆದರೆ ಹುಡುಕಾಟ, ಅಳವಡಿಸುವಿಕೆ, ಮತ್ತು ಅಳಿಸುವಿಕೆಗಳ ಕಾರ್ಯಾಚರಣೆಗಳ ವೆಚ್ಚವು ಟ್ರೀಯ ಆಳದ ಜತೆಗೇ ಹೆಚ್ಚುತ್ತ ಹೋಗುತ್ತದೆ.  ಯಾವುದೇ ಸಂತುಲಿತ ಟ್ರೀಯಲ್ಲಿ, ವೆಚ್ಚವು ಘಟಕಗಳ ಸಂಖ್ಯೆಗಿಂತ ಕಡಿಮೆ ವೇಗದಲ್ಲಿ ಬೆಳೆಯುತ್ತ ಹೋಗುವುದು.

ಕೆಲವು ಸಂತುಲಿತ ಟ್ರೀಗಳು ವ್ಯಾಲ್ಯೂಗಳನ್ನು ತಮ್ಮ ಲೀಫ್ ನೋಡ್‌ಗಳಲ್ಲಿ ಮಾತ್ರ ಸಂಗ್ರಹಿಸುತ್ತವೆ, ಮತ್ತು ಇದರಿಂದಾಗಿ ಲೀಫ್ ನೋಡ್‌ಗಳು ಮತ್ತು ಇಂಟರ್ನಲ್ ನೋಡ್‌ಗಳಿಗೆ ಬೇರೆಬೇರೆ ರೀತಿಯ ನೋಡ್‍ಗಳನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಬಿ-ಟ್ರೀಗಳು ಟ್ರೀಯ ಪ್ರತಿಯೊಂದು ನೋಡ್‌ನಲ್ಲಿಯೂ ವ್ಯಾಲ್ಯೂಗಳನ್ನಿಟ್ಟಿರುತ್ತವೆ, ಮತ್ತು ಬಹುಶಃ ಎಲ್ಲಾ ನೋಡ್‍ಗಳಲ್ಲಿಯೂ ಇದೇ ರಚನಾಕ್ರಮವನ್ನು ಬಳಸಬಹುದು. ಅದರೆ, ಲೀಫ್ ನೋಡ್‌ಗಳು ಚಿಲ್ಡ್ರನ್ ಅನ್ನು ಖಚಿತವಾಗಿ ಹೊಂದಿಲ್ಲದಿರುವುದರಿಂದ, ಬಿ-ಟ್ರೀಗಳಲ್ಲಿ ಲೀಫ್ ನೋಡ್‌ಗಳಿಗಾಗಿಯೇ ವಿಶೇಷವಾದ ರಚನಾಕ್ರಮವು ಕಾರ್ಯನಿರ್ವಹಣೆಯನ್ನು ಉತ್ತಮಗೊಳಿಸುವುದು.

ಬೆಸ್ಟ್ ಕೇಸ್ ಮತ್ತು ವರ್ಸ್ಟ್ ಕೇಸ್ ಎತ್ತರಗಳು

ಬಿ-ಟ್ರೀಯ ಒಂದು ಉತ್ತಮ ನಿದರ್ಶನದ ಉದ್ದವೆಂದರೆ:

$\log _{m}n.\$

ಬಿ-ಟ್ರೀಯ ಒಂದು ಕಳಪೆ ನಿದರ್ಶನದ ಉದ್ದವೆಂದರೆ:

$\log _{m/2}n\$

ಇದರಲ್ಲಿ $m$ ಎಂಬುದು ಒಂದು ನೋಡ್ ಹೊಂದಬಹುದಾದಂತಹ ಗರಿಷ್ಟ ಸಂಖ್ಯೆ ಚಿಲ್ಡ್ರನ್ ನೋಡ್‌ಗಳನ್ನು ಸೂಚಿಸುತ್ತದೆ.

ಆಲ್ಗಾರಿದಮ್‌ಗಳು

ಎಚ್ಚರಿಕೆ : ಈ ಕೆಳಗಿನ ಚರ್ಚೆಯು "ಎಲಿಮೆಂಟ್(ಘಟಕ)", "ವ್ಯಾಲ್ಯೂ", "ಕೀ", "ಸಪರೇಟರ್", ಮತ್ತು "ಸಪರೇಶನ್ ವ್ಯಾಲ್ಯೂ" - ಇವೆಲ್ಲವನ್ನೂ ಒಂದೇ ಅರ್ಥದಲ್ಲ್ಲಿ ಬಳಸುತ್ತದೆ. ಪದಗಳನ್ನು ಸ್ಪಷ್ಟವಾಗಿ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿಲ್ಲ. ರೂಟ್ ಮತ್ತು ಲೀವ್ಸ್‌ಗಳಲ್ಲಿ ಕೆಲವು ಸೂಕ್ಷ್ಮವಾದ ವಿವಾದಾಂಶಗಳಿವೆ.

ಹುಡುಕಾಟ

ಹುಡುಕಾಟವು ಒಂದು ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀಯನ್ನು ಹುಡುಕುವುದಕ್ಕೆ ಸಮಾನವಾಗಿದೆ. ರೂಟ್‌ನಲ್ಲಿ ಆರಂಭಿಸಿ, ಟ್ರೀಯನ್ನು ರಿಕರ್ಸಿವ್ ಆಗಿ ಮೇಲಿನಿಂದ ಕೆಳಗಿನವರೆಗೂ ಕ್ರಮಿಸಲಾಗುತ್ತದೆ. ಪ್ರತಿಯೊಂದು ಮಟ್ಟದಲ್ಲಿಯೂ ಸರ್ಚ್ ಚೈಲ್ಡ್ ಪಾಯಿಂಟರ್ ಅನ್ನು ಆಯ್ಕೆ ಮಾಡಿಕೊಳ್ಳುತ್ತದೆ, ಮತ್ತು ಈ ಪಾಯಿಂಟರ್‌ನ ಸಪರೇಶನ್ ವ್ಯಾಲ್ಯೂಗಳು ಸರ್ಚ್ ವ್ಯಾಲ್ಯೂನ ಎರಡೂ ಬದಿಗಳಲ್ಲಿರುತ್ತವೆ.

ನೋಡ್‌ಗಳೊಳಗಿನ ಸಪರೇಶನ್ ವ್ಯಾಲ್ಯೂಗಳು ಮತ್ತು ಆಸಕ್ತಿಯ ಚೈಲ್ಡ್ ಟ್ರೀಯನ್ನು ಹುಡುಕಲು ನೋಡ್‌ಗಳೊಳಗೆ ಬೈನರಿ ಸರ್ಚ್ ಅನ್ನು ವಿಶೇಷವಾಗಿ (ಆದರೆ ಅವಶ್ಯವಾಗಿ ಅಲ್ಲ) ಬಳಸಲಾಗುತ್ತದೆ.

ಅಳವಡಿಸುವಿಕೆ

ಪ್ರತಿಯೊಂದು ಪುನರಾವರ್ತನೆಯೊಂದಿಗೆ ಒಂದು ಬಿ-ಟ್ರೀ ಒಳಸೇರಿಸುವಿಕೆಯ ಉದಾಹರಣೆ.

ಎಲ್ಲಾ ಅಳವಡಿಸುವಿಕೆಗಳೂ ಒಂದು ಲೀಫ್ ನೋಡ್‌ನಲ್ಲಿ ಆರಂಭವಾಗುತ್ತವೆ. ಹೊಸ ಎಲಿಮೆಂಟ್(ಘಟಕ) ಅನ್ನು ಅಳವಡಿಸುವುದು

ಟ್ರೀಯನ್ನು ಹುಡುಕಿ ಹೊಸ ಘಟಕವನ್ನು ಸೇರಿಸಬೇಕಾಗಿರುವ ಲೀಫ್ ಅನ್ನು ಗುರುತಿಸಿರಿ ಕೆಳಗಿನ ವಿಧಾನವನ್ನು ಅನುಸರಿಸುವುದರ ಮೂಲಕ ಆ ನೋಡ್‌ಗೆ ಹೊಸ ಘಟಕವನ್ನು ಸೇರಿಸಿರಿ:

1. ನೋಡ್ ಗರಿಷ್ಟ ನ್ಯಾಯಸಮ್ಮತ ಸಂಖ್ಯೆಗಿಂತ ಕಡಿಮೆ ಘಟಕಗಳನ್ನು ಹೊಂದಿದ್ದಲ್ಲಿ, ಆಗ ಹೊಸ ಘಟಕಕ್ಕೆ ಜಾಗವಿದೆ ಎಂದಾಗುವುದು. ನೋಡ್‌ನ ಘಟಕಗಳು ಕ್ರಮಬದ್ಧವಾಗಿರುವಂತೆ ನೋಡಿಕೊಂಡು ಹೊಸ ಘಟಕವನ್ನು ಒಳಸೇರಿಸಿರಿ.
2. ನೋಡ್ ಸಂಪೂರ್ಣ ತುಂಬಿದ್ದಲ್ಲಿ, ಅದನ್ನು ಸರಿಯಾಗಿ ಎರಡು ನೋಡ್‌ಗಳಾಗಿ ವಿಭಾಗಿಸಿರಿ.
   1. ಲೀಫ್‌ನ ಘಟಕಗಳು ಮತ್ತು ಹೊಸ ಘಟಕದ ನಡುವಿನಿಂದ ಒಂದು ಮೀಡಿಯನ್ ಅನ್ನು ಆಯ್ಕೆ ಮಾಡಲಾಗುವುದು.
   2. ಮೀಡಿಯನ್‌ಗಿಂತ ಕಡಿಮೆ ಇರುವ ವ್ಯಾಲ್ಯೂಗಳನ್ನು ಹೊಸ ಎಡಬದಿಯ ನೋಡ್‌ನಲ್ಲಿ ಹಾಕಲಾಗುವುದು ಮತ್ತು ಮೀಡಿಯನ್‌ಗಿಂತ ಹೆಚ್ಚಿನ ವ್ಯಾಲ್ಯೂಗಳನ್ನು ಹೊಸ ಬಲಬದಿಯ ನೋಡ್‌ನಲ್ಲಿ ಹಾಕಲಾಗುವುದು ಮತ್ತು ಮೀಡಿಯನ್ ವಿಭಜಕ ವ್ಯಾಲ್ಯೂ ಆಗಿ ವರ್ತಿಸುವುದು.
   3. ಸಪರೇಶನ್ ವ್ಯಾಲ್ಯೂವನ್ನು ನೋಡ್‌ನ ಪೇರೆಂಟ್‌ಗೆ ಸೇರಿಸಿರಿ, ಇದರಿಂದ ಅದು ವಿಭಜಿತವಾಗುವುದು. ನೋಡ್‌ಗೆ ಪೇರೆಂಟ್ ಇಲ್ಲದಿದ್ದಲ್ಲಿ (ಎಂದರೆ, ನೋಡ್ ಒಂದು ರೂಟ್ ಆಗಿದ್ದಲ್ಲಿ), ಈ ನೋಡ್‌ನ ಮೇಲ್ಭಾಗದಲ್ಲಿ ಒಂದು ಹೊಸ ರೂಟ್ ಅನ್ನು ರಚಿಸಿರಿ (ಟ್ರೀಯ ಎತ್ತರವನ್ನು ಹೆಚ್ಚಿಸುತ್ತ).

ಈ ವಿಭಜನೆಯು ಮೆಲಕ್ಕೆ ರೂಟ್‌ನವರೆಗೂ ಹೋದಲ್ಲಿ, ಅದು ಒಂದು ಸಿಂಗಲ್ ಸಪರೇಟರ್ ವ್ಯಾಲ್ಯೂ ಮತ್ತು ಎರಡು ಚಿಲ್ಡ್ರನ್ ಇರುವ ಹೊಸ ರೂಟ್ ಒಂದನ್ನು ನಿರ್ಮಿಸುತ್ತದೆ, ಮತ್ತು ಈ ಕಾರಣದಿಂದಾಗಿ ರೂಟ್‌ಗೆ ಇಂಟರ್ನಲ್ ನೋಡ್‌ಗಳ ಗಾತ್ರದ ಕಡಿಮೆ ಪರಿಮಿತಿಯು ಅನ್ವಯಿಸುವುದಿಲ್ಲ. ಪ್ರತಿ ನೋಡ್‌ಗೆ ಇರಬೇಕಾದ ಘಟಕಗಳ ಗರಿಷ್ಟ ಸಂಖ್ಯೆ U −1. ಒಂದು ನೋಡ್ ವಿಭಜಿತವಾದಾಗ, ಒಂದು ಘಟಕವು ಪೇರೆಂಟ್‌ಗೆ ಹೋಗಿ ಸೇರಿಕೊಳ್ಳುವುದು, ಆದರೆ ಒಂದು ಘಟಕವನ್ನು ಸೇರಿಸಲಾಗುವುದು ಆದ್ದರಿಂದ ಗರಿಷ್ಟ ಸಂಖ್ಯೆ U −1 ನ ಘಟಕಗಳನ್ನು ಎರಡು ಲೀಗಲ್ ನೋಡ್‌ಗಳನ್ನಾಗಿ ವಿಭಜಿಸುವುದು ಸಾಧ್ಯವಾಗಬೇಕು. ಈ ಸಂಖ್ಯೆಯು ಬೆಸಸಂಖ್ಯೆಯಾಗಿದ್ದಲ್ಲಿ, ಆಗ U =2L ಮತ್ತು ಹೊಸ ನೋಡ್‌ಗಳಲ್ಲಿ ಒಂದು ನೋಡ್ (U −2)/2 = L −1 ಘಟಕಗಳನ್ನು ಹೊಂದಿರುವುದು, ಅದ್ದರಿಂದ ಇದು ಒಂದು ಲೀಗಲ್ ನೋಡ್ ಆಗಿರುವುದು, ಮತ್ತು ಇನ್ನೊಂದು ನೋಡ್ ಒಂದು ಹೆಚ್ಚಿಗೆ ಘಟಕವನ್ನು ಹೊಂದಿರುವುದರಿಂದ ಅದು ಕೂಡ ಲೀಗಲ್ ಆಗಿರುವುದು. ಅಕಸ್ಮಾತ್ U −1 ಸರಿಸಂಖ್ಯೆಯಾಗಿದ್ದಲ್ಲಿ, ಆಗ U =2L −1, ಅದ್ದರಿಂದ ನೋಡ್‌ನಲ್ಲಿ 2L −2 ಘಟಕಗಳಿರುವುವು. ಈ ಸಂಖ್ಯೆಯ ಅರ್ಧಭಾಗವು L −೧ ಆಗಿದ್ದು, ಇದು ಪ್ರತಿ ನೋಡ್‌ಗೆ ಸಮ್ಮತಿಸಲಗಿರುವ ಘಟಕಗಳ ಕನಿಷ್ಟ ಸಂಖ್ಯೆಯಾಗಿದೆ.

ಒಂದು ಸುಧಾರಿತ ಅಲ್ಗಾರಿದಮ್ ರೂಟ್‌ನಿಂದ ಇನ್‌ಸರ್ಶನ್ ಆಗಬೇಕಿರುವ ನೋಡ್‌ಗೆ ಒಂದು ಸಿಂಗಲ್ ಪಾಸ್ ಅನ್ನು ಬೆಂಬಲಿಸುತ್ತದೆ, ಮತ್ತು ಇಲ್ಲಿ ದಾರಿಯಲ್ಲಿ ಎದುರಾದ ಎಲ್ಲ ಫುಲ್ ನೋಡ್‌ಗಳನ್ನು ವಿಭಜಿಸುತ್ತ ಮುಂದೆ ಹೋಗಲಾಗುತ್ತದೆ. ಇದರಿಂದಾಗಿ ಪೇರೆಂಟ್ ನೋಡ್‌ಗಳನ್ನು ವಾಪಾಸು ಮೆಮೊರಿಗೆ ತೆಗೆದುಕೊಂಡು ಬರಬೇಕಾಗಿಲ್ಲ, ಏಕೆಂದರೆ ನೋಡ್‌ಗಳು ಸೆಕೆಂಡರಿ ಸ್ಟೋರೇಜ್‌ನಲ್ಲಿದ್ದರೆ ಇದು ಬಹಳ ದುಬಾರಿಯಾಗಬಹುದು. ಅದರೆ, ಈ ಸುಧಾರಿತ ಅಲ್ಗರಿದಮ್ ಅನ್ನು ಬಳಸಲು, ನಾವು ಒಂದು ಘಟಕವನ್ನು ಪೇರೆಂಟ್‍ಗೆ ಕಳುಹಿಸಿ ಉಳಿದ U −2 ಘಟಕಗಳನ್ನು ಎರಡು ಲೀಗಲ್ ನೋಡ್‌ಗಳಾಗಿ, ಹೊಸ ಘಟಕವನ್ನು ಸೇರಿಸದೆಯೆ ವಿಭಜಿಸಬೇಕಾಗುತ್ತದೆ. ಇದಕ್ಕಾಗಿ U = 2L −1ಗಿಂತ U = 2L ಅವಶ್ಯಕವಾಗಿದೆ, ಹಾಗೂ ಇದು ಕೆಲವು ಪಠ್ಯಪುಸ್ತಕಗಳಲ್ಲಿ ಬಿ-ಟ್ರೀಯನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಲು ಅವಶ್ಯಕತೆಯನ್ನಾಗಿ ವಿಧಿಸಲು ಕಾರಣವಾಗಿದೆ.

ಅಳಿಸುವುದು

ಬಿ-ಟ್ರೀಯಿಂದ ಅಳಿಸಿಹಾಕುವುದನ್ನು ಮಾಡಲು ಎರಡು ಜನಪ್ರಿಯ ತಂತ್ರಗಳು ಇವೆ.

• ಅಂಶವನ್ನು ಪತ್ತೆಹಚ್ಚಿ ಡಿಲಿಟ್(ಅಳಿಸಿ) ಮಾಡಿ, ನಂತರ ಟ್ರೀಯನ್ನು ಅದರ ಇನ್‌ವೇರಿಯೆಂಟ್ಸ್ ಅನ್ನು ಮತ್ತೆ ಪಡೆದುಕೊಳ್ಳುವಂತೆ ಪುನರ್ರಚನೆ ಮಾಡಿ.

ಅಥವಾ

• ಟ್ರೀಯ ಕೆಳಗಿನವರೆಗೆ ಒಂದು ಸಿಂಗಲ್ ಪಾಸ್ ಅನ್ನು ಮಾಡಿರಿ, ಅದರೆ ಒಂದು ನೋಡ್‌ಗೆ ಭೇಟಿ ನೀಡುವ ಮೊದಲು, ಟ್ರೀಯನ್ನು ಪುನರ್ರಚನೆ ಮಾಡಿ, ಏಕೆಂದರೆ ಇದರಿಂದ ಡಿಲಿಟ್ ಮಾಡಬೇಕಾಗಿರುವ ಕೀಯನ್ನು ನೇರವಾಗಿ ಎದುರಿಸಬಹುದು ಮತ್ತು ಮುಂದೆ ಯಾವ ಪುನರ್ರಚನೆಗೂ ಆಸ್ಪದ ನೀಡದೆಯೆ ಅದನ್ನು ಡಿಲಿಟ್ ಮಾಡಬಹುದು.

ಕೆಳಗಿರುವ ಅಲ್ಗಾರಿದಮ್ ಈ ಹಿಂದಿನ ತಂತ್ರವನ್ನು ಬಳಸುತ್ತದೆ.

ಒಂದು ಘಟಕವನ್ನು ಡಿಲಿಟ್ ಮಾಡುವಾಗ ಎರಡು ವಿಶೇಷ ಸಂದರ್ಭಗಳನ್ನು ಪರಿಗಣಿಸಬೇಕಾಗುತ್ತದೆ:

1. ಇಂಟರ್ನಲ್ ನೋಡ್‌ನಲ್ಲಿರುವ ಘಟಕವು ಅದರ ಚೈಲ್ಡ್ ನೋಡ್‌ಗಳ ಸಪರೇಟರ್ ಆಗಿರಬಹುದು
2. ಒಂದು ಘಟಕವನ್ನು ಡಿಲಿಟ್ ಮಾಡುವುದರಿಂದ ಅದರ ನೋಡ್ ಅನ್ನು ಘಟಕಗಳು ಮತ್ತು ಚಿಲ್ಡ್ರನ್‌ಗಳ ಕನಿಷ್ಟ ಸಂಖ್ಯೆಯಡಿಗೆ ಹಾಕಬಹುದು.

ಈ ಎರಡೂ ಸನ್ನಿವೇಶಗಳನ್ನು ಒಂದಾದಮೇಲೊಂದರಂತೆ ನಿರ್ವಹಿಸಲಾಗುವುದು.

ಲೀಫ್ ನೋಡ್ ಒಂದರಿಂದ ಡಿಲಿಶನ್

• ಡಿಲಿಟ್ ಮಾಡಬೇಕಿರುವ ವ್ಯಾಲ್ಯೂಗಾಗಿ ಶೋಧ ನಡೆಸಿ.
• ಆ ವ್ಯಾಲ್ಯೂ ಲೀಫ್ ನೋಡ್‌ನಲ್ಲಿದ್ದರೆ, ಅದನ್ನು ನೋಡ್‌ನಿಂದ ಸರಳವಾಗಿ ಡಿಲಿಟ್ ಮಾಡಬಹುದು,
• ಅಂಡರ್‌ಫ್ಲೋ ನಡೆದಲ್ಲಿ, ಒಂದು ಕೀ ಅನ್ನು ಟ್ರ್ಯಾನ್ಸ್‌ಫರ್ ಮಾಡುವ ಸಲುವಾಗಿ ಇಲ್ಲವೇ ಸಿಬ್ಲಿಂಗ್‌ಗಳನ್ನು ಒಟ್ಟಿಗೆ ಜೋಡಿಸುವ ಸಲುವಾಗಿ ಸಿಬ್ಲಿಂಗ್ಸನ್ನು ತಪಾಸಣೆ ಮಾಡಿರಿ.
• ಬಲಬದಿಯ ಚೈಲ್ಡ್‌ನಿಂದ ಡಿಲಿಶನ್ ಆಗಿದ್ದಲ್ಲಿ, ಮತ್ತು ಲೆಫ್ಟ್ ಚೈಲ್ಡ್‌ನಲ್ಲಿ ಯಾವುದೇ ಅಂಡರ್‌ಫ್ಲೋ ಇಲ್ಲದಿದ್ದಲ್ಲಿ, ಎಡಬದಿಯ ಚೈಲ್ಡ್‌ನ ಅಧಿಕತಮ ಮೌಲ್ಯವನ್ನು ಮತ್ತೆ ವಶಪಡಿಸಿಕೊಳ್ಳಿರಿ.
• ಇದಕ್ಕೆ ವ್ಯತಿರಿಕ್ತವಾದ ಸಂದರ್ಭವಿದ್ದಲ್ಲಿ ಬಲಬದಿಯಿಂದ ಕನಿಷ್ಠ ಘಟಕವನ್ನು ಮತ್ತೆ ವಶಕ್ಕೆ ತೆಗೆದುಕೊಳ್ಳಿರಿ.

ಇಂಟರ್ನಲ್ ನೋಡ್ ಒಂದರಿಂದ ಡಿಲಿಶನ್

ಇಂಟರ್ನಲ್ ನೋಡ್‌ನಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಘಟಕವೂ ಎರಡು ಸಬ್‌ಟ್ರೀಗಳ ಸಪರೇಶನ್ ವ್ಯಾಲ್ಯೂ ಆಗಿ ವರ್ತಿಸುತ್ತದೆ, ಮತ್ತು ಇಂತಹ ಘಟಕವೊಂದನ್ನು ಡಿಲಿಟ್ ಮಾಡಿದಾಗ, ಎರಡು ಸನ್ನಿವೇಶಗಳು ಹುಟ್ಟಿಕೊಳ್ಳುತ್ತವೆ. ಮೊದಲನೆಯ ಸಂದರ್ಭದಲ್ಲಿ, ಡಿಲಿಟ್ ಮಾಡಲಾದ ಘಟಕದ ಎಡ ಮತ್ತು ಬಲಬದಿಗಳ ಎರಡೂ ಚೈಲ್ಡ್ ನೋಡ್‌ಗಳು ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯ ಘಟಕಗಳನ್ನು, ಎಂದರೆ L −1 ಅನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಇವನ್ನು 2L −2 ಘಟಕಗಳನ್ನು ಬಳಸಿ ಒಂದು ಸಿಂಗಲ್ ನೋಡ್ ಆಗಿ ಸೇರಿಸಬಹುದು, ಮತ್ತು ಈ ಸಂಖ್ಯೆಯು U −1ಗಿಂತ ಹೆಚ್ಚಿಲ್ಲದಿರುವ ಕಾರಣ ಇದು ಒಂದು ಲೀಗಲ್ ನೋಡ್ ಆಗುತ್ತದೆ. ಈ ನಿರ್ದಿಷ್ಟ ಬಿ-ಟ್ರೀಯು ದತ್ತಾಂಶದ ನಕಲನ್ನು ಹೊಂದಿಲ್ಲ ಎಂದು ಮಾಹಿತಿ ದೊರಕದಿದ್ದ ಪಕ್ಷದಲ್ಲಿ, ನಾವು ಜತೆಗೇ ಹೊಸ ನೋಡ್‌ನಿಂದ ಪ್ರಶ್ನೆಗೊಳಗಾಗಿರುವ ಘಟಕವನ್ನು (ರಿಕರ್ಸಿವ್ ಆಗಿ) ಡಿಲಿಟ್ ಮಾಡಬೇಕಾಗುವುದು.

ಎರಡನೆ ಸಂದರ್ಭದಲ್ಲಿ, ಎರಡು ಚೈಲ್ಡ್ ನೋಡ್‌ಗಳಲ್ಲಿ ಒಂದು ನೋಡ್ ಕನಿಷ್ಟ ಸಂಖ್ಯೆಗಿಂತ ಹೆಚ್ಚಿನ ಘಟಕಗಳನ್ನು ಹೊಂದಿರುವುದು. ಆಗ ಆ ಸಬ್‌ಟ್ರೀಗಳಿಗೆ ಹೊಸ ಸಪರೇಟರ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕಾಗಿ ಬರುವುದು. ಎಡಬದಿಯ ಸಬ್‌ಟ್ರೀಯ ಅತ್ಯ್ಂತ ದೊಡ್ಡ ಘಟಕವು ಇನ್ನೂ ಸಪರೇಟರ್‌ಗಿಂತ ಕಡಿಮೆ ಇದೆಯೆಂಬುದನ್ನು ಗಮನಿಸಿ. ಇದರಂತೆಯೆ, ಬಲಭಾಗದ ಸಬ್‌ಟ್ರೀಯ ಅತ್ಯಂತ ಸಣ್ಣ ಘಟಕವೂ ಸಪರೇಟರ್‌ಗಿಂತ ಹೆಚ್ಚಿರುವುದು. ಈ ಎರಡೂ ಘಟಕಗಳು ಲೀಫ್ ನೋಡ್‌ಗಳಲ್ಲಿರುತ್ತವೆ, ಮತ್ತು ಇವೆರಡರಲ್ಲಿ ಯಾವುದಾದರೂ ಕೂಡಾ ಎರಡು ಸಬ್‌ಟ್ರೀಗಳಿಗೆ ಹೊಸ ಸಪರೇಟರ್ ಆಗಬಹುದು.

• ವ್ಯಾಲ್ಯೂ ಇಂಟರ್ನಲ್ ನೋಡ್‌ನಲ್ಲಿದ್ದಲ್ಲಿ, ಹೊಸ ಸಪರೇಟರ್ ಅನ್ನು ಆಯ್ಕೆಮಾಡಿರಿ (ಎಡ ಸಬ್‍ಟ್ರೀಯ ಅತಿ ದೊಡ್ಡ ಘಟಕ ಅಥವಾ ಬಲ ಸಬ್‌ಟ್ರೀಯ ಅತಿ ಚಿಕ್ಕ ಘಟಕ), ಅದು ಸ್ಥಿತವಾಗಿರುವ ಲೀಫ್ ನೋಡ್‍ನಿಂದ ಅದನ್ನು ತೆಗೆಯಿರಿ, ಮತ್ತು ಡಿಲಿಟ್ ಮಾಡಬೇಕಿರುವ ಎಲಿಮೆಂಟ್ ಅನ್ನು ಹೊಸ ಸಪರೇಟರ್ ಹಾಕಿ ಬದಲಿ ಮಾಡಿರಿ.
• ಇದರಿಂದಾಗಿ ಒಂದು ಲೀಫ್ ನೋಡ್‌ನಿಂದ ಘಟಕವೊಂದು ಡಿಲಿಟ್ ಆಗುವುದು, ಮತ್ತು ಇದು ಹಿಂದಿನದಕ್ಕೆ ಸಮವಾಗುವುದು.

ಡಿಲಿಶನ್‌ನ ನಂತರ ಮರುಸಮತೋಲನ

ಒಂದು ಲೀಫ್ ನೋಡ್‌ನಿಂದ ಘಟಕವೊಂದನ್ನು ಡಿಲಿಟ್ ಮಾಡುವುದರಿಂದ ಅದು ಕನಿಷ್ಠ ಗಾತ್ರಕ್ಕಿಂತ ಕಡಿಮೆಯಾಗುವಂತಿದ್ದಲ್ಲಿ, ಎಲ್ಲಾ ನೋಡ್‌ಗಳನ್ನೂ ಕನಿಷ್ಠಗಾತ್ರಕ್ಕೆ ತರಲು ಕೆಲವು ಘಟಕಗಳನ್ನು ಮರುವಿತರಿಸಬೇಕಾಗುವುದು. ಕೆಲವು ಸಂದರ್ಭಗಳಲ್ಲಿ ಮರುವಿತರಣೆಯು ಈ ನ್ಯೂನತೆಯನ್ನು ಪೇರೆಂಟ್‌ಗೆ ಕೊಂಡೊಯ್ಯುವುದು, ಮತ್ತು ಮರುವಿತರಣೆಯನ್ನು ಟ್ರೀಯ ಕೆಳಗಿನಿಂದ ಮೇಲಕ್ಕೆ ಮತ್ತೆ ಪುನಃ ಪ್ರಯೋಗಿಸಬೇಕಾಗಿ ಬರಬಹುದು, ಬಹುಶಃ ರೂಟ್‌ಗೂ ಕೂಡ. ಮಿನಿಮಮ್ ಎಲಿಮೆಂಟ್ ಕೌಂಟ್ ರೂಟ್‌ಗೆ ಅನ್ವಯಿಸುವುದಿಲ್ಲವಾದ್ದರಿಂದ, ರೂಟನ್ನು ಏಕೈಕ ನ್ಯೂನತೆಯುಳ್ಳ ನೋಡ್ ಅನ್ನಾಗಿ ಮಾಡುವುದರಲ್ಲಿ ಯಾವುದೇ ತೊಂದರೆಯಿಲ್ಲ. ಟ್ರೀಯನ್ನು ಮರುಸಂತುಲಿತಗೊಳಿಸುವ ಅಲ್ಗಾರಿದಮ್ ಈ ಕೆಳಗಿನಂತಿರುವುದು:

• ರೈಟ್ ಸಿಬ್ಲಿಂಗ್ ಕನಿಷ್ಠ ಸಂಖ್ಯೆಗಿಂತ ಹೆಚ್ಚಿನ ಘಟಕಗಳನ್ನು ಹೊಂದಿದ್ದಲ್ಲಿ
  • ನ್ಯೂನತೆ ಹೊಂದಿರುವ ನೋಡ್‌ನ ತುದಿಗೆ ಸಪರೇಟರ್ ಅನ್ನು ಸೇರಿಸಿರಿ.
  • ಪೇರೆಂಟ್‌ನಲ್ಲಿನ ಸಪರೇಟರ್‌ಗೆ ಬದಲಾಗಿ ರೈಟ್ ಸಿಬ್ಲಿಂಗ್‌ನ ಮೊದಲನೆ ಘಟಕವನ್ನು ಇರಿಸಿರಿ.
  • ರೈಟ್ ಸಿಬ್ಲಿಂಗ್‌ನ ಮೊದಲ ಚೈಲ್ಡ್ ಅನ್ನು ಡಿಫಿಶಿಯೆಂಟ್ ನೋಡ್‍ನ ಕೊನೆಯ ಚೈಲ್ಡ್ ಆಗಿ ಮಾಡಿ ಜೋಡಿಸಿರಿ
• ಇಲ್ಲದಿದ್ದರೆ, ಲೆಫ್ಟ್ ಸಿಬ್ಲಿಂಗ್ ಕನಿಷ್ಠ ಸಂಖ್ಯೆಗಿಂತ ಹೆಚ್ಚಿನ ಘಟಕಗಳನ್ನು ಹೊಂದಿದ್ದಲ್ಲಿ.
  • ಸಪರೇಟರ್ ಅನ್ನು ಡಿಫಿಶಿಯೆಂಟ್(ನ್ಯೂನತೆ ಹೊಂದಿರುವ) ನೋಡ್‌ನ ಆರಂಭಕ್ಕೆ ಸೇರಿಸಿ.
  • ಪೇರೆಂಟ್‌ನಲ್ಲಿನ ಸಪರೇಟರ್‌ಗೆ ಬದಲಾಗಿ ಲೆಫ್ಟ್ ಸಿಬ್ಲಿಂಗ್‌ನ ಕೊನೆಯ ಘಟಕವನ್ನು ಇರಿಸಿರಿ.
  • ಲೆಫ್ಟ್ ಸಿಬ್ಲಿಂಗ್‌ನ ಕೊನೆಯ ಚೈಲ್ಡ್ ಅನ್ನು ಡಿಫಿಶಿಯೆಂಟ್ ನೋಡ್‍ನ ಮೊದಲ ಚೈಲ್ಡ್ ಆಗಿ ಮಾಡಿ ಜೋಡಿಸಿರಿ
• ಎರಡೂ ಪಕ್ಕಪಕ್ಕದಲ್ಲಿರುವ ಸಿಬ್ಲಿಂಗ್‌ಗಳು ಬರೇ ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯ ಘಟಕಗಳನ್ನು ಮಾತ್ರ ಹೊಂದಿದ್ದಲ್ಲಿ
  • ಡಿಫಿಶಿಯೆಂಟ್ ನೋಡ್‌ನ ಎಲ್ಲಾ ಘಟಕಗಳನ್ನು ಬಳಸಿಕೊಂಡು, ಅದರ ಸಿಬ್ಲಿಂಗ್ ಒಂದರ ಎಲ್ಲಾ ಘಟಕಗಳು ಮತ್ತು ಎರಡು ಕಂಬೈನ್ಡ್ ಸಿಬ್ಲಿಂಗ್ ನೋಡ್‌ಗಳ ಪೇರೆಂಟ್‌ನಲ್ಲಿರುವ ಸಪರೇಟರ್ ಅನ್ನು ಬಳಸಿಕೊಂಡು ಒಂದು ಹೊಸ ನೋಡ್ ಅನ್ನು ರೂಪಿಸಿರಿ.
  • ಸಪರೇಟರ್ ಅನ್ನು ಪೇರೆಂಟ್‌ನಿಂದ ತೆಗೆಯಿರಿ, ಮತ್ತು ಅದು ವಿಭಜಿಸಿದ ಎರಡೂ ಚಿಲ್ಡ್ರನ್‍ಗಳ ಬದಲಿಗೆ ಕಂಬೈನ್ಡ್ ನೋಡ್ ಅನ್ನು ಇರಿಸಿರಿ.
  • ಇದರಿಂದ ಪೇರೆಂಟ್‌ನಲ್ಲಿರುವ ಘಟಕಗಳ ಸಂಖ್ಯೆಯು ಕನಿಷ್ಠಕ್ಕಿಂತ ಕಡಿಮೆಯಾದಲ್ಲಿ, ಈ ಹೆಜ್ಜೆಗಳನ್ನು ಆ ಡಿಫಿಶಿಯೆಂಟ್ ನೋಡ್‌ನೊಂದಿಗೆ ಪುನರಾವರ್ತಿಸಿರಿ, ಆದರೆ ಅದು ರೂಟ್ ಆಗಿರಬಾರದು, ಏಕೆಂದರೆ ರೂಟ್ ಡಿಫಿಶಿಯೆಂಟ್ ಆಗಿರುವ ಸಾಧ್ಯತೆಗಳಿವೆ.

ಇದಲ್ಲದೆ ಪರಿಗಣಿಸಬಹುದಾದ ಒಂದೇ ಕೇಸ್ ಎಂದರೆ ರೂಟ್‌ನಲ್ಲಿ ಯಾವುದೇ ಘಟಕಗಳಿರದೆ ಬರೆ ಒಂದು ಚೈಲ್ಡ್ ಮಾತ್ರ ಇರುವಂತಹ ಸಂದರ್ಭ. ಇಂತಹ ವೇಳೆಯಲ್ಲಿ ಅದರ ಬದಲು ಅದರ ಏಕೈಕ ಚೈಲ್ಡ್ ಅನ್ನು ಇರಿಸಿದರೆ ಸಾಕಾಗುವುದು.

ಪ್ರಾರಂಭಿಕ ನಿರ್ಮಾಣ

ಅಪ್ಲಿಕೇಶನ್‌ಗಳಲ್ಲಿ, ಒಂದು ದೊಡ್ಡಗಾತ್ರದ ದತ್ತಾಂಶ ಸಂಗ್ರಹವನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಸಲುವಾಗಿ ಒಂದು ಬಿ-ಟ್ರೀಯನ್ನು ರಚಿಸುವುದು ಮತ್ತು ನಂತರದಲ್ಲಿ ನಿರ್ಧಾರಿತ ಮಾನದಂಡಗಳ ಬಿ-ಟ್ರೀ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಬಳಸಿ ಅದನ್ನು ಏರಿಕೆಯ ಕ್ರಮದಲ್ಲಿ ಅಪ್‌ಡೇಟ್ ಮಾಡುವುದು ಆಗಾಗ ಪ್ರಯೋಜನಕಾರಿಯಾಗಿರುತ್ತದೆ. ಈ ವಿಷಯದಲ್ಲಿ, ಪ್ರಾರಂಭಿಕ ಬಿ-ಟ್ರೀಯನ್ನು ರಚಿಸಲು ಅತ್ಯಂತ ಸಮರ್ಥವಾದ ವಿಧಾನವೆಂದರೆ, ಪ್ರಾರಂಭಿಕ ಸಂಗ್ರಹದಲ್ಲಿ ಪ್ರತಿಯೊಂದು ಘಟಕವನ್ನೂ ಒಂದಾದಮೇಲೊಂದರಂತೆ ಒಳಸೇರಿಸದಿರುವುದು, ಮತ್ತು ಇದಕ್ಕೆ ಬದಲಾಗಿ ಲೀಫ್ ನೋಡ್‌ಗಳ ಪ್ರಾರಂಭಿಕ ಗುಂಪನ್ನು ನೇರವಾಗಿ ಇನ್‌ಪುಟ್‌ನಿಂದ ನಿರ್ಮಿಸುವುದು, ಮತ್ತು ನಂತರ ಇವುಗಳಿಂದ ಇಂಟರ್ನಲ್ ನೋಡ್‌ಗಳನ್ನು ನಿರ್ಮಿಸುವುದು. ಬಿ-ಟ್ರೀ ನಿರ್ಮಾಣದ ಈ ವಿಧಾನವನ್ನು ಬಲ್ಕ್‌ಲೋಡಿಂಗ್ ಎನ್ನಲಾಗುತ್ತದೆ. ಮೊದಲಿಗೆ, ಕೊನೆಯ ಒಂದು ಲೀಫ್ ಅನ್ನು ಬಿಟ್ಟು ಉಳಿದೆಲ್ಲವೂ ಒಂದು ಹೆಚ್ಚುವರಿ ಘಟಕವನ್ನು ಹೊಂದಿರುವುದು, ಮತ್ತು ಇದನ್ನು ಇಂಟರ್ನಲ್ ನೋಡ್‌ಗಳನ್ನು ನಿರ್ಮಿಸಲು ಬಳಸಲಾಗುವುದು.

ಉದಾಹರಣೆಗೆ, ಲೀಫ್ ನೋಡ್‌ಗಳು ಗರಿಷ್ಠ ಗಾತ್ರ 4ನ್ನು ಹೊಂದಿದ್ದು ಪ್ರಾರಂಭಿಕ ಸಂಗ್ರಹವು 1ರಿಂದ 24ರ ಇಡೀ ಸಂಖ್ಯೆಗಳಾಗಿದ್ದರೆ, ನಾವು ಮೊದಲಿಗೆ ತಲಾ 5 ವ್ಯಾಲ್ಯೂಗಳನ್ನುಳ್ಳ 4 ಲೀಫ್ ನೋಡ್‌ಗಳು ಮತ್ತು 4 ವ್ಯಾಲ್ಯೂಗಳನ್ನುಳ್ಳ 1 ನೋಡ್ ಅನ್ನು ರಚಿಸಬಹುದು:

1 2 3 4 5

6 7 8 9 10

11 12 13 14 15

16 17 18 19 20

21 22 23 24

ನಾವು ನಂತರದ ಲೆವೆಲ್ ಅನ್ನು, ಲೀವ್ಸ್ ಇಂದ ಕೊನೆಯದನ್ನು ಬಿಟ್ಟು ಪ್ರತಿ ಲೀಫ್ ನೋಡ್‌ನಿಂದ ಕೊನೆಯ ಘಟಕವನ್ನು ತೆಗೆದುಕೊಳ್ಳುವುದರ ಮೂಲಕ ನಿರ್ಮಿಸಬಹುದು. ಪುನಃ, ಕೊನೆಯ ನೋಡ್ ಅನ್ನು ಬಿಟ್ಟು ಉಳಿದ ಪ್ರತಿಯೊಂದು ನೋಡ್ ಕೂಡಾ ಒಂದು ಹೆಚ್ಚುವರಿ ವ್ಯಾಲ್ಯೂ ಅನ್ನು ಹೊಂದಿರುವುದು. ಉದಾಹರಣೆಯಲ್ಲಿ, ಅಕಸ್ಮಾತ್ ಇಂಟರ್ನಲ್ ನೋಡ್‍ಗಳು ಹೆಚ್ಚೆಂದರೆ 2 ವ್ಯಾಲ್ಯೂಗಳನ್ನು ಹೊಂದಿದ್ದಲ್ಲಿ (3 ಚೈಲ್ಡ್ ಪಾಯಿಂಟರ್‌ಗಳು). ಆಗ ಇಂಟರ್ನಲ್ ನೋಡ್‌ಗಳ ನಂತರದ ಮೇಲಿನ ಮಟ್ಟವು ಈ ರೀತಿಯಾಗಿರುವುದು:

5 10 15

20

1 2 3 4

6 7 8 9

11 12 13 14

16 17 18 19

21 22 23 24

ಈ ವಿಧಾನವನ್ನು ನಾವು ಒಂದೇ ಒಂದು ನೋಡ್ ಇರುವ ಮತ್ತು ಅದು ತುಂಬಿತುಳುಕದಿರುವ ಮಟ್ಟವನ್ನು ತಲುಪುವ ತನಕ ಮುಂದುವರಿಸಲಾಗುವುದು. ಉದಾಹರಣೆಯಲ್ಲಿ ರೂಟ್ ಮಟ್ಟವು ಈ ರೀತಿ ಇರುವುದು:

15

5 10

20

1 2 3 4

6 7 8 9

11 12 13 14

16 17 18 19

21 22 23 24

ಫೈಲ್‌ಸಿಸ್ಟಮ್‌ಗಳಲ್ಲಿ ಬಿ-ಟ್ರೀಗಳು

ಇದಲ್ಲದೆ, ಬಿ-ಟ್ರೀಯನ್ನು ಫೈಲ್ ಸಿಸ್ಟಮ್‌ಗಳಲ್ಲಿ ಒಂದು ನಿರ್ದಿಷ್ಟವಾದ ಫೈಲ್‌ನ ಒಂದು ಆರ್ಬಿಟ್ರರಿ ಬ್ಲಾಕ್‌ಗೆ ತ್ವರಿತವಾದ ರ‍್ಯಾಂಡಮ್ ಆಕ್ಸೆಸ್ ಅನ್ನು ಕಲ್ಪಿಸಲು ಕೂಡಾ ಬಳಸಲಾಗುತ್ತದೆ. ಮೂಲ ತೊಂದರೆಯೆಂದರೆ, ಲಾಜಿಕಲ್ ಬ್ಲಾಕ್ $i$ ಅಡ್ರೆಸನ್ನು ಒಂದು ಫಿಸಿಕಲ್ ಡಿಸ್ಕ್ ಬ್ಲಾಕ್ ಆಗಿ ಪರಿವರ್ತಿಸುವುದು (ಅಥವಾ ಪ್ರಾಯಶಃ ಒಂದು ಸಿಲಿಂಡರ್-ಹೆಡ್-ಸೆಕ್ಟರ್ ಅಡ್ರೆಸ್ ಆಗಿ).

ಕೆಲವು ಆಪರೇಟಿಂಗ್ ಸಿಸ್ಟಮ್‌ಗಳಲ್ಲಿ ಫೈಲ್ ಅನ್ನು ರೂಪಿಸಿದಾಗ ಯೂಸರ್ ಫೈಲ್‌ನ ಗರಿಷ್ಠ ಗಾತ್ರವನ್ನು ನಿಗದಿಪಡಿಸಬೇಕಾಗುತ್ತದೆ. ನಂತರ ಫೈಲ್ ಅನ್ನು ಕಾಂಟಿಗ್ಯುವಸ್ ಡಿಸ್ಕ್ ಬ್ಲಾಕ್‌ಗಳಾಗಿ ಹಂಚಲಾಗುವುದು. ಫಿಸಿಕಲ್ ಬ್ಲಾಕ್‌ಗೆ ಮಾರ್ಪಡಿಸುವಿಕೆ: ಆಪರೇಟಿಂಗ್ ಸಿಸ್ಟಮ್ ಬರೆ ಲಾಜಿಕಲ್ ಬ್ಲಾಕ್ ಅಡ್ರೆಸ್ ಅನ್ನು ಫೈಲ್‌ನ ಸ್ಟಾರ್ಟಿಂಗ್ ಫಿಸಿಕಲ್ ಬ್ಲಾಕ್‌ಗೆ ಸೇರಿಸುತ್ತದೆ. ಈ ಯೋಜನೆಯು ಸರಳವಾಗಿದೆಯಾದರೂ, ಫೈಲ್ ತನ್ನ ರಚನಾ ಗಾತ್ರವನ್ನು ಮೀರುವಂತಿಲ್ಲ.

ಇತರ ಆಪರೇಟಿಂಗ್ ಸಿಸ್ಟಮ್‍ಗಳಲ್ಲಿ ಫೈಲ್ ಬೆಳೆಯಲು ಅವಕಾಶ ನೀಡಲಾಗುತ್ತದೆ. ಇದರಿಂದುಂಟಾಗುವ ಡಿಸ್ಕ್ ಬ್ಲಾಕ್‌ಗಳು ಕಾಂಟಿಗ್ಯುವಸ್ ಆಗಿಲ್ಲದಿರಬಹುದು, ಆದ್ದರಿಂದ ಲಾಜಿಕಲ್ ಬ್ಲಾಕ್‌ಗಳನ್ನು ಫಿಸಿಕಲ್ ಬ್ಲಾಕ್‌ಗಳನ್ನಾಗಿ ಮ್ಯಾಪಿಂಗ್ ಮಾಡುವುದು ಹೆಚ್ಚು ತೊಡಕಿನ ಕೆಲಸ.

MS/DOS, ಉದಾಹರಣೆಗೆ, ಒಂದು ಸರಳವಾದ File Allocation Table (FAT) ಅನ್ನು ಬಳಸಿತು. FAT ಪ್ರತಿ ಫಿಸಿಕಲ್ ಡಿಸ್ಕ್ ಬ್ಲಾಕ್‌ಗೆ ಒಂದು ಪ್ರವೇಶವನ್ನು ಹೊಂದಿದ್ದು, ಈ ಪ್ರವೇಶವು ಫೈಲ್ ಒಂದರ ನಂತರದ ಫಿಸಿಕಲ್ ಡಿಸ್ಕ್ ಬ್ಲಾಕ್‌ ಅನ್ನು ಗುರುತಿಸುವುದು. ಇದರಿಂದಾಗಿ, ಫೈಲ್‌ನ ಡಿಸ್ಕ್ ಬ್ಲಾಕ್‌ಗಳು ಒಂದು ಲಿಂಕ್ಡ್ ಲಿಸ್ಟ್ನಲ್ಲಿರುವವು. ಬ್ಲಾಕ್‌ $i$ನ ಫಿಸಿಕಲ್ ಅಡ್ರೆಸ್ ಅನ್ನು ಹುಡುಕಬೇಕೆಂದರೆ, ಆಪರೇಟಿಂಗ್ ಸಿಸ್ಟಮ್ FAT ಅನ್ನು ಸೀಕ್ವೆನ್ಷಿಯಲ್ ಆಗಿ ಹುಡುಕಬೇಕಾಗುವುದು. MS/DOSಗೆ ಇದು ದೊಡ್ಡ ಪ್ರತಿಬಂಧಕವೇನೂ ಆಗಿರಲಿಲ್ಲ, ಏಕೆಂದರೆ ಡಿಸ್ಕ್‌ಗಳು ಸಣ್ಣವಾಗಿದ್ದವು ಮತ್ತು FAT ಕಡಿಮೆ ಎಂಟ್ರಿಗಳನ್ನು ಹೊಂದಿತ್ತು. FAT12 ಫೈಲ್‌ಸಿಸ್ಟಮ್‌ನಲ್ಲಿ ಕೇವಲ 4,096 ಎಂಟ್ರಿಗಳಿದ್ದವು, ಮತ್ತು FAT ಸಾಮಾನ್ಯವಾಗಿ ರೆಸಿಡೆಂಟ್ ಆಗಿರುತ್ತಿದ್ದಿತು. ಡಿಸ್ಕ್‌ಗಳು ದೊಡ್ಡದಾಗುತ್ತಿದ್ದಂತೆ FAT ವಾಸ್ತುಶಿಲ್ಪವು ಪ್ರತಿಬಂಧಕಗಳನ್ನು ಎದುರಿಸಬೇಕಾಗುತ್ತದೆ. ಯೂಸರ್ ಓದಬೇಕೆಂದಿರುವ ಬ್ಲಾಕ್‌ನ ಫಿಸಿಕಲ್ ಅಡ್ರೆಸ್ ಅನ್ನು ತಿಳಿದುಕೊಳ್ಳಲು ಡಿಸ್ಕ್ ರೀಡ್‌ಗಳನ್ನು ನಡೆಸುವುದು ಅವಶ್ಯಕವಾಗಬಹುದು.

TOPS-20 (ಮತ್ತು ಪ್ರಾಯಶಃ TENEX) ಒಂದು ಬಿ-ಟ್ರೀಗೆ ಸದೃಶವಾಗಿರುವ 0ಯಿಂದ 2 lಲೆವೆಲ್ ಟ್ರೀಯನ್ನು ಬಳಸಿದವು. ಒಂದು ಡಿಸ್ಕ್ ಬ್ಲಾಕ್ 512 36-ಬಿಟ್ ಪದಗಳಾಗಿತ್ತು. ಫೈಲ್ ಒಂದು 512 ($2^{9}$) ವರ್ಡ್ ಬ್ಲಾಕ್‌ನಲ್ಲಿ ಸರಿಹೊಂದಿಕೊಂಡಲ್ಲಿ, ಆಗ ಫೈಲ್ ಡೈರೆಕ್ಟರಿಯು ಆ ಫಿಸಿಕಲ್ ಡಿಸ್ಕ್ ಬ್ಲಾಕ್‍ಗೆ ಗುರಿಮಾಡಿ ತೋರುವುದು. ಅಕಸ್ಮಾತ್ ಫೈಲ್ $2^{18}$ ಪದಗಳಲ್ಲಿ ಸರಿಹೊಂದಿಕೊಂಡಲ್ಲಿ, ಆಗ ಡೈರೆಕ್ಟರಿಯು ಒಂದು ಆಕ್ಸ್ ಇಂಡೆಕ್ಸ್‌ ಅನ್ನು ತೋರುವುದು; ಆ ಇಂಡೆಕ್ಸ್‌ನ 512 ಪದಗಳು ಇಲ್ಲವೇ NULL ಆಗಿರುವವು (ಬ್ಲಾಕ್ ಅನ್ನು ನಿಗದಿಪಡಿಸಲಾಗಿರುವುದಿಲ್ಲ) ಅಥವಾ ಬ್ಲಾಕ್‍ನ ಫಿಸಿಕಲ್ ಅಡ್ರೆಸ್‍ನೆಡೆಗೆ ಗುರಿಮಾಡಿ ತೋರುತ್ತವೆ. ಅಕಸ್ಮಾತ್ ಫೈಲ್ $2^{27}$ ಪದಗಳಲ್ಲಿ ಸರಿಹೊಂದಿಕೊಂಡಲ್ಲಿ, ಆಗ ಡೈರೆಕ್ಟರಿಯು ಒಂದು ಆಕ್ಸ್ ಇಂಡೆಕ್ಸ್‌ ಅನ್ನು ಹಿಡಿದುಕೊಂಡಿರುವ ಬ್ಲಾಕ್ ಅನ್ನು ತೋರುವುದು; ಪ್ರತಿಯೊಂದು ಎಂಟ್ರಿಯೂ NULL ಆಗಿರುವುದು ಅಥವಾ ಆಕ್ಸ್ ಇಂಡೆಕ್ಸ್ ಒಂದನ್ನು ತೋರುವುದು. ಪರಿಣಾಮವಾಗಿ, ಒಂದು $2^{27}$ ಪದಗಳ ಫೈಲ್‌ನ ಫಿಸಿಕಲ್ ಡಿಸ್ಕ್ ಬ್ಲಾಕ್ ಅನ್ನು ಎರಡು ಡಿಸ್ಕ್ ರೀಡ್‌ಗಳಲ್ಲಿ ಪತ್ತೆ ಹಚ್ಚಿ ಮೂರನೆಯದರಲ್ಲಿ ರೀಡ್ ಮಾಡಬಹುದು.

Appleನ ಫೈಲ್‌ಸಿಸ್ಟಮ್ HFS+ ಮತ್ತು Microsoftನ NTFS ಗಳು ಬಿ-ಟ್ರೀಗಳನ್ನು ಬಳಸುತ್ತವೆ.

ಟಿಪ್ಪಣಿಗಳು

ಪ್ರವೇಶ ಸಮ್ಮತಿ

ಲೆಹ್ಮನ್ ಮತ್ತು ಯಾವೊ ರವರು ಪ್ರತೀ ಲೆವೆಲ್‍ನಲ್ಲಿನ ಟ್ರೀಬ್ಲಾಕ್‌ಗಳನ್ನು ಒಂದಕ್ಕೊಂದಕ್ಕೆ ಸಂಪರ್ಕ ಕಲ್ಪಿಸಿ ಅಲ್ಲಿ ’ನೆಕ್ಸ್ಟ್’ ಪಾಯಿಂಟರ್ ಅನ್ನು ಹಾಕುವುದರಿಂದ ಎಲ್ಲಾ ರೀಡ್ ಲಾಕ್‌ಗಳನ್ನು ತಪ್ಪಿಸಬಹುದು (ಮತ್ತು ಇದರಿಂದ ಕಾನ್‌ಕರೆಂಟ್ ಆಕ್ಸೆಸ್ ಅನ್ನು ಬಹಳ ಹೆಚ್ಚು ಉತ್ತಮಪಡಿಸಬಹುದು) ಎಂದು ತೋರಿಸಿಕೊಟ್ಟಿದ್ದಾರೆ. ಇದರ ಫಲಸ್ವರೂಪವಾಗಿ ಇನ್‌ಸರ್ಶನ್ ಮತ್ತು ಸರ್ಚ್ ಕಾರ್ಯಾಚರಣೆಗಳೆರಡೂ ರೂಟ್‌ನಿಂದ ಲೀಫ್‌ಗೆ ಇಳಿದುಬರುವಂತಹ ಟ್ರೀ ರಚನೆಯುಂಟಾಗುವುದು. ಒಂದು ಟ್ರೀ ಬ್ಲಾಕ್ ಅನ್ನು ಮಾರ್ಪಡಿಸುವಾಗ ಮಾತ್ರ ರೈಟ್ ಲಾಕ್‌ಗಳ ಅವಶ್ಯಕತೆಯುಂಟಾಗುತ್ತದೆ. ಇದು ಬಹುಸಂಖ್ಯೆಯ ಬಳಕೆದಾರರ(ಯೂಸರ್ಸ್) ಆಕ್ಸೆಸ್ ಕನ್‌ಕರೆನ್ಸಿಯನ್ನು ಗರಿಷ್ಠಮಟ್ಟಕ್ಕೇರಿಸುತ್ತದೆ, ಮತ್ತು ಇದು ದತ್ತಸಂಚಯಗಳು ಮತ್ತು/ಅಥವಾ ಇತರೆ ಬಿ-ಟ್ರೀ ಆಧರಿತ ISAM ಸಂಗ್ರಹ ವಿಧಾನಗಳಿಗೆ ಮಹತ್ವದ ಪ್ರಯೋಜನವಾಗಿದೆ. ಈ ಸುಧಾರಣೆಯೊಂದಿಗೆ ಬರುವ ವೆಚ್ಚವೆಂದರೆ ಸಾಮಾನ್ಯ ಕಾರ್ಯಾಚರಣೆಗಳ ವೇಳೆಯಲ್ಲಿ ಖಾಲಿ ಪೇಜ್‌ಗಳನ್ನು ತೆಗೆದುಹಾಕಲು ಸಾಧ್ಯವಾಗುವುದಿಲ್ಲ. (ಆದರೆ, ನೋಡಿ ನೋಡ್ ಮರ್ಜಿಂಗ್ ಮತ್ತು ಸೋರ್ಸ್ ಕೋಡ್‌ಗಳನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಲು ಇರುವ ಹಲವಾರು ತಂತ್ರಗಳು, ಇಲ್ಲಿ .)

ಇವನ್ನೂ ಗಮನಿಸಿ

• B+ ಟ್ರೀ
• ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ
• ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಟ್ರೀ

ಆಕರಗಳು

• Bayer, R.; McCreight, E. (1972), "Organization and Maintenance of Large Ordered Indexes" (PDF), Acta Informatica, 1 (3): 173–189 {{citation}}: Invalid |ref=harv (help)

• Comer, Douglas (June 1979), "The Ubiquitous B-Tree" (PDF), Computing Surveys, 11 (2): 123–137 {{citation}}: Invalid |ref=harv (help)CS1 maint: date and year (link). (slow download)

• [35] ಅಧ್ಯಾಯ 18: B-Trees.
• Folk, Michael J.; Zoellick, Bill (1992), File Structures (2nd ed.), Addison-Wesley, ISBN 0-201-55713-4 {{citation}}: Invalid |ref=harv (help)

• Knuth, Donald (1997), Sorting and Searching, The Art of Computer Programming, vol. Volume 3 (Third ed.), Addison-Wesley, ISBN 0-201-89685-0 {{citation}}: |volume= has extra text (help). ವಿಭಾಗ 6.2.4: Multiway Trees, pp. 481–491. Also, pp. 476–477 of section 6.2.3 (Balanced Trees) discusses 2-3 trees.

Original papers

• Bayer, Rudolf; McCreight, E. (1970), Organization and Maintenance of Large Ordered Indices, vol. Mathematical and Information Sciences Report No. 20, Boeing Scientific Research Laboratories. ಜುಲೈ 2007.

• Bayer, Rudolf (1971), "Binary B-Trees for Virtual Memory", Proceedings of 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control, San Diego, California {{citation}}: Missing or empty |title= (help)CS1 maint: location missing publisher (link). ನವೆಂಬರ್ 11-12, 1971.

ಹೊರಗಿನ ಕೊಂಡಿಗಳು

• B-Tree animation applet ಸ್ಲ್ಯಾಡಿಯವರಿಂದ
• B-tree and UB-tree on Scholarpedia ಕ್ಯುರೇಟರ್: ಡಾ ರುಡೋಲ್ಫ್ ಬೇಯರ್
• B-Trees: Balanced Tree Data Structures Archived 2010-03-05 ವೇಬ್ಯಾಕ್ ಮೆಷಿನ್ ನಲ್ಲಿ.
• NIST's Dictionary of Algorithms and Data Structures: B-tree
• C++ source code for a balanced tree (B-tree) (Windows required for test timings)
• WB disk-based B-tree C-library/Java-library/C#-library
• B-Trees in Perl