ಹೇ ಹಬ್ರ್! ನಾನು ನಿಮ್ಮ ಗಮನಕ್ಕೆ ಲೇಖನದ ಅನುವಾದವನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತೇನೆ
"ಸಂಬಂಧಿತ ಡೇಟಾಬೇಸ್ ಹೇಗೆ ಕೆಲಸ ಮಾಡುತ್ತದೆ".

ಸಂಬಂಧಿತ ಡೇಟಾಬೇಸ್‌ಗಳ ವಿಷಯಕ್ಕೆ ಬಂದಾಗ ನಾನು ಸಹಾಯ ಮಾಡಲು ಸಾಧ್ಯವಿಲ್ಲ ಆದರೆ ಏನಾದರೂ ಕಾಣೆಯಾಗಿದೆ ಎಂದು ಭಾವಿಸುತ್ತೇನೆ. ಅವುಗಳನ್ನು ಎಲ್ಲೆಡೆ ಬಳಸಲಾಗುತ್ತದೆ. ಸಣ್ಣ ಮತ್ತು ಉಪಯುಕ್ತ SQLite ನಿಂದ ಪ್ರಬಲವಾದ ಟೆರಾಡೇಟಾದವರೆಗೆ ಹಲವಾರು ವಿಭಿನ್ನ ಡೇಟಾಬೇಸ್‌ಗಳು ಲಭ್ಯವಿವೆ. ಆದರೆ ಡೇಟಾಬೇಸ್ ಹೇಗೆ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ ಎಂಬುದನ್ನು ವಿವರಿಸುವ ಕೆಲವು ಲೇಖನಗಳು ಮಾತ್ರ ಇವೆ. ಎಷ್ಟು ಕಡಿಮೆ ಫಲಿತಾಂಶಗಳಿವೆ ಎಂಬುದನ್ನು ನೋಡಲು "howdoesarelationaldabasework" ಅನ್ನು ಬಳಸಿಕೊಂಡು ನೀವೇ ಹುಡುಕಬಹುದು. ಇದಲ್ಲದೆ, ಈ ಲೇಖನಗಳು ಚಿಕ್ಕದಾಗಿದೆ. ನೀವು ಇತ್ತೀಚಿನ buzzy ತಂತ್ರಜ್ಞಾನಗಳನ್ನು (BigData, NoSQL ಅಥವಾ JavaScript) ಹುಡುಕುತ್ತಿದ್ದರೆ, ಅವುಗಳು ಹೇಗೆ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತವೆ ಎಂಬುದನ್ನು ವಿವರಿಸುವ ಹೆಚ್ಚು ಆಳವಾದ ಲೇಖನಗಳನ್ನು ನೀವು ಕಾಣುತ್ತೀರಿ.

ಸಂಬಂಧಿತ ಡೇಟಾಬೇಸ್‌ಗಳು ತುಂಬಾ ಹಳೆಯದಾಗಿದೆ ಮತ್ತು ವಿಶ್ವವಿದ್ಯಾಲಯದ ಕೋರ್ಸ್‌ಗಳು, ಸಂಶೋಧನಾ ಪ್ರಬಂಧಗಳು ಮತ್ತು ಪುಸ್ತಕಗಳ ಹೊರಗೆ ವಿವರಿಸಲು ತುಂಬಾ ನೀರಸವಾಗಿದೆಯೇ?

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

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

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

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

ನಿಮ್ಮಲ್ಲಿ ಹೆಚ್ಚು ಜ್ಞಾನವುಳ್ಳವರಿಗಾಗಿ, ಈ ಲೇಖನವನ್ನು 3 ಭಾಗಗಳಾಗಿ ವಿಂಗಡಿಸಲಾಗಿದೆ:

ಕಡಿಮೆ ಮಟ್ಟದ ಮತ್ತು ಉನ್ನತ ಮಟ್ಟದ ಡೇಟಾಬೇಸ್ ಘಟಕಗಳ ಅವಲೋಕನ
ಪ್ರಶ್ನೆ ಆಪ್ಟಿಮೈಸೇಶನ್ ಪ್ರಕ್ರಿಯೆಯ ಅವಲೋಕನ
ವಹಿವಾಟು ಮತ್ತು ಬಫರ್ ಪೂಲ್ ನಿರ್ವಹಣೆಯ ಅವಲೋಕನ

ಬೇಸಿಕ್ಸ್ ಗೆ ಹಿಂತಿರುಗಿ

ವರ್ಷಗಳ ಹಿಂದೆ (ಗ್ಯಾಲಕ್ಸಿಯಲ್ಲಿ ದೂರದ, ದೂರದ...), ಡೆವಲಪರ್‌ಗಳು ತಾವು ಕೋಡಿಂಗ್ ಮಾಡುತ್ತಿರುವ ಕಾರ್ಯಾಚರಣೆಗಳ ಸಂಖ್ಯೆಯನ್ನು ನಿಖರವಾಗಿ ತಿಳಿದುಕೊಳ್ಳಬೇಕಾಗಿತ್ತು. ಅವರು ತಮ್ಮ ಅಲ್ಗಾರಿದಮ್‌ಗಳು ಮತ್ತು ಡೇಟಾ ರಚನೆಗಳನ್ನು ಹೃದಯದಿಂದ ತಿಳಿದಿದ್ದರು ಏಕೆಂದರೆ ಅವರ ನಿಧಾನಗತಿಯ ಕಂಪ್ಯೂಟರ್‌ಗಳ CPU ಮತ್ತು ಮೆಮೊರಿಯನ್ನು ವ್ಯರ್ಥ ಮಾಡಲು ಅವರಿಗೆ ಸಾಧ್ಯವಾಗಲಿಲ್ಲ.

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

O(1) vs O(n2)

ಇತ್ತೀಚಿನ ದಿನಗಳಲ್ಲಿ, ಅನೇಕ ಡೆವಲಪರ್‌ಗಳು ಅಲ್ಗಾರಿದಮ್‌ಗಳ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯ ಬಗ್ಗೆ ಕಾಳಜಿ ವಹಿಸುವುದಿಲ್ಲ ... ಮತ್ತು ಅವರು ಸರಿ!

ಆದರೆ ನೀವು ಬಹಳಷ್ಟು ಡೇಟಾದೊಂದಿಗೆ ವ್ಯವಹರಿಸುವಾಗ (ನಾನು ಸಾವಿರಾರು ಮಾತನಾಡುತ್ತಿಲ್ಲ) ಅಥವಾ ನೀವು ಮಿಲಿಸೆಕೆಂಡ್‌ಗಳಲ್ಲಿ ಹೆಣಗಾಡುತ್ತಿದ್ದರೆ, ಈ ಪರಿಕಲ್ಪನೆಯನ್ನು ಅರ್ಥಮಾಡಿಕೊಳ್ಳುವುದು ನಿರ್ಣಾಯಕವಾಗುತ್ತದೆ. ಮತ್ತು ನೀವು ಊಹಿಸುವಂತೆ, ಡೇಟಾಬೇಸ್ಗಳು ಎರಡೂ ಸಂದರ್ಭಗಳಲ್ಲಿ ವ್ಯವಹರಿಸಬೇಕು! ಪಾಯಿಂಟ್ ಅನ್ನು ಪಡೆಯಲು ನಾನು ನಿಮಗೆ ಅಗತ್ಯಕ್ಕಿಂತ ಹೆಚ್ಚಿನ ಸಮಯವನ್ನು ಕಳೆಯುವಂತೆ ಮಾಡುವುದಿಲ್ಲ. ವೆಚ್ಚ-ಆಧಾರಿತ ಆಪ್ಟಿಮೈಸೇಶನ್ ಪರಿಕಲ್ಪನೆಯನ್ನು ನಂತರ ಅರ್ಥಮಾಡಿಕೊಳ್ಳಲು ಇದು ನಮಗೆ ಸಹಾಯ ಮಾಡುತ್ತದೆ (ವೆಚ್ಚ ಆಧಾರಿತ ಆಪ್ಟಿಮೈಜೇಷನ್).

ಪರಿಕಲ್ಪನೆ

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

ಉದಾಹರಣೆಗೆ, "ಈ ಅಲ್ಗಾರಿದಮ್ ಸಂಕೀರ್ಣತೆ O(some_function())" ಎಂದು ನಾನು ಹೇಳಿದಾಗ, ನಿರ್ದಿಷ್ಟ ಪ್ರಮಾಣದ ಡೇಟಾವನ್ನು ಪ್ರಕ್ರಿಯೆಗೊಳಿಸಲು ಅಲ್ಗಾರಿದಮ್‌ಗೆ ಕೆಲವು_ಫಂಕ್ಷನ್ (a_certain_amount_of_data) ಕಾರ್ಯಾಚರಣೆಗಳ ಅಗತ್ಯವಿದೆ ಎಂದರ್ಥ.

ಹೀಗೆ ಇದು ಮುಖ್ಯವಾದ ಡೇಟಾದ ಪ್ರಮಾಣವಲ್ಲ **, ಇಲ್ಲದಿದ್ದರೆ ** ಹೆಚ್ಚುತ್ತಿರುವ ಡೇಟಾ ಪರಿಮಾಣದೊಂದಿಗೆ ಕಾರ್ಯಾಚರಣೆಗಳ ಸಂಖ್ಯೆಯು ಹೇಗೆ ಹೆಚ್ಚಾಗುತ್ತದೆ. ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ನಿಖರವಾದ ಕಾರ್ಯಾಚರಣೆಗಳ ಸಂಖ್ಯೆಯನ್ನು ಒದಗಿಸುವುದಿಲ್ಲ, ಆದರೆ ಮರಣದಂಡನೆಯ ಸಮಯವನ್ನು ಅಂದಾಜು ಮಾಡಲು ಉತ್ತಮ ಮಾರ್ಗವಾಗಿದೆ.

ಈ ಗ್ರಾಫ್‌ನಲ್ಲಿ ನೀವು ವಿವಿಧ ರೀತಿಯ ಅಲ್ಗಾರಿದಮ್ ಸಮಯದ ಸಂಕೀರ್ಣತೆಗಳಿಗಾಗಿ ಇನ್‌ಪುಟ್ ಡೇಟಾದ ಮೊತ್ತದ ವಿರುದ್ಧ ಕಾರ್ಯಾಚರಣೆಗಳ ಸಂಖ್ಯೆಯನ್ನು ನೋಡಬಹುದು. ಅವುಗಳನ್ನು ಪ್ರದರ್ಶಿಸಲು ನಾನು ಲಾಗರಿಥಮಿಕ್ ಸ್ಕೇಲ್ ಅನ್ನು ಬಳಸಿದ್ದೇನೆ. ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ಡೇಟಾದ ಪ್ರಮಾಣವು ತ್ವರಿತವಾಗಿ 1 ರಿಂದ 1 ಬಿಲಿಯನ್‌ಗೆ ಹೆಚ್ಚಾಗುತ್ತದೆ. ನಾವು ಅದನ್ನು ನೋಡಬಹುದು:

O(1) ಅಥವಾ ಸ್ಥಿರವಾದ ಸಂಕೀರ್ಣತೆಯು ಸ್ಥಿರವಾಗಿರುತ್ತದೆ (ಇಲ್ಲದಿದ್ದರೆ ಅದನ್ನು ನಿರಂತರ ಸಂಕೀರ್ಣತೆ ಎಂದು ಕರೆಯಲಾಗುವುದಿಲ್ಲ).
O(ಲಾಗ್(n)) ಶತಕೋಟಿ ಡೇಟಾ ಇದ್ದರೂ ಸಹ ಕಡಿಮೆಯಿರುತ್ತದೆ.
ಕೆಟ್ಟ ಕಷ್ಟ - O(n2), ಅಲ್ಲಿ ಕಾರ್ಯಾಚರಣೆಗಳ ಸಂಖ್ಯೆಯು ವೇಗವಾಗಿ ಬೆಳೆಯುತ್ತದೆ.
ಇನ್ನೆರಡು ತೊಡಕುಗಳು ಅಷ್ಟೇ ಬೇಗ ಹೆಚ್ಚಾಗುತ್ತವೆ.

ಉದಾಹರಣೆಗಳು

ಸಣ್ಣ ಪ್ರಮಾಣದ ಡೇಟಾದೊಂದಿಗೆ, O(1) ಮತ್ತು O(n2) ನಡುವಿನ ವ್ಯತ್ಯಾಸವು ಅತ್ಯಲ್ಪವಾಗಿದೆ. ಉದಾಹರಣೆಗೆ, ನೀವು 2000 ಅಂಶಗಳನ್ನು ಪ್ರಕ್ರಿಯೆಗೊಳಿಸಲು ಅಗತ್ಯವಿರುವ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಹೊಂದಿದ್ದೀರಿ ಎಂದು ಹೇಳೋಣ.

O(1) ಅಲ್ಗಾರಿದಮ್ ನಿಮಗೆ 1 ಕಾರ್ಯಾಚರಣೆಯನ್ನು ವೆಚ್ಚ ಮಾಡುತ್ತದೆ
O(log(n)) ಅಲ್ಗಾರಿದಮ್ ನಿಮಗೆ 7 ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ವೆಚ್ಚ ಮಾಡುತ್ತದೆ
O(n) ಅಲ್ಗಾರಿದಮ್ ನಿಮಗೆ 2 ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ವೆಚ್ಚ ಮಾಡುತ್ತದೆ
O(n*log(n)) ಅಲ್ಗಾರಿದಮ್ ನಿಮಗೆ 14 ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ವೆಚ್ಚ ಮಾಡುತ್ತದೆ
O(n2) ಅಲ್ಗಾರಿದಮ್ ನಿಮಗೆ 4 ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ವೆಚ್ಚ ಮಾಡುತ್ತದೆ

O(1) ಮತ್ತು O(n2) ನಡುವಿನ ವ್ಯತ್ಯಾಸವು ದೊಡ್ಡದಾಗಿ ತೋರುತ್ತದೆ (4 ಮಿಲಿಯನ್ ಕಾರ್ಯಾಚರಣೆಗಳು) ಆದರೆ ನೀವು ಗರಿಷ್ಠ 2 ms ಕಳೆದುಕೊಳ್ಳುತ್ತೀರಿ, ನಿಮ್ಮ ಕಣ್ಣುಗಳನ್ನು ಮಿಟುಕಿಸುವ ಸಮಯ. ವಾಸ್ತವವಾಗಿ, ಆಧುನಿಕ ಸಂಸ್ಕಾರಕಗಳು ಪ್ರಕ್ರಿಯೆಗೊಳಿಸಬಹುದು ಪ್ರತಿ ಸೆಕೆಂಡಿಗೆ ನೂರಾರು ಮಿಲಿಯನ್ ಕಾರ್ಯಾಚರಣೆಗಳು. ಇದಕ್ಕಾಗಿಯೇ ಅನೇಕ ಐಟಿ ಯೋಜನೆಗಳಲ್ಲಿ ಕಾರ್ಯಕ್ಷಮತೆ ಮತ್ತು ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಯಾಗಿಲ್ಲ.

ನಾನು ಹೇಳಿದಂತೆ, ಬೃಹತ್ ಪ್ರಮಾಣದ ಡೇಟಾದೊಂದಿಗೆ ಕೆಲಸ ಮಾಡುವಾಗ ಈ ಪರಿಕಲ್ಪನೆಯನ್ನು ತಿಳಿದುಕೊಳ್ಳುವುದು ಇನ್ನೂ ಮುಖ್ಯವಾಗಿದೆ. ಈ ಸಮಯದಲ್ಲಿ ಅಲ್ಗಾರಿದಮ್ 1 ಅಂಶಗಳನ್ನು ಪ್ರಕ್ರಿಯೆಗೊಳಿಸಬೇಕಾದರೆ (ಡೇಟಾಬೇಸ್‌ಗೆ ಇದು ಹೆಚ್ಚು ಅಲ್ಲ):

O(1) ಅಲ್ಗಾರಿದಮ್ ನಿಮಗೆ 1 ಕಾರ್ಯಾಚರಣೆಯನ್ನು ವೆಚ್ಚ ಮಾಡುತ್ತದೆ
O(log(n)) ಅಲ್ಗಾರಿದಮ್ ನಿಮಗೆ 14 ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ವೆಚ್ಚ ಮಾಡುತ್ತದೆ
O(n) ಅಲ್ಗಾರಿದಮ್ ನಿಮಗೆ 1 ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ವೆಚ್ಚ ಮಾಡುತ್ತದೆ
O(n*log(n)) ಅಲ್ಗಾರಿದಮ್ ನಿಮಗೆ 14 ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ವೆಚ್ಚ ಮಾಡುತ್ತದೆ
O(n2) ಅಲ್ಗಾರಿದಮ್ ನಿಮಗೆ 1 ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ವೆಚ್ಚ ಮಾಡುತ್ತದೆ

ನಾನು ಗಣಿತವನ್ನು ಮಾಡಿಲ್ಲ, ಆದರೆ O(n2) ಅಲ್ಗಾರಿದಮ್‌ನೊಂದಿಗೆ ನೀವು ಕಾಫಿ ಕುಡಿಯಲು ಸಮಯವಿದೆ ಎಂದು ನಾನು ಹೇಳುತ್ತೇನೆ (ಎರಡು ಸಹ!). ಡೇಟಾ ವಾಲ್ಯೂಮ್‌ಗೆ ನೀವು ಇನ್ನೊಂದು 0 ಅನ್ನು ಸೇರಿಸಿದರೆ, ನೀವು ಚಿಕ್ಕನಿದ್ರೆ ತೆಗೆದುಕೊಳ್ಳಲು ಸಮಯವನ್ನು ಹೊಂದಿರುತ್ತೀರಿ.

ಆಳಕ್ಕೆ ಹೋಗೋಣ

ಉಲ್ಲೇಖಕ್ಕಾಗಿ:

ಉತ್ತಮ ಹ್ಯಾಶ್ ಟೇಬಲ್ ಲುಕಪ್ O(1) ನಲ್ಲಿ ಒಂದು ಅಂಶವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ.
ಸಮತೋಲಿತ ಮರವನ್ನು ಹುಡುಕುವುದು O(log(n)) ನಲ್ಲಿ ಫಲಿತಾಂಶಗಳನ್ನು ನೀಡುತ್ತದೆ.
ಒಂದು ಶ್ರೇಣಿಯನ್ನು ಹುಡುಕುವುದು O(n) ನಲ್ಲಿ ಫಲಿತಾಂಶಗಳನ್ನು ನೀಡುತ್ತದೆ.
ಅತ್ಯುತ್ತಮ ವಿಂಗಡಣೆ ಅಲ್ಗಾರಿದಮ್‌ಗಳು O(n*log(n)) ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿವೆ.
ಕೆಟ್ಟ ವಿಂಗಡಣೆ ಅಲ್ಗಾರಿದಮ್ O(n2) ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿದೆ.

ಗಮನಿಸಿ: ಈ ಕೆಳಗಿನ ಭಾಗಗಳಲ್ಲಿ ನಾವು ಈ ಅಲ್ಗಾರಿದಮ್‌ಗಳು ಮತ್ತು ಡೇಟಾ ರಚನೆಗಳನ್ನು ನೋಡುತ್ತೇವೆ.

ಅಲ್ಗಾರಿದಮ್ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯ ಹಲವಾರು ವಿಧಗಳಿವೆ:

ಸರಾಸರಿ ಪ್ರಕರಣದ ಸನ್ನಿವೇಶ
ಅತ್ಯುತ್ತಮ ಸನ್ನಿವೇಶ
ಮತ್ತು ಕೆಟ್ಟ ಸನ್ನಿವೇಶ

ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಸಾಮಾನ್ಯವಾಗಿ ಕೆಟ್ಟ ಸನ್ನಿವೇಶವಾಗಿದೆ.

ನಾನು ಅಲ್ಗಾರಿದಮ್‌ನ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯ ಬಗ್ಗೆ ಮಾತ್ರ ಮಾತನಾಡುತ್ತಿದ್ದೆ, ಆದರೆ ಸಂಕೀರ್ಣತೆಯು ಇದಕ್ಕೆ ಅನ್ವಯಿಸುತ್ತದೆ:

ಅಲ್ಗಾರಿದಮ್ನ ಮೆಮೊರಿ ಬಳಕೆ
ಡಿಸ್ಕ್ I/O ಬಳಕೆ ಅಲ್ಗಾರಿದಮ್

ಸಹಜವಾಗಿ, n2 ಗಿಂತ ಕೆಟ್ಟದಾದ ತೊಡಕುಗಳಿವೆ, ಉದಾಹರಣೆಗೆ:

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

ಗಮನಿಸಿ: ನಾನು ನಿಮಗೆ ದೊಡ್ಡ O ಪದನಾಮದ ನಿಜವಾದ ವ್ಯಾಖ್ಯಾನವನ್ನು ನೀಡಿಲ್ಲ, ಕೇವಲ ಒಂದು ಕಲ್ಪನೆ. ನೀವು ಈ ಲೇಖನವನ್ನು ಓದಬಹುದು ವಿಕಿಪೀಡಿಯ ನೈಜ (ಅಸಿಂಪ್ಟೋಟಿಕ್) ವ್ಯಾಖ್ಯಾನಕ್ಕಾಗಿ.

ವಿಲೀನಗೊಳಿಸು

ನೀವು ಸಂಗ್ರಹವನ್ನು ವಿಂಗಡಿಸಬೇಕಾದಾಗ ನೀವು ಏನು ಮಾಡುತ್ತೀರಿ? ಏನು? ನೀವು sort() ಕಾರ್ಯವನ್ನು ಕರೆಯುತ್ತೀರಿ... ಸರಿ, ಉತ್ತಮ ಉತ್ತರ... ಆದರೆ ಡೇಟಾಬೇಸ್‌ಗಾಗಿ, ಈ ರೀತಿಯ () ಕಾರ್ಯವು ಹೇಗೆ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ ಎಂಬುದನ್ನು ನೀವು ಅರ್ಥಮಾಡಿಕೊಳ್ಳಬೇಕು.

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

ವಿಲೀನಗೊಳ್ಳಲು

ಅನೇಕ ಉಪಯುಕ್ತ ಅಲ್ಗಾರಿದಮ್‌ಗಳಂತೆ, ವಿಲೀನ ವಿಂಗಡಣೆಯು ಒಂದು ಟ್ರಿಕ್‌ನ ಮೇಲೆ ಅವಲಂಬಿತವಾಗಿದೆ: N/2 ಗಾತ್ರದ 2 ವಿಂಗಡಿಸಲಾದ ಸರಣಿಗಳನ್ನು N-ಎಲಿಮೆಂಟ್ ವಿಂಗಡಿಸಲಾದ ಅರೇಗೆ ಸಂಯೋಜಿಸುವುದು N ಕಾರ್ಯಾಚರಣೆಗಳಿಗೆ ಮಾತ್ರ ವೆಚ್ಚವಾಗುತ್ತದೆ. ಈ ಕಾರ್ಯಾಚರಣೆಯನ್ನು ವಿಲೀನ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ.

ಸರಳ ಉದಾಹರಣೆಯೊಂದಿಗೆ ಇದರ ಅರ್ಥವನ್ನು ನೋಡೋಣ:

ಅಂತಿಮ ವಿಂಗಡಿಸಲಾದ 8-ಅಂಶಗಳ ಸರಣಿಯನ್ನು ನಿರ್ಮಿಸಲು, ನೀವು 2 4-ಅಂಶಗಳ ಸರಣಿಗಳ ಮೇಲೆ ಒಮ್ಮೆ ಮಾತ್ರ ಪುನರಾವರ್ತಿಸುವ ಅಗತ್ಯವಿದೆ ಎಂದು ಈ ಅಂಕಿ ತೋರಿಸುತ್ತದೆ. ಎರಡೂ 4-ಎಲಿಮೆಂಟ್ ಅರೇಗಳನ್ನು ಈಗಾಗಲೇ ವಿಂಗಡಿಸಿರುವುದರಿಂದ:

1) ನೀವು ಪ್ರಸ್ತುತ ಅಂಶಗಳನ್ನು ಎರಡು ಸರಣಿಗಳಲ್ಲಿ ಹೋಲಿಸಿ (ಆರಂಭದಲ್ಲಿ ಪ್ರಸ್ತುತ = ಮೊದಲ)
2) ನಂತರ ಅದನ್ನು 8 ಅಂಶಗಳ ರಚನೆಗೆ ಹಾಕಲು ಚಿಕ್ಕದನ್ನು ತೆಗೆದುಕೊಳ್ಳಿ
3) ಮತ್ತು ನೀವು ಚಿಕ್ಕ ಅಂಶವನ್ನು ತೆಗೆದುಕೊಂಡ ರಚನೆಯ ಮುಂದಿನ ಅಂಶಕ್ಕೆ ಸರಿಸಿ
ಮತ್ತು ನೀವು ಸರಣಿಗಳಲ್ಲಿ ಒಂದರ ಕೊನೆಯ ಅಂಶವನ್ನು ತಲುಪುವವರೆಗೆ 1,2,3 ಅನ್ನು ಪುನರಾವರ್ತಿಸಿ.
ನಂತರ ನೀವು ಇತರ ರಚನೆಯ ಉಳಿದ ಅಂಶಗಳನ್ನು 8 ಅಂಶಗಳ ರಚನೆಯಲ್ಲಿ ಇರಿಸಲು ತೆಗೆದುಕೊಳ್ಳುತ್ತೀರಿ.

ಇದು ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ ಏಕೆಂದರೆ ಎರಡೂ 4-ಎಲಿಮೆಂಟ್ ಅರೇಗಳನ್ನು ವಿಂಗಡಿಸಲಾಗಿದೆ ಮತ್ತು ಆದ್ದರಿಂದ ನೀವು ಆ ಅರೇಗಳಲ್ಲಿ "ಹಿಂತಿರುಗಿ" ಮಾಡಬೇಕಾಗಿಲ್ಲ.

ಈಗ ನಾವು ಟ್ರಿಕ್ ಅನ್ನು ಅರ್ಥಮಾಡಿಕೊಂಡಿದ್ದೇವೆ, ವಿಲೀನಕ್ಕಾಗಿ ನನ್ನ ಸೂಡೊಕೋಡ್ ಇಲ್ಲಿದೆ:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

ವಿಲೀನ ವಿಂಗಡಣೆಯು ಸಮಸ್ಯೆಯನ್ನು ಸಣ್ಣ ಸಮಸ್ಯೆಗಳಾಗಿ ಒಡೆಯುತ್ತದೆ ಮತ್ತು ನಂತರ ಮೂಲ ಸಮಸ್ಯೆಯ ಫಲಿತಾಂಶವನ್ನು ಪಡೆಯಲು ಸಣ್ಣ ಸಮಸ್ಯೆಗಳ ಫಲಿತಾಂಶಗಳನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ (ಗಮನಿಸಿ: ಈ ರೀತಿಯ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ವಿಭಜಿಸಿ ಮತ್ತು ವಶಪಡಿಸಿಕೊಳ್ಳುವುದು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ). ಈ ಅಲ್ಗಾರಿದಮ್ ನಿಮಗೆ ಅರ್ಥವಾಗದಿದ್ದರೆ, ಚಿಂತಿಸಬೇಡಿ; ನಾನು ಅದನ್ನು ಮೊದಲ ಬಾರಿಗೆ ನೋಡಿದಾಗ ನನಗೆ ಅರ್ಥವಾಗಲಿಲ್ಲ. ಇದು ನಿಮಗೆ ಸಹಾಯ ಮಾಡಬಹುದಾದರೆ, ನಾನು ಈ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಎರಡು-ಹಂತದ ಅಲ್ಗಾರಿದಮ್ ಆಗಿ ನೋಡುತ್ತೇನೆ:

ವಿಭಾಗ ಹಂತ, ಅಲ್ಲಿ ರಚನೆಯನ್ನು ಸಣ್ಣ ಸರಣಿಗಳಾಗಿ ವಿಂಗಡಿಸಲಾಗಿದೆ
ವಿಂಗಡಣೆಯ ಹಂತವು ಸಣ್ಣ ಅರೇಗಳನ್ನು ಒಟ್ಟುಗೂಡಿಸಿ (ಯೂನಿಯನ್ ಬಳಸಿ) ದೊಡ್ಡ ಶ್ರೇಣಿಯನ್ನು ರೂಪಿಸುತ್ತದೆ.

ವಿಭಾಗ ಹಂತ

ವಿಭಜನೆಯ ಹಂತದಲ್ಲಿ, ರಚನೆಯನ್ನು 3 ಹಂತಗಳಲ್ಲಿ ಏಕೀಕೃತ ಸರಣಿಗಳಾಗಿ ವಿಂಗಡಿಸಲಾಗಿದೆ. ಹಂತಗಳ ಔಪಚಾರಿಕ ಸಂಖ್ಯೆಯು ಲಾಗ್(N) ಆಗಿದೆ (N=8 ರಿಂದ, ಲಾಗ್(N) = 3).

ನನಗೆ ಇದು ಹೇಗೆ ಗೊತ್ತು?

ನಾನು ಮೇಧಾವಿ! ಒಂದು ಪದದಲ್ಲಿ - ಗಣಿತ. ಕಲ್ಪನೆಯೆಂದರೆ ಪ್ರತಿ ಹಂತವು ಮೂಲ ರಚನೆಯ ಗಾತ್ರವನ್ನು 2 ರಿಂದ ಭಾಗಿಸುತ್ತದೆ. ಹಂತಗಳ ಸಂಖ್ಯೆಯು ಮೂಲ ರಚನೆಯನ್ನು ನೀವು ಎಷ್ಟು ಬಾರಿ ವಿಂಗಡಿಸಬಹುದು. ಇದು ಲಾಗರಿಥಮ್‌ನ ನಿಖರವಾದ ವ್ಯಾಖ್ಯಾನವಾಗಿದೆ (ಬೇಸ್ 2).

ವಿಂಗಡಿಸುವ ಹಂತ

ವಿಂಗಡಿಸುವ ಹಂತದಲ್ಲಿ, ನೀವು ಏಕೀಕೃತ (ಏಕ-ಅಂಶ) ಸರಣಿಗಳೊಂದಿಗೆ ಪ್ರಾರಂಭಿಸುತ್ತೀರಿ. ಪ್ರತಿ ಹಂತದ ಸಮಯದಲ್ಲಿ ನೀವು ಬಹು ವಿಲೀನ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಅನ್ವಯಿಸುತ್ತೀರಿ ಮತ್ತು ಒಟ್ಟು ವೆಚ್ಚವು N = 8 ಕಾರ್ಯಾಚರಣೆಗಳು:

ಮೊದಲ ಹಂತದಲ್ಲಿ ನೀವು 4 ವಿಲೀನಗಳನ್ನು ಹೊಂದಿದ್ದೀರಿ, ಪ್ರತಿಯೊಂದೂ 2 ಕಾರ್ಯಾಚರಣೆಗಳಿಗೆ ವೆಚ್ಚವಾಗುತ್ತದೆ
ಎರಡನೇ ಹಂತದಲ್ಲಿ ನೀವು 2 ವಿಲೀನಗಳನ್ನು ಹೊಂದಿದ್ದೀರಿ, ಪ್ರತಿಯೊಂದೂ 4 ಕಾರ್ಯಾಚರಣೆಗಳಿಗೆ ವೆಚ್ಚವಾಗುತ್ತದೆ
ಮೂರನೇ ಹಂತದಲ್ಲಿ ನೀವು 1 ವಿಲೀನವನ್ನು ಹೊಂದಿದ್ದೀರಿ ಅದು 8 ಕಾರ್ಯಾಚರಣೆಗಳಿಗೆ ವೆಚ್ಚವಾಗುತ್ತದೆ

ಲಾಗ್ (N) ಹಂತಗಳು ಇರುವುದರಿಂದ, ಒಟ್ಟು ವೆಚ್ಚ ಎನ್ * ಲಾಗ್ (ಎನ್) ಕಾರ್ಯಾಚರಣೆಗಳು.

ವಿಲೀನ ರೀತಿಯ ಪ್ರಯೋಜನಗಳು

ಈ ಅಲ್ಗಾರಿದಮ್ ಏಕೆ ಶಕ್ತಿಯುತವಾಗಿದೆ?

ಏಕೆಂದರೆ:

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

ಗಮನಿಸಿ: ಈ ರೀತಿಯ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಕರೆಯಲಾಗುತ್ತದೆ in-ಸ್ಥಾನ (ಹೆಚ್ಚುವರಿ ಮೆಮೊರಿ ಇಲ್ಲದೆ ವಿಂಗಡಿಸುವುದು).

ಗಮನಾರ್ಹವಾದ ಡಿಸ್ಕ್ I/O ಓವರ್‌ಹೆಡ್‌ಗೆ ಒಳಪಡದೆ ಅದೇ ಸಮಯದಲ್ಲಿ ಡಿಸ್ಕ್ ಸ್ಪೇಸ್ ಮತ್ತು ಸ್ವಲ್ಪ ಪ್ರಮಾಣದ ಮೆಮೊರಿಯನ್ನು ಬಳಸಲು ನೀವು ಅದನ್ನು ಬದಲಾಯಿಸಬಹುದು. ಪ್ರಸ್ತುತ ಪ್ರಕ್ರಿಯೆಯಲ್ಲಿರುವ ಭಾಗಗಳನ್ನು ಮಾತ್ರ ಮೆಮೊರಿಗೆ ಲೋಡ್ ಮಾಡುವುದು ಕಲ್ಪನೆ. ನೀವು ಕೇವಲ 100-ಮೆಗಾಬೈಟ್ ಮೆಮೊರಿ ಬಫರ್‌ನೊಂದಿಗೆ ಬಹು-ಗಿಗಾಬೈಟ್ ಟೇಬಲ್ ಅನ್ನು ವಿಂಗಡಿಸಬೇಕಾದಾಗ ಇದು ಮುಖ್ಯವಾಗಿದೆ.

ಗಮನಿಸಿ: ಈ ರೀತಿಯ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಕರೆಯಲಾಗುತ್ತದೆ ಬಾಹ್ಯ ವಿಂಗಡಣೆ.

ಬಹು ಪ್ರಕ್ರಿಯೆಗಳು/ಥ್ರೆಡ್‌ಗಳು/ಸರ್ವರ್‌ಗಳಲ್ಲಿ ರನ್ ಮಾಡಲು ನೀವು ಅದನ್ನು ಬದಲಾಯಿಸಬಹುದು.

ಉದಾಹರಣೆಗೆ, ವಿತರಿಸಿದ ವಿಲೀನ ವಿಂಗಡಣೆಯು ಪ್ರಮುಖ ಅಂಶಗಳಲ್ಲಿ ಒಂದಾಗಿದೆ ಹ್ಯಾಡ್ಲೂಪ್ (ಇದು ದೊಡ್ಡ ಡೇಟಾದಲ್ಲಿ ರಚನೆಯಾಗಿದೆ).

ಈ ಅಲ್ಗಾರಿದಮ್ ಸೀಸವನ್ನು ಚಿನ್ನವಾಗಿ ಪರಿವರ್ತಿಸಬಹುದು (ನಿಜವಾಗಿಯೂ!).

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

ಅರೇ, ಟ್ರೀ ಮತ್ತು ಹ್ಯಾಶ್ ಟೇಬಲ್

ಈಗ ನಾವು ಸಮಯದ ಸಂಕೀರ್ಣತೆ ಮತ್ತು ವಿಂಗಡಣೆಯ ಕಲ್ಪನೆಯನ್ನು ಅರ್ಥಮಾಡಿಕೊಂಡಿದ್ದೇವೆ, ನಾನು ನಿಮಗೆ 3 ಡೇಟಾ ರಚನೆಗಳ ಬಗ್ಗೆ ಹೇಳಬೇಕು. ಅವರು ಏಕೆಂದರೆ ಇದು ಮುಖ್ಯವಾಗಿದೆ ಆಧುನಿಕ ಡೇಟಾಬೇಸ್‌ಗಳ ಆಧಾರವಾಗಿದೆ. ನಾನು ಪರಿಕಲ್ಪನೆಯನ್ನು ಸಹ ಪರಿಚಯಿಸುತ್ತೇನೆ ಡೇಟಾಬೇಸ್ ಸೂಚ್ಯಂಕ.

ಮಾಸ್ಸಿವ್

ಎರಡು ಆಯಾಮದ ರಚನೆಯು ಸರಳವಾದ ಡೇಟಾ ರಚನೆಯಾಗಿದೆ. ಟೇಬಲ್ ಅನ್ನು ಒಂದು ಶ್ರೇಣಿ ಎಂದು ಪರಿಗಣಿಸಬಹುದು. ಉದಾಹರಣೆಗೆ:

ಈ 2 ಆಯಾಮದ ರಚನೆಯು ಸಾಲುಗಳು ಮತ್ತು ಕಾಲಮ್‌ಗಳನ್ನು ಹೊಂದಿರುವ ಟೇಬಲ್ ಆಗಿದೆ:

ಪ್ರತಿಯೊಂದು ಸಾಲು ಒಂದು ಘಟಕವನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ
ಕಾಲಮ್‌ಗಳು ಅಸ್ತಿತ್ವವನ್ನು ವಿವರಿಸುವ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಸಂಗ್ರಹಿಸುತ್ತವೆ.
ಪ್ರತಿಯೊಂದು ಕಾಲಮ್ ನಿರ್ದಿಷ್ಟ ಪ್ರಕಾರದ ಡೇಟಾವನ್ನು ಸಂಗ್ರಹಿಸುತ್ತದೆ (ಪೂರ್ಣಾಂಕ, ಸ್ಟ್ರಿಂಗ್, ದಿನಾಂಕ...).

ಡೇಟಾವನ್ನು ಸಂಗ್ರಹಿಸಲು ಮತ್ತು ದೃಶ್ಯೀಕರಿಸಲು ಇದು ಅನುಕೂಲಕರವಾಗಿದೆ, ಆದಾಗ್ಯೂ, ನೀವು ನಿರ್ದಿಷ್ಟ ಮೌಲ್ಯವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕಾದಾಗ, ಇದು ಸೂಕ್ತವಲ್ಲ.

ಉದಾಹರಣೆಗೆ, ನೀವು ಯುಕೆಯಲ್ಲಿ ಕೆಲಸ ಮಾಡುವ ಎಲ್ಲ ಹುಡುಗರನ್ನು ಹುಡುಕಲು ಬಯಸಿದರೆ, ಆ ಸಾಲು ಯುಕೆಗೆ ಸೇರಿದೆಯೇ ಎಂದು ನಿರ್ಧರಿಸಲು ನೀವು ಪ್ರತಿ ಸಾಲನ್ನು ನೋಡಬೇಕು. ಇದು ನಿಮಗೆ N ವಹಿವಾಟುಗಳನ್ನು ವೆಚ್ಚ ಮಾಡುತ್ತದೆಅಲ್ಲಿ N - ಸಾಲುಗಳ ಸಂಖ್ಯೆ, ಇದು ಕೆಟ್ಟದ್ದಲ್ಲ, ಆದರೆ ವೇಗವಾದ ಮಾರ್ಗವಿದೆಯೇ? ಈಗ ನಾವು ಮರಗಳ ಪರಿಚಯ ಮಾಡಿಕೊಳ್ಳುವ ಸಮಯ ಬಂದಿದೆ.

ಗಮನಿಸಿ: ಹೆಚ್ಚಿನ ಆಧುನಿಕ ಡೇಟಾಬೇಸ್‌ಗಳು ಕೋಷ್ಟಕಗಳನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಸಂಗ್ರಹಿಸಲು ವಿಸ್ತೃತ ಸರಣಿಗಳನ್ನು ಒದಗಿಸುತ್ತವೆ: ರಾಶಿ-ಸಂಘಟಿತ ಕೋಷ್ಟಕಗಳು ಮತ್ತು ಸೂಚ್ಯಂಕ-ಸಂಘಟಿತ ಕೋಷ್ಟಕಗಳು. ಆದರೆ ಕಾಲಮ್‌ಗಳ ಗುಂಪಿನಲ್ಲಿ ನಿರ್ದಿಷ್ಟ ಸ್ಥಿತಿಯನ್ನು ತ್ವರಿತವಾಗಿ ಕಂಡುಹಿಡಿಯುವ ಸಮಸ್ಯೆಯನ್ನು ಇದು ಬದಲಾಯಿಸುವುದಿಲ್ಲ.

ಡೇಟಾಬೇಸ್ ಮರ ಮತ್ತು ಸೂಚ್ಯಂಕ

ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ವಿಶೇಷ ಆಸ್ತಿಯನ್ನು ಹೊಂದಿರುವ ಬೈನರಿ ಮರವಾಗಿದೆ, ಪ್ರತಿ ನೋಡ್‌ನಲ್ಲಿನ ಕೀಲಿಯು ಹೀಗಿರಬೇಕು:

ಎಡ ಸಬ್‌ಟ್ರೀಯಲ್ಲಿ ಸಂಗ್ರಹವಾಗಿರುವ ಎಲ್ಲಾ ಕೀಗಳಿಗಿಂತ ಹೆಚ್ಚು
ಬಲ ಸಬ್‌ಟ್ರೀಯಲ್ಲಿ ಸಂಗ್ರಹವಾಗಿರುವ ಎಲ್ಲಾ ಕೀಗಳಿಗಿಂತ ಕಡಿಮೆ

ಇದರ ಅರ್ಥವನ್ನು ದೃಷ್ಟಿಗೋಚರವಾಗಿ ನೋಡೋಣ

ಐಡಿಯಾ

ಈ ಮರವು N = 15 ಅಂಶಗಳನ್ನು ಹೊಂದಿದೆ. ನಾನು 208 ಗಾಗಿ ಹುಡುಕುತ್ತಿದ್ದೇನೆ ಎಂದು ಹೇಳೋಣ:

ನಾನು 136 ಕೀ ಇರುವ ರೂಟ್‌ನಿಂದ ಪ್ರಾರಂಭಿಸುತ್ತೇನೆ. 136<208 ರಿಂದ, ನಾನು ನೋಡ್ 136 ರ ಬಲ ಸಬ್‌ಟ್ರೀಯನ್ನು ನೋಡುತ್ತೇನೆ.
398>208 ಆದ್ದರಿಂದ ನಾನು ನೋಡ್ 398 ನ ಎಡ ಉಪಟ್ರೀಯನ್ನು ನೋಡುತ್ತಿದ್ದೇನೆ
250>208 ಆದ್ದರಿಂದ ನಾನು ನೋಡ್ 250 ನ ಎಡ ಉಪಟ್ರೀಯನ್ನು ನೋಡುತ್ತಿದ್ದೇನೆ
200<208, ಆದ್ದರಿಂದ ನಾನು ನೋಡ್ 200 ರ ಬಲ ಸಬ್‌ಟ್ರೀಯನ್ನು ನೋಡುತ್ತಿದ್ದೇನೆ. ಆದರೆ 200 ಗೆ ಸರಿಯಾದ ಸಬ್‌ಟ್ರೀ ಇಲ್ಲ, ಮೌಲ್ಯವು ಅಸ್ತಿತ್ವದಲ್ಲಿಲ್ಲ (ಏಕೆಂದರೆ ಅದು ಅಸ್ತಿತ್ವದಲ್ಲಿದ್ದರೆ, ಅದು ಸರಿಯಾದ ಸಬ್ಟ್ರೀ 200 ರಲ್ಲಿ ಇರುತ್ತದೆ).

ಈಗ ನಾನು 40 ಗಾಗಿ ಹುಡುಕುತ್ತಿದ್ದೇನೆ ಎಂದು ಹೇಳೋಣ

ನಾನು 136 ಕೀ ಇರುವ ಮೂಲದಿಂದ ಪ್ರಾರಂಭಿಸುತ್ತೇನೆ. 136 > 40 ರಿಂದ, ನಾನು ನೋಡ್ 136 ನ ಎಡ ಉಪಟ್ರೀಯನ್ನು ನೋಡುತ್ತೇನೆ.
80 > 40, ಆದ್ದರಿಂದ ನಾನು ನೋಡ್ 80 ರ ಎಡ ಉಪಟ್ರೀಯನ್ನು ನೋಡುತ್ತಿದ್ದೇನೆ
40= 40, ನೋಡ್ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ. ನಾನು ನೋಡ್‌ನ ಒಳಗಿನ ಸಾಲು ID ಯನ್ನು ಹಿಂಪಡೆಯುತ್ತೇನೆ (ಚಿತ್ರದಲ್ಲಿ ತೋರಿಸಲಾಗಿಲ್ಲ) ಮತ್ತು ಕೊಟ್ಟಿರುವ ಸಾಲು ID ಗಾಗಿ ಟೇಬಲ್‌ನಲ್ಲಿ ನೋಡುತ್ತೇನೆ.
ಸಾಲು ಐಡಿಯನ್ನು ತಿಳಿದುಕೊಳ್ಳುವುದರಿಂದ ಟೇಬಲ್‌ನಲ್ಲಿ ಡೇಟಾ ಎಲ್ಲಿದೆ ಎಂಬುದನ್ನು ನಿಖರವಾಗಿ ತಿಳಿಯಲು ನನಗೆ ಅನುಮತಿಸುತ್ತದೆ, ಹಾಗಾಗಿ ನಾನು ಅದನ್ನು ತಕ್ಷಣವೇ ಹಿಂಪಡೆಯಬಹುದು.

ಕೊನೆಯಲ್ಲಿ, ಎರಡೂ ಹುಡುಕಾಟಗಳು ನನಗೆ ಮರದೊಳಗಿನ ಹಂತಗಳ ಸಂಖ್ಯೆಯನ್ನು ವೆಚ್ಚ ಮಾಡುತ್ತವೆ. ನೀವು ವಿಲೀನ ವಿಂಗಡಣೆಯ ಭಾಗವನ್ನು ಎಚ್ಚರಿಕೆಯಿಂದ ಓದಿದರೆ, ಲಾಗ್ (N) ಹಂತಗಳಿವೆ ಎಂದು ನೀವು ನೋಡಬೇಕು. ಇದು ತಿರುಗುತ್ತದೆ, ಹುಡುಕಾಟ ವೆಚ್ಚದ ಲಾಗ್ (N), ಕೆಟ್ಟದ್ದಲ್ಲ!

ನಮ್ಮ ಸಮಸ್ಯೆಗೆ ಹಿಂತಿರುಗಿ ನೋಡೋಣ

ಆದರೆ ಇದು ತುಂಬಾ ಅಮೂರ್ತವಾಗಿದೆ, ಆದ್ದರಿಂದ ನಮ್ಮ ಸಮಸ್ಯೆಗೆ ಹಿಂತಿರುಗಿ ನೋಡೋಣ. ಸರಳ ಪೂರ್ಣಾಂಕದ ಬದಲಿಗೆ, ಹಿಂದಿನ ಕೋಷ್ಟಕದಲ್ಲಿ ಯಾರೊಬ್ಬರ ದೇಶವನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಕಲ್ಪಿಸಿಕೊಳ್ಳಿ. ಟೇಬಲ್‌ನ "ದೇಶ" ಕ್ಷೇತ್ರವನ್ನು (ಕಾಲಮ್ 3) ಹೊಂದಿರುವ ಮರವನ್ನು ನೀವು ಹೊಂದಿದ್ದೀರಿ ಎಂದು ಹೇಳೋಣ:

ಯುಕೆಯಲ್ಲಿ ಯಾರು ಕೆಲಸ ಮಾಡುತ್ತಾರೆ ಎಂಬುದನ್ನು ನೀವು ತಿಳಿದುಕೊಳ್ಳಲು ಬಯಸಿದರೆ
ಗ್ರೇಟ್ ಬ್ರಿಟನ್ ಅನ್ನು ಪ್ರತಿನಿಧಿಸುವ ನೋಡ್ ಅನ್ನು ಪಡೆಯಲು ನೀವು ಮರವನ್ನು ನೋಡುತ್ತೀರಿ
"UKnode" ಒಳಗೆ ನೀವು UK ಕೆಲಸಗಾರರ ದಾಖಲೆಗಳ ಸ್ಥಳವನ್ನು ಕಾಣಬಹುದು.

ನೀವು ರಚನೆಯನ್ನು ನೇರವಾಗಿ ಬಳಸಿದರೆ ಈ ಹುಡುಕಾಟವು N ಕಾರ್ಯಾಚರಣೆಗಳ ಬದಲಿಗೆ ಲಾಗ್ (N) ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ವೆಚ್ಚ ಮಾಡುತ್ತದೆ. ನೀವು ಈಗ ಪ್ರಸ್ತುತಪಡಿಸಿದ್ದು ಡೇಟಾಬೇಸ್ ಸೂಚ್ಯಂಕ.

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

ಬಿ+ಟ್ರೀ ಇಂಡೆಕ್ಸ್

ನಿರ್ದಿಷ್ಟ ಮೌಲ್ಯವನ್ನು ಪಡೆಯಲು ಈ ಮರವು ಉತ್ತಮವಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತಿರುವಾಗ, ನಿಮಗೆ ಅಗತ್ಯವಿರುವಾಗ ದೊಡ್ಡ ಸಮಸ್ಯೆ ಇದೆ ಎರಡು ಮೌಲ್ಯಗಳ ನಡುವೆ ಬಹು ಅಂಶಗಳನ್ನು ಪಡೆಯಿರಿ. ಇದು O (N) ವೆಚ್ಚವಾಗುತ್ತದೆ ಏಕೆಂದರೆ ನೀವು ಮರದ ಪ್ರತಿಯೊಂದು ನೋಡ್ ಅನ್ನು ನೋಡಬೇಕು ಮತ್ತು ಅದು ಈ ಎರಡು ಮೌಲ್ಯಗಳ ನಡುವೆ ಇದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಬೇಕು (ಉದಾ. ಮರದ ಆದೇಶದ ಪ್ರಯಾಣದೊಂದಿಗೆ). ಇದಲ್ಲದೆ, ನೀವು ಸಂಪೂರ್ಣ ಮರವನ್ನು ಓದಬೇಕಾಗಿರುವುದರಿಂದ ಈ ಕಾರ್ಯಾಚರಣೆಯು ಡಿಸ್ಕ್ I/O ಸ್ನೇಹಿಯಾಗಿಲ್ಲ. ಸಮರ್ಥವಾಗಿ ಕಾರ್ಯಗತಗೊಳಿಸಲು ನಾವು ಒಂದು ಮಾರ್ಗವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು ಶ್ರೇಣಿಯ ವಿನಂತಿ. ಈ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು, ಆಧುನಿಕ ದತ್ತಸಂಚಯಗಳು B+Tree ಎಂಬ ಹಿಂದಿನ ಮರದ ಮಾರ್ಪಡಿಸಿದ ಆವೃತ್ತಿಯನ್ನು ಬಳಸುತ್ತವೆ. ಬಿ+ಟ್ರೀ ಮರದಲ್ಲಿ:

ಕೇವಲ ಕಡಿಮೆ ನೋಡ್‌ಗಳು (ಎಲೆಗಳು) ಮಾಹಿತಿಯನ್ನು ಸಂಗ್ರಹಿಸಿ (ಸಂಬಂಧಿತ ಕೋಷ್ಟಕದಲ್ಲಿನ ಸಾಲುಗಳ ಸ್ಥಳ)
ಉಳಿದ ನೋಡ್‌ಗಳು ಇಲ್ಲಿವೆ ರೂಟಿಂಗ್ಗಾಗಿ ಸರಿಯಾದ ನೋಡ್‌ಗೆ ಹುಡುಕಾಟದ ಸಮಯದಲ್ಲಿ.

ನೀವು ನೋಡುವಂತೆ, ಇಲ್ಲಿ ಹೆಚ್ಚಿನ ನೋಡ್‌ಗಳಿವೆ (ಎರಡು ಬಾರಿ). ವಾಸ್ತವವಾಗಿ, ನೀವು ಹೆಚ್ಚುವರಿ ನೋಡ್‌ಗಳನ್ನು ಹೊಂದಿದ್ದೀರಿ, "ನಿರ್ಣಯ ನೋಡ್‌ಗಳು", ಅದು ನಿಮಗೆ ಸರಿಯಾದ ನೋಡ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಹಾಯ ಮಾಡುತ್ತದೆ (ಇದು ಸಂಬಂಧಿತ ಕೋಷ್ಟಕದಲ್ಲಿ ಸಾಲುಗಳ ಸ್ಥಳವನ್ನು ಸಂಗ್ರಹಿಸುತ್ತದೆ). ಆದರೆ ಹುಡುಕಾಟದ ಸಂಕೀರ್ಣತೆಯು ಇನ್ನೂ O(log(N)) ಆಗಿದೆ (ಇನ್ನೂ ಒಂದು ಹಂತ ಮಾತ್ರ ಇದೆ). ದೊಡ್ಡ ವ್ಯತ್ಯಾಸವೆಂದರೆ ಅದು ಕೆಳಗಿನ ಹಂತದಲ್ಲಿ ನೋಡ್‌ಗಳು ತಮ್ಮ ಉತ್ತರಾಧಿಕಾರಿಗಳೊಂದಿಗೆ ಸಂಪರ್ಕ ಹೊಂದಿವೆ.

ಈ ಬಿ+ಟ್ರೀಯೊಂದಿಗೆ, ನೀವು 40 ಮತ್ತು 100 ರ ನಡುವಿನ ಮೌಲ್ಯಗಳನ್ನು ಹುಡುಕುತ್ತಿದ್ದರೆ:

ನೀವು ಹಿಂದಿನ ಮರದೊಂದಿಗೆ ಮಾಡಿದಂತೆ ನೀವು 40 (ಅಥವಾ 40 ಅಸ್ತಿತ್ವದಲ್ಲಿಲ್ಲದಿದ್ದರೆ 40 ರ ನಂತರದ ಹತ್ತಿರದ ಮೌಲ್ಯ) ಗಾಗಿ ನೋಡಬೇಕಾಗಿದೆ.
ನಂತರ ನೀವು 40 ತಲುಪುವವರೆಗೆ ನೇರ ಉತ್ತರಾಧಿಕಾರಿ ಲಿಂಕ್‌ಗಳನ್ನು ಬಳಸಿಕೊಂಡು 100 ಉತ್ತರಾಧಿಕಾರಿಗಳನ್ನು ಸಂಗ್ರಹಿಸಿ.

ನೀವು M ಉತ್ತರಾಧಿಕಾರಿಗಳನ್ನು ಕಂಡುಕೊಂಡಿದ್ದೀರಿ ಮತ್ತು ಮರವು N ನೋಡ್‌ಗಳನ್ನು ಹೊಂದಿದೆ ಎಂದು ಹೇಳೋಣ. ನಿರ್ದಿಷ್ಟ ನೋಡ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಹಿಂದಿನ ಮರದಂತೆಯೇ ಲಾಗ್ (N) ವೆಚ್ಚವಾಗುತ್ತದೆ. ಆದರೆ ಒಮ್ಮೆ ನೀವು ಈ ನೋಡ್ ಅನ್ನು ಪಡೆದರೆ, ನೀವು M ಕಾರ್ಯಾಚರಣೆಗಳಲ್ಲಿ M ಉತ್ತರಾಧಿಕಾರಿಗಳನ್ನು ಅವರ ಉತ್ತರಾಧಿಕಾರಿಗಳ ಉಲ್ಲೇಖಗಳೊಂದಿಗೆ ಪಡೆಯುತ್ತೀರಿ. ಈ ಹುಡುಕಾಟಕ್ಕೆ M+log(N) ಮಾತ್ರ ವೆಚ್ಚವಾಗುತ್ತದೆ ಹಿಂದಿನ ಮರದ ಮೇಲೆ N ಕಾರ್ಯಾಚರಣೆಗಳಿಗೆ ಹೋಲಿಸಿದರೆ ಕಾರ್ಯಾಚರಣೆಗಳು. ಇದಲ್ಲದೆ, ನೀವು ಪೂರ್ಣ ಟ್ರೀ ಅನ್ನು ಓದಬೇಕಾಗಿಲ್ಲ (ಕೇವಲ M+log(N) ನೋಡ್‌ಗಳು), ಅಂದರೆ ಕಡಿಮೆ ಡಿಸ್ಕ್ ಬಳಕೆ. M ಚಿಕ್ಕದಾಗಿದ್ದರೆ (ಉದಾ 200 ಸಾಲುಗಳು) ಮತ್ತು N ದೊಡ್ಡದಾಗಿದ್ದರೆ (1 ಸಾಲುಗಳು), ದೊಡ್ಡ ವ್ಯತ್ಯಾಸವಿರುತ್ತದೆ.

ಆದರೆ ಇಲ್ಲಿ ಹೊಸ ಸಮಸ್ಯೆಗಳಿವೆ (ಮತ್ತೆ!). ನೀವು ಡೇಟಾಬೇಸ್‌ನಲ್ಲಿ ಸಾಲನ್ನು ಸೇರಿಸಿದರೆ ಅಥವಾ ಅಳಿಸಿದರೆ (ಮತ್ತು ಆದ್ದರಿಂದ ಸಂಬಂಧಿತ ಬಿ+ಟ್ರೀ ಇಂಡೆಕ್ಸ್‌ನಲ್ಲಿ):

ನೀವು B+ಟ್ರೀ ಒಳಗೆ ನೋಡ್‌ಗಳ ನಡುವೆ ಕ್ರಮವನ್ನು ನಿರ್ವಹಿಸಬೇಕು, ಇಲ್ಲದಿದ್ದರೆ ನೀವು ವಿಂಗಡಿಸದ ಮರದೊಳಗೆ ನೋಡ್‌ಗಳನ್ನು ಹುಡುಕಲು ಸಾಧ್ಯವಾಗುವುದಿಲ್ಲ.
ನೀವು ಬಿ+ಟ್ರೀಯಲ್ಲಿ ಕನಿಷ್ಠ ಸಂಭವನೀಯ ಸಂಖ್ಯೆಯ ಹಂತಗಳನ್ನು ಇಟ್ಟುಕೊಳ್ಳಬೇಕು, ಇಲ್ಲದಿದ್ದರೆ O(ಲಾಗ್(N)) ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು O(N) ಆಗುತ್ತದೆ.

ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ಬಿ+ಟ್ರೀ ಸ್ವಯಂ-ಆದೇಶ ಮತ್ತು ಸಮತೋಲಿತವಾಗಿರಬೇಕು. ಅದೃಷ್ಟವಶಾತ್, ಸ್ಮಾರ್ಟ್ ಡಿಲೀಟ್ ಮತ್ತು ಇನ್ಸರ್ಟ್ ಕಾರ್ಯಾಚರಣೆಗಳೊಂದಿಗೆ ಇದು ಸಾಧ್ಯ. ಆದರೆ ಇದು ವೆಚ್ಚದಲ್ಲಿ ಬರುತ್ತದೆ: ಬಿ+ ಟ್ರೀಯಲ್ಲಿನ ಅಳವಡಿಕೆಗಳು ಮತ್ತು ಅಳಿಸುವಿಕೆಗಳ ಬೆಲೆ O(ಲಾಗ್(N)). ಅದಕ್ಕಾಗಿಯೇ ನಿಮ್ಮಲ್ಲಿ ಕೆಲವರು ಅದನ್ನು ಕೇಳಿದ್ದೀರಿ ಹಲವಾರು ಸೂಚ್ಯಂಕಗಳನ್ನು ಬಳಸುವುದು ಒಳ್ಳೆಯದಲ್ಲ. ನಿಜವಾಗಿಯೂ, ನೀವು ಟೇಬಲ್‌ನಲ್ಲಿ ಸಾಲನ್ನು ವೇಗವಾಗಿ ಸೇರಿಸುವುದನ್ನು/ಅಪ್‌ಡೇಟ್ ಮಾಡುವುದನ್ನು/ಅಳಿಸುವುದನ್ನು ನಿಧಾನಗೊಳಿಸುತ್ತಿರುವಿರಿಏಕೆಂದರೆ ಡೇಟಾಬೇಸ್ ಪ್ರತಿ ಸೂಚ್ಯಂಕಕ್ಕೆ ದುಬಾರಿ O(log(N)) ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಬಳಸಿಕೊಂಡು ಟೇಬಲ್‌ನ ಸೂಚಿಕೆಗಳನ್ನು ನವೀಕರಿಸಬೇಕಾಗುತ್ತದೆ. ಇದಲ್ಲದೆ, ಸೂಚ್ಯಂಕಗಳನ್ನು ಸೇರಿಸುವುದು ಎಂದರೆ ಹೆಚ್ಚಿನ ಕೆಲಸದ ಹೊರೆ ವಹಿವಾಟು ವ್ಯವಸ್ಥಾಪಕ (ಲೇಖನದ ಕೊನೆಯಲ್ಲಿ ವಿವರಿಸಲಾಗುವುದು).

ಹೆಚ್ಚಿನ ವಿವರಗಳಿಗಾಗಿ, ನೀವು ವಿಕಿಪೀಡಿಯ ಲೇಖನವನ್ನು ನೋಡಬಹುದು B+ಮರ. ಡೇಟಾಬೇಸ್‌ನಲ್ಲಿ ಬಿ+ಟ್ರೀ ಅಳವಡಿಸುವ ಉದಾಹರಣೆ ನಿಮಗೆ ಬೇಕಾದರೆ, ಒಮ್ಮೆ ನೋಡಿ ಈ ಲೇಖನ и ಈ ಲೇಖನ ಪ್ರಮುಖ MySQL ಡೆವಲಪರ್‌ನಿಂದ. InnoDB (MySQL ಎಂಜಿನ್) ಸೂಚ್ಯಂಕಗಳನ್ನು ಹೇಗೆ ನಿರ್ವಹಿಸುತ್ತದೆ ಎಂಬುದರ ಮೇಲೆ ಇಬ್ಬರೂ ಗಮನಹರಿಸುತ್ತಾರೆ.

ಗಮನಿಸಿ: ಕಡಿಮೆ ಮಟ್ಟದ ಆಪ್ಟಿಮೈಸೇಶನ್‌ಗಳಿಂದಾಗಿ, B+ ಟ್ರೀ ಸಂಪೂರ್ಣವಾಗಿ ಸಮತೋಲನದಲ್ಲಿರಬೇಕು ಎಂದು ಓದುಗರೊಬ್ಬರು ನನಗೆ ಹೇಳಿದರು.

ಹ್ಯಾಶ್ಟೇಬಲ್

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

ಹ್ಯಾಶ್ ಟೇಬಲ್ ಎನ್ನುವುದು ಡೇಟಾ ರಚನೆಯಾಗಿದ್ದು ಅದು ಅದರ ಕೀಲಿಯಿಂದ ಅಂಶವನ್ನು ತ್ವರಿತವಾಗಿ ಕಂಡುಹಿಡಿಯುತ್ತದೆ. ಹ್ಯಾಶ್ ಟೇಬಲ್ ಅನ್ನು ನಿರ್ಮಿಸಲು ನೀವು ವ್ಯಾಖ್ಯಾನಿಸಬೇಕಾಗಿದೆ:

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

ಸರಳ ಉದಾಹರಣೆ

ಸ್ಪಷ್ಟ ಉದಾಹರಣೆಯನ್ನು ತೆಗೆದುಕೊಳ್ಳೋಣ:

ಈ ಹ್ಯಾಶ್ ಟೇಬಲ್ 10 ವಿಭಾಗಗಳನ್ನು ಹೊಂದಿದೆ. ನಾನು ಸೋಮಾರಿಯಾದ ಕಾರಣ, ನಾನು ಕೇವಲ 5 ವಿಭಾಗಗಳನ್ನು ಮಾತ್ರ ಚಿತ್ರಿಸಿದ್ದೇನೆ, ಆದರೆ ನೀವು ಬುದ್ಧಿವಂತರು ಎಂದು ನನಗೆ ತಿಳಿದಿದೆ, ಹಾಗಾಗಿ ಉಳಿದ 5 ಅನ್ನು ನೀವೇ ಚಿತ್ರಿಸಲು ನಾನು ನಿಮಗೆ ಅವಕಾಶ ನೀಡುತ್ತೇನೆ. ನಾನು ಹ್ಯಾಶ್ ಫಂಕ್ಷನ್ ಮಾಡ್ಯುಲೋ 10 ಕೀಯನ್ನು ಬಳಸಿದ್ದೇನೆ. ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ಅದರ ವಿಭಾಗವನ್ನು ಕಂಡುಹಿಡಿಯಲು ನಾನು ಅಂಶದ ಕೀಲಿಯ ಕೊನೆಯ ಅಂಕಿಯನ್ನು ಮಾತ್ರ ಸಂಗ್ರಹಿಸುತ್ತೇನೆ:

ಕೊನೆಯ ಅಂಕಿಯು 0 ಆಗಿದ್ದರೆ, ಅಂಶವು ವಿಭಾಗ 0 ಗೆ ಬರುತ್ತದೆ,
ಕೊನೆಯ ಅಂಕಿಯು 1 ಆಗಿದ್ದರೆ, ಅಂಶವು ವಿಭಾಗ 1 ಗೆ ಬರುತ್ತದೆ,
ಕೊನೆಯ ಅಂಕಿಯು 2 ಆಗಿದ್ದರೆ, ಅಂಶವು ಪ್ರದೇಶ 2 ಕ್ಕೆ ಬರುತ್ತದೆ,
...

ನಾನು ಬಳಸಿದ ಹೋಲಿಕೆ ಕಾರ್ಯವು ಎರಡು ಪೂರ್ಣಾಂಕಗಳ ನಡುವಿನ ಸಮಾನತೆಯಾಗಿದೆ.

ನೀವು ಅಂಶ 78 ಅನ್ನು ಪಡೆಯಲು ಬಯಸುತ್ತೀರಿ ಎಂದು ಹೇಳೋಣ:

ಹ್ಯಾಶ್ ಟೇಬಲ್ 78 ಗಾಗಿ ಹ್ಯಾಶ್ ಕೋಡ್ ಅನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುತ್ತದೆ, ಅದು 8 ಆಗಿದೆ.
ಹ್ಯಾಶ್ ಟೇಬಲ್ ಸೆಗ್ಮೆಂಟ್ 8 ಅನ್ನು ನೋಡುತ್ತದೆ ಮತ್ತು ಅದು ಕಂಡುಕೊಳ್ಳುವ ಮೊದಲ ಅಂಶ 78 ಆಗಿದೆ.
ಅವಳು ನಿಮಗೆ ಐಟಂ 78 ಅನ್ನು ಹಿಂತಿರುಗಿಸುತ್ತಾಳೆ
ಹುಡುಕಾಟದ ವೆಚ್ಚ ಕೇವಲ 2 ಕಾರ್ಯಾಚರಣೆಗಳು (ಒಂದು ಹ್ಯಾಶ್ ಮೌಲ್ಯವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಮತ್ತು ಇನ್ನೊಂದು ವಿಭಾಗದೊಳಗಿನ ಅಂಶವನ್ನು ನೋಡಲು).

ಈಗ ನೀವು ಅಂಶ 59 ಅನ್ನು ಪಡೆಯಲು ಬಯಸುತ್ತೀರಿ ಎಂದು ಹೇಳೋಣ:

ಹ್ಯಾಶ್ ಟೇಬಲ್ 59 ಗಾಗಿ ಹ್ಯಾಶ್ ಕೋಡ್ ಅನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುತ್ತದೆ, ಅದು 9 ಆಗಿದೆ.
ಹ್ಯಾಶ್ ಟೇಬಲ್ ವಿಭಾಗ 9 ರಲ್ಲಿ ಹುಡುಕುತ್ತದೆ, ಮೊದಲ ಅಂಶವು 99 ಆಗಿದೆ. 99!=59 ರಿಂದ, ಅಂಶ 99 ಮಾನ್ಯವಾದ ಅಂಶವಲ್ಲ.
ಅದೇ ತರ್ಕವನ್ನು ಬಳಸಿ, ಎರಡನೇ ಅಂಶ (9), ಮೂರನೇ (79), ..., ಕೊನೆಯ (29) ಅನ್ನು ತೆಗೆದುಕೊಳ್ಳಲಾಗುತ್ತದೆ.
ಅಂಶ ಕಂಡುಬಂದಿಲ್ಲ.
ಹುಡುಕಾಟದ ವೆಚ್ಚ 7 ಕಾರ್ಯಾಚರಣೆಗಳು.

ಉತ್ತಮ ಹ್ಯಾಶ್ ಕಾರ್ಯ

ನೀವು ನೋಡುವಂತೆ, ನೀವು ಹುಡುಕುತ್ತಿರುವ ಮೌಲ್ಯವನ್ನು ಅವಲಂಬಿಸಿ, ವೆಚ್ಚವು ಒಂದೇ ಆಗಿರುವುದಿಲ್ಲ!

ನಾನು ಈಗ ಹ್ಯಾಶ್ ಫಂಕ್ಷನ್ ಮಾಡ್ಯುಲೋ 1 ಕೀಲಿಯನ್ನು ಬದಲಾಯಿಸಿದರೆ (ಅಂದರೆ, ಕೊನೆಯ 000 ಅಂಕೆಗಳನ್ನು ತೆಗೆದುಕೊಂಡರೆ), ಸೆಗ್ಮೆಂಟ್ 000 ರಲ್ಲಿ ಯಾವುದೇ ಅಂಶಗಳಿಲ್ಲದ ಕಾರಣ ಎರಡನೇ ಲುಕಪ್ ಕೇವಲ 6 ಕಾರ್ಯಾಚರಣೆಗೆ ವೆಚ್ಚವಾಗುತ್ತದೆ. ಕಡಿಮೆ ಸಂಖ್ಯೆಯ ಅಂಶಗಳನ್ನು ಹೊಂದಿರುವ ಬಕೆಟ್‌ಗಳನ್ನು ರಚಿಸುವ ಉತ್ತಮ ಹ್ಯಾಶ್ ಕಾರ್ಯವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ನಿಜವಾದ ಸವಾಲು.

ನನ್ನ ಉದಾಹರಣೆಯಲ್ಲಿ, ಉತ್ತಮ ಹ್ಯಾಶ್ ಕಾರ್ಯವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಸುಲಭ. ಆದರೆ ಇದು ಸರಳ ಉದಾಹರಣೆಯಾಗಿದೆ, ಕೀಲಿಯಾಗಿರುವಾಗ ಉತ್ತಮ ಹ್ಯಾಶ್ ಕಾರ್ಯವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಹೆಚ್ಚು ಕಷ್ಟ:

ಸ್ಟ್ರಿಂಗ್ (ಉದಾಹರಣೆಗೆ - ಕೊನೆಯ ಹೆಸರು)
2 ಸಾಲುಗಳು (ಉದಾಹರಣೆಗೆ - ಕೊನೆಯ ಹೆಸರು ಮತ್ತು ಮೊದಲ ಹೆಸರು)
2 ಸಾಲುಗಳು ಮತ್ತು ದಿನಾಂಕ (ಉದಾಹರಣೆಗೆ - ಕೊನೆಯ ಹೆಸರು, ಮೊದಲ ಹೆಸರು ಮತ್ತು ಹುಟ್ಟಿದ ದಿನಾಂಕ)
...

ಉತ್ತಮ ಹ್ಯಾಶ್ ಕಾರ್ಯದೊಂದಿಗೆ, ಹ್ಯಾಶ್ ಟೇಬಲ್ ಲುಕಪ್‌ಗಳ ಬೆಲೆ O(1).

ಅರೇ vs ಹ್ಯಾಶ್ ಟೇಬಲ್

ಒಂದು ಶ್ರೇಣಿಯನ್ನು ಏಕೆ ಬಳಸಬಾರದು?

ಹಾಂ, ಒಳ್ಳೆಯ ಪ್ರಶ್ನೆ.

ಹ್ಯಾಶ್ ಟೇಬಲ್ ಆಗಿರಬಹುದು ಮೆಮೊರಿಗೆ ಭಾಗಶಃ ಲೋಡ್ ಮಾಡಲಾಗಿದೆ, ಮತ್ತು ಉಳಿದ ವಿಭಾಗಗಳು ಡಿಸ್ಕ್ನಲ್ಲಿ ಉಳಿಯಬಹುದು.
ರಚನೆಯೊಂದಿಗೆ ನೀವು ಮೆಮೊರಿಯಲ್ಲಿ ಪಕ್ಕದ ಜಾಗವನ್ನು ಬಳಸಬೇಕು. ನೀವು ದೊಡ್ಡ ಟೇಬಲ್ ಅನ್ನು ಲೋಡ್ ಮಾಡುತ್ತಿದ್ದರೆ ಸಾಕಷ್ಟು ನಿರಂತರ ಜಾಗವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ತುಂಬಾ ಕಷ್ಟ.
ಹ್ಯಾಶ್ ಟೇಬಲ್‌ಗಾಗಿ, ನಿಮಗೆ ಬೇಕಾದ ಕೀಲಿಯನ್ನು ನೀವು ಆಯ್ಕೆ ಮಾಡಬಹುದು (ಉದಾಹರಣೆಗೆ, ದೇಶ ಮತ್ತು ವ್ಯಕ್ತಿಯ ಕೊನೆಯ ಹೆಸರು).

ಹೆಚ್ಚಿನ ಮಾಹಿತಿಗಾಗಿ, ನೀವು ಬಗ್ಗೆ ಲೇಖನವನ್ನು ಓದಬಹುದು ಜಾವಾಹ್ಯಾಶ್‌ಮ್ಯಾಪ್, ಇದು ಹ್ಯಾಶ್ ಟೇಬಲ್‌ನ ಸಮರ್ಥ ಅನುಷ್ಠಾನವಾಗಿದೆ; ಈ ಲೇಖನದಲ್ಲಿ ಒಳಗೊಂಡಿರುವ ಪರಿಕಲ್ಪನೆಗಳನ್ನು ಅರ್ಥಮಾಡಿಕೊಳ್ಳಲು ನೀವು ಜಾವಾವನ್ನು ಅರ್ಥಮಾಡಿಕೊಳ್ಳುವ ಅಗತ್ಯವಿಲ್ಲ.

ಮೂಲ: www.habr.com

ಸಂಬಂಧಿತ ಡೇಟಾಬೇಸ್‌ಗಳು ಹೇಗೆ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತವೆ (ಭಾಗ 1)