ਹੇ ਹਬਰ! ਮੈਂ ਲੇਖ ਦਾ ਅਨੁਵਾਦ ਤੁਹਾਡੇ ਧਿਆਨ ਵਿੱਚ ਪੇਸ਼ ਕਰਦਾ ਹਾਂ
"ਰਿਲੇਸ਼ਨਲ ਡੇਟਾਬੇਸ ਕਿਵੇਂ ਕੰਮ ਕਰਦਾ ਹੈ".

ਜਦੋਂ ਰਿਲੇਸ਼ਨਲ ਡੇਟਾਬੇਸ ਦੀ ਗੱਲ ਆਉਂਦੀ ਹੈ ਤਾਂ ਮੈਂ ਮਦਦ ਨਹੀਂ ਕਰ ਸਕਦਾ ਪਰ ਸੋਚਦਾ ਹਾਂ ਕਿ ਕੁਝ ਗੁੰਮ ਹੈ। ਉਹ ਹਰ ਜਗ੍ਹਾ ਵਰਤੇ ਜਾਂਦੇ ਹਨ. ਛੋਟੇ ਅਤੇ ਉਪਯੋਗੀ SQLite ਤੋਂ ਲੈ ਕੇ ਸ਼ਕਤੀਸ਼ਾਲੀ ਟੈਰਾਡੇਟਾ ਤੱਕ ਬਹੁਤ ਸਾਰੇ ਵੱਖ-ਵੱਖ ਡੇਟਾਬੇਸ ਉਪਲਬਧ ਹਨ। ਪਰ ਇੱਥੇ ਕੁਝ ਹੀ ਲੇਖ ਹਨ ਜੋ ਦੱਸਦੇ ਹਨ ਕਿ ਡੇਟਾਬੇਸ ਕਿਵੇਂ ਕੰਮ ਕਰਦਾ ਹੈ। ਤੁਸੀਂ ਇਹ ਦੇਖਣ ਲਈ "howdoesarelationaldatabasework" ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਆਪਣੇ ਲਈ ਖੋਜ ਕਰ ਸਕਦੇ ਹੋ ਕਿ ਨਤੀਜੇ ਕਿੰਨੇ ਘੱਟ ਹਨ। ਇਸ ਤੋਂ ਇਲਾਵਾ, ਇਹ ਲੇਖ ਛੋਟੇ ਹਨ। ਜੇ ਤੁਸੀਂ ਨਵੀਨਤਮ ਬਜ਼ੀ ਤਕਨਾਲੋਜੀਆਂ (ਬਿਗਡਾਟਾ, NoSQL ਜਾਂ JavaScript) ਦੀ ਭਾਲ ਕਰ ਰਹੇ ਹੋ, ਤਾਂ ਤੁਹਾਨੂੰ ਇਹ ਦੱਸਣ ਵਾਲੇ ਹੋਰ ਡੂੰਘਾਈ ਵਾਲੇ ਲੇਖ ਮਿਲਣਗੇ ਕਿ ਉਹ ਕਿਵੇਂ ਕੰਮ ਕਰਦੇ ਹਨ।

ਕੀ ਰਿਲੇਸ਼ਨਲ ਡੇਟਾਬੇਸ ਬਹੁਤ ਪੁਰਾਣੇ ਅਤੇ ਬਹੁਤ ਬੋਰਿੰਗ ਹਨ ਜੋ ਯੂਨੀਵਰਸਿਟੀ ਦੇ ਕੋਰਸਾਂ, ਖੋਜ ਪੱਤਰਾਂ ਅਤੇ ਕਿਤਾਬਾਂ ਤੋਂ ਬਾਹਰ ਸਮਝਾਉਣ ਲਈ ਹਨ?

ਇੱਕ ਡਿਵੈਲਪਰ ਵਜੋਂ, ਮੈਨੂੰ ਅਜਿਹੀ ਕੋਈ ਚੀਜ਼ ਵਰਤਣ ਤੋਂ ਨਫ਼ਰਤ ਹੈ ਜੋ ਮੈਂ ਨਹੀਂ ਸਮਝਦਾ। ਅਤੇ ਜੇਕਰ ਡੇਟਾਬੇਸ 40 ਸਾਲਾਂ ਤੋਂ ਵੱਧ ਸਮੇਂ ਲਈ ਵਰਤੇ ਗਏ ਹਨ, ਤਾਂ ਇੱਕ ਕਾਰਨ ਹੋਣਾ ਚਾਹੀਦਾ ਹੈ. ਸਾਲਾਂ ਦੌਰਾਨ, ਮੈਂ ਇਹਨਾਂ ਅਜੀਬ ਬਲੈਕ ਬਾਕਸਾਂ ਨੂੰ ਸੱਚਮੁੱਚ ਸਮਝਣ ਲਈ ਸੈਂਕੜੇ ਘੰਟੇ ਬਿਤਾਏ ਹਨ ਜੋ ਮੈਂ ਹਰ ਰੋਜ਼ ਵਰਤਦਾ ਹਾਂ। ਰਿਲੇਸ਼ਨਲ ਡਾਟਾਬੇਸ ਬਹੁਤ ਦਿਲਚਸਪ ਕਿਉਂਕਿ ਉਹ ਉਪਯੋਗੀ ਅਤੇ ਮੁੜ ਵਰਤੋਂ ਯੋਗ ਸੰਕਲਪਾਂ 'ਤੇ ਅਧਾਰਤ. ਜੇ ਤੁਸੀਂ ਇੱਕ ਡੇਟਾਬੇਸ ਨੂੰ ਸਮਝਣ ਵਿੱਚ ਦਿਲਚਸਪੀ ਰੱਖਦੇ ਹੋ, ਪਰ ਇਸ ਵਿਆਪਕ ਵਿਸ਼ੇ ਵਿੱਚ ਜਾਣ ਲਈ ਤੁਹਾਡੇ ਕੋਲ ਕਦੇ ਸਮਾਂ ਜਾਂ ਝੁਕਾਅ ਨਹੀਂ ਹੈ, ਤਾਂ ਤੁਹਾਨੂੰ ਇਸ ਲੇਖ ਦਾ ਆਨੰਦ ਲੈਣਾ ਚਾਹੀਦਾ ਹੈ।

ਹਾਲਾਂਕਿ ਇਸ ਲੇਖ ਦਾ ਸਿਰਲੇਖ ਸਪਸ਼ਟ ਹੈ, ਇਸ ਲੇਖ ਦਾ ਉਦੇਸ਼ ਇਹ ਸਮਝਣਾ ਨਹੀਂ ਹੈ ਕਿ ਡੇਟਾਬੇਸ ਦੀ ਵਰਤੋਂ ਕਿਵੇਂ ਕਰੀਏ. ਇਸ ਲਈ, ਤੁਹਾਨੂੰ ਪਹਿਲਾਂ ਹੀ ਪਤਾ ਹੋਣਾ ਚਾਹੀਦਾ ਹੈ ਕਿ ਇੱਕ ਸਧਾਰਨ ਕੁਨੈਕਸ਼ਨ ਬੇਨਤੀ ਅਤੇ ਬੁਨਿਆਦੀ ਸਵਾਲ ਕਿਵੇਂ ਲਿਖਣੇ ਹਨ ਰਾਅ; ਨਹੀਂ ਤਾਂ ਤੁਸੀਂ ਇਸ ਲੇਖ ਨੂੰ ਸਮਝ ਨਹੀਂ ਸਕਦੇ ਹੋ। ਤੁਹਾਨੂੰ ਸਿਰਫ ਇਹੀ ਜਾਣਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ, ਮੈਂ ਬਾਕੀ ਦੀ ਵਿਆਖਿਆ ਕਰਾਂਗਾ.

ਮੈਂ ਕੁਝ ਕੰਪਿਊਟਰ ਵਿਗਿਆਨ ਦੀਆਂ ਮੂਲ ਗੱਲਾਂ ਨਾਲ ਸ਼ੁਰੂ ਕਰਾਂਗਾ, ਜਿਵੇਂ ਕਿ ਐਲਗੋਰਿਦਮ ਦੀ ਸਮਾਂ ਗੁੰਝਲਤਾ (BigO)। ਮੈਂ ਜਾਣਦਾ ਹਾਂ ਕਿ ਤੁਹਾਡੇ ਵਿੱਚੋਂ ਕੁਝ ਇਸ ਸੰਕਲਪ ਨੂੰ ਨਫ਼ਰਤ ਕਰਦੇ ਹਨ, ਪਰ ਇਸਦੇ ਬਿਨਾਂ ਤੁਸੀਂ ਡੇਟਾਬੇਸ ਦੇ ਅੰਦਰ ਦੀਆਂ ਪੇਚੀਦਗੀਆਂ ਨੂੰ ਸਮਝਣ ਦੇ ਯੋਗ ਨਹੀਂ ਹੋਵੋਗੇ। ਕਿਉਂਕਿ ਇਹ ਇੱਕ ਬਹੁਤ ਵੱਡਾ ਵਿਸ਼ਾ ਹੈ, ਮੈਂ 'ਤੇ ਧਿਆਨ ਕੇਂਦਰਤ ਕਰਾਂਗਾ ਜੋ ਮੈਂ ਸੋਚਦਾ ਹਾਂ ਉਹ ਮਹੱਤਵਪੂਰਨ ਹੈ: ਡੇਟਾਬੇਸ ਦੀ ਪ੍ਰਕਿਰਿਆ ਕਿਵੇਂ ਹੁੰਦੀ ਹੈ SQL ਪੁੱਛਗਿੱਛ. ਮੈਂ ਹੁਣੇ ਜਾਣ-ਪਛਾਣ ਕਰਾਂਗਾ ਬੁਨਿਆਦੀ ਡਾਟਾਬੇਸ ਸੰਕਲਪਤਾਂ ਜੋ ਲੇਖ ਦੇ ਅੰਤ ਵਿੱਚ ਤੁਹਾਨੂੰ ਇੱਕ ਵਿਚਾਰ ਹੋਵੇ ਕਿ ਹੁੱਡ ਦੇ ਹੇਠਾਂ ਕੀ ਹੋ ਰਿਹਾ ਹੈ.

ਕਿਉਂਕਿ ਇਹ ਇੱਕ ਲੰਮਾ ਅਤੇ ਤਕਨੀਕੀ ਲੇਖ ਹੈ ਜਿਸ ਵਿੱਚ ਬਹੁਤ ਸਾਰੇ ਐਲਗੋਰਿਦਮ ਅਤੇ ਡੇਟਾ ਢਾਂਚੇ ਸ਼ਾਮਲ ਹਨ, ਇਸ ਨੂੰ ਪੜ੍ਹਨ ਲਈ ਆਪਣਾ ਸਮਾਂ ਲਓ। ਕੁਝ ਧਾਰਨਾਵਾਂ ਨੂੰ ਸਮਝਣਾ ਮੁਸ਼ਕਲ ਹੋ ਸਕਦਾ ਹੈ; ਤੁਸੀਂ ਉਹਨਾਂ ਨੂੰ ਛੱਡ ਸਕਦੇ ਹੋ ਅਤੇ ਫਿਰ ਵੀ ਆਮ ਵਿਚਾਰ ਪ੍ਰਾਪਤ ਕਰ ਸਕਦੇ ਹੋ।

ਤੁਹਾਡੇ ਵਿੱਚੋਂ ਵਧੇਰੇ ਜਾਣਕਾਰ ਲਈ, ਇਸ ਲੇਖ ਨੂੰ 3 ਭਾਗਾਂ ਵਿੱਚ ਵੰਡਿਆ ਗਿਆ ਹੈ:

• ਹੇਠਲੇ-ਪੱਧਰ ਅਤੇ ਉੱਚ-ਪੱਧਰੀ ਡਾਟਾਬੇਸ ਭਾਗਾਂ ਦੀ ਸੰਖੇਪ ਜਾਣਕਾਰੀ
• ਪੁੱਛਗਿੱਛ ਅਨੁਕੂਲਨ ਪ੍ਰਕਿਰਿਆ ਦੀ ਸੰਖੇਪ ਜਾਣਕਾਰੀ
• ਟ੍ਰਾਂਜੈਕਸ਼ਨ ਅਤੇ ਬਫਰ ਪੂਲ ਪ੍ਰਬੰਧਨ ਦੀ ਸੰਖੇਪ ਜਾਣਕਾਰੀ

ਮੂਲ ਗੱਲਾਂ 'ਤੇ ਵਾਪਸ ਜਾਓ

ਕਈ ਸਾਲ ਪਹਿਲਾਂ (ਇੱਕ ਗਲੈਕਸੀ ਵਿੱਚ, ਬਹੁਤ ਦੂਰ...), ਡਿਵੈਲਪਰਾਂ ਨੂੰ ਉਹਨਾਂ ਓਪਰੇਸ਼ਨਾਂ ਦੀ ਸੰਖਿਆ ਨੂੰ ਬਿਲਕੁਲ ਪਤਾ ਹੋਣਾ ਚਾਹੀਦਾ ਸੀ ਜੋ ਉਹ ਕੋਡਿੰਗ ਕਰ ਰਹੇ ਸਨ। ਉਹ ਆਪਣੇ ਐਲਗੋਰਿਦਮ ਅਤੇ ਡੇਟਾ ਢਾਂਚੇ ਨੂੰ ਦਿਲੋਂ ਜਾਣਦੇ ਸਨ ਕਿਉਂਕਿ ਉਹ ਆਪਣੇ ਹੌਲੀ ਕੰਪਿਊਟਰਾਂ ਦੀ CPU ਅਤੇ ਮੈਮੋਰੀ ਨੂੰ ਬਰਬਾਦ ਨਹੀਂ ਕਰ ਸਕਦੇ ਸਨ।

ਇਸ ਹਿੱਸੇ ਵਿੱਚ, ਮੈਂ ਤੁਹਾਨੂੰ ਇਹਨਾਂ ਵਿੱਚੋਂ ਕੁਝ ਸੰਕਲਪਾਂ ਦੀ ਯਾਦ ਦਿਵਾਵਾਂਗਾ ਕਿਉਂਕਿ ਉਹ ਡੇਟਾਬੇਸ ਨੂੰ ਸਮਝਣ ਲਈ ਜ਼ਰੂਰੀ ਹਨ। ਮੈਂ ਸੰਕਲਪ ਵੀ ਪੇਸ਼ ਕਰਾਂਗਾ ਡਾਟਾਬੇਸ ਸੂਚਕਾਂਕ.

O(1) ਬਨਾਮ O(n2)

ਅੱਜਕੱਲ੍ਹ, ਬਹੁਤ ਸਾਰੇ ਡਿਵੈਲਪਰ ਐਲਗੋਰਿਦਮ ਦੀ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਦੀ ਪਰਵਾਹ ਨਹੀਂ ਕਰਦੇ... ਅਤੇ ਉਹ ਸਹੀ ਹਨ!

ਪਰ ਜਦੋਂ ਤੁਸੀਂ ਬਹੁਤ ਸਾਰੇ ਡੇਟਾ ਨਾਲ ਕੰਮ ਕਰ ਰਹੇ ਹੋ (ਮੈਂ ਹਜ਼ਾਰਾਂ ਦੀ ਗੱਲ ਨਹੀਂ ਕਰ ਰਿਹਾ ਹਾਂ) ਜਾਂ ਜੇ ਤੁਸੀਂ ਮਿਲੀਸਕਿੰਟ ਵਿੱਚ ਸੰਘਰਸ਼ ਕਰ ਰਹੇ ਹੋ, ਤਾਂ ਇਸ ਧਾਰਨਾ ਨੂੰ ਸਮਝਣਾ ਮਹੱਤਵਪੂਰਨ ਹੋ ਜਾਂਦਾ ਹੈ। ਅਤੇ ਜਿਵੇਂ ਕਿ ਤੁਸੀਂ ਕਲਪਨਾ ਕਰ ਸਕਦੇ ਹੋ, ਡੇਟਾਬੇਸ ਨੂੰ ਦੋਵਾਂ ਸਥਿਤੀਆਂ ਨਾਲ ਨਜਿੱਠਣਾ ਪੈਂਦਾ ਹੈ! ਮੈਂ ਤੁਹਾਨੂੰ ਬਿੰਦੂ ਨੂੰ ਪਾਰ ਕਰਨ ਲਈ ਲੋੜ ਤੋਂ ਵੱਧ ਸਮਾਂ ਨਹੀਂ ਬਿਤਾਵਾਂਗਾ। ਇਹ ਬਾਅਦ ਵਿੱਚ ਲਾਗਤ-ਅਧਾਰਿਤ ਅਨੁਕੂਲਨ ਦੀ ਧਾਰਨਾ ਨੂੰ ਸਮਝਣ ਵਿੱਚ ਸਾਡੀ ਮਦਦ ਕਰੇਗਾ (ਕੀਮਤ ਅਧਾਰਿਤ ਅਨੁਕੂਲਤਾ).

ਸੰਕਲਪ

ਐਲਗੋਰਿਦਮ ਦੀ ਸਮਾਂ ਗੁੰਝਲਤਾ ਇਹ ਦੇਖਣ ਲਈ ਵਰਤਿਆ ਜਾਂਦਾ ਹੈ ਕਿ ਦਿੱਤੇ ਗਏ ਡੇਟਾ ਦੀ ਮਾਤਰਾ ਲਈ ਇੱਕ ਐਲਗੋਰਿਦਮ ਨੂੰ ਪੂਰਾ ਹੋਣ ਵਿੱਚ ਕਿੰਨਾ ਸਮਾਂ ਲੱਗੇਗਾ. ਇਸ ਗੁੰਝਲਤਾ ਦਾ ਵਰਣਨ ਕਰਨ ਲਈ, ਅਸੀਂ ਵੱਡੇ O ਗਣਿਤਿਕ ਸੰਕੇਤ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹਾਂ। ਇਹ ਸੰਕੇਤ ਇੱਕ ਫੰਕਸ਼ਨ ਦੇ ਨਾਲ ਵਰਤਿਆ ਜਾਂਦਾ ਹੈ ਜੋ ਦੱਸਦਾ ਹੈ ਕਿ ਇੱਕ ਦਿੱਤੇ ਗਏ ਇਨਪੁਟਸ ਲਈ ਇੱਕ ਐਲਗੋਰਿਦਮ ਨੂੰ ਕਿੰਨੇ ਓਪਰੇਸ਼ਨਾਂ ਦੀ ਲੋੜ ਹੁੰਦੀ ਹੈ।

ਉਦਾਹਰਨ ਲਈ, ਜਦੋਂ ਮੈਂ ਕਹਿੰਦਾ ਹਾਂ ਕਿ "ਇਸ ਐਲਗੋਰਿਦਮ ਵਿੱਚ O(some_function()) ਦੀ ਗੁੰਝਲਤਾ ਹੈ", ਤਾਂ ਇਸਦਾ ਮਤਲਬ ਹੈ ਕਿ ਐਲਗੋਰਿਦਮ ਨੂੰ ਡੇਟਾ ਦੀ ਇੱਕ ਨਿਸ਼ਚਿਤ ਮਾਤਰਾ ਦੀ ਪ੍ਰਕਿਰਿਆ ਕਰਨ ਲਈ 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: ਤੁਸੀਂ ਥੋੜ੍ਹੇ ਜਿਹੇ ਡੇਟਾ ਦੇ ਨਾਲ ਵੀ ਆਪਣੇ ਨਤੀਜੇ ਪ੍ਰਾਪਤ ਨਹੀਂ ਕਰੋਗੇ।
• nn: ਜੇਕਰ ਤੁਹਾਨੂੰ ਇਸ ਗੁੰਝਲਤਾ ਦਾ ਸਾਹਮਣਾ ਕਰਨਾ ਪੈਂਦਾ ਹੈ, ਤਾਂ ਤੁਹਾਨੂੰ ਆਪਣੇ ਆਪ ਤੋਂ ਪੁੱਛਣਾ ਚਾਹੀਦਾ ਹੈ ਕਿ ਕੀ ਇਹ ਅਸਲ ਵਿੱਚ ਤੁਹਾਡੀ ਗਤੀਵਿਧੀ ਦਾ ਖੇਤਰ ਹੈ...

ਨੋਟ: ਮੈਂ ਤੁਹਾਨੂੰ ਵੱਡੇ O ਅਹੁਦੇ ਦੀ ਅਸਲ ਪਰਿਭਾਸ਼ਾ ਨਹੀਂ ਦਿੱਤੀ, ਸਿਰਫ਼ ਇੱਕ ਵਿਚਾਰ। ਤੁਸੀਂ ਇਸ ਲੇਖ ਨੂੰ ਇੱਥੇ ਪੜ੍ਹ ਸਕਦੇ ਹੋ ਵਿਕੀਪੀਡੀਆ ਅਸਲੀ (ਅਸਿੰਪਟੋਟਿਕ) ਪਰਿਭਾਸ਼ਾ ਲਈ।

ਮਿਲਾਓ

ਜਦੋਂ ਤੁਹਾਨੂੰ ਸੰਗ੍ਰਹਿ ਨੂੰ ਕ੍ਰਮਬੱਧ ਕਰਨ ਦੀ ਲੋੜ ਹੁੰਦੀ ਹੈ ਤਾਂ ਤੁਸੀਂ ਕੀ ਕਰਦੇ ਹੋ? ਕੀ? ਤੁਸੀਂ sort() ਫੰਕਸ਼ਨ ਨੂੰ ਕਾਲ ਕਰੋ... ਠੀਕ ਹੈ, ਵਧੀਆ ਜਵਾਬ... ਪਰ ਇੱਕ ਡੇਟਾਬੇਸ ਲਈ, ਤੁਹਾਨੂੰ ਇਹ ਸਮਝਣਾ ਚਾਹੀਦਾ ਹੈ ਕਿ ਇਹ 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 ਪੜਾਵਾਂ ਵਿੱਚ ਯੂਨੀਟਰੀ ਐਰੇ ਵਿੱਚ ਵੰਡਿਆ ਜਾਂਦਾ ਹੈ। ਕਦਮਾਂ ਦੀ ਰਸਮੀ ਸੰਖਿਆ log(N) ਹੈ (ਕਿਉਂਕਿ N=8, log(N) = 3)।

ਮੈਨੂੰ ਇਹ ਕਿਵੇਂ ਪਤਾ ਹੈ?

ਮੈਂ ਪ੍ਰਤਿਭਾਵਾਨ ਹਾਂ! ਇੱਕ ਸ਼ਬਦ ਵਿੱਚ - ਗਣਿਤ. ਇਹ ਵਿਚਾਰ ਇਹ ਹੈ ਕਿ ਹਰੇਕ ਕਦਮ ਅਸਲ ਐਰੇ ਦੇ ਆਕਾਰ ਨੂੰ 2 ਨਾਲ ਵੰਡਦਾ ਹੈ। ਕਦਮਾਂ ਦੀ ਗਿਣਤੀ ਉਹ ਹੈ ਜਿੰਨੀ ਵਾਰ ਤੁਸੀਂ ਅਸਲ ਐਰੇ ਨੂੰ ਦੋ ਵਿੱਚ ਵੰਡ ਸਕਦੇ ਹੋ। ਇਹ ਇੱਕ ਲਘੂਗਣਕ (ਬੇਸ 2) ਦੀ ਸਹੀ ਪਰਿਭਾਸ਼ਾ ਹੈ।

ਛਾਂਟੀ ਦਾ ਪੜਾਅ

ਛਾਂਟੀ ਦੇ ਪੜਾਅ ਵਿੱਚ, ਤੁਸੀਂ ਇਕਸਾਰ (ਸਿੰਗਲ-ਐਲੀਮੈਂਟ) ਐਰੇ ਨਾਲ ਸ਼ੁਰੂ ਕਰਦੇ ਹੋ। ਹਰ ਪਗ ਦੇ ਦੌਰਾਨ ਤੁਸੀਂ ਮਲਟੀਪਲ ਮਰਜ ਓਪਰੇਸ਼ਨ ਲਾਗੂ ਕਰਦੇ ਹੋ ਅਤੇ ਕੁੱਲ ਲਾਗਤ N = 8 ਓਪਰੇਸ਼ਨ ਹੈ:

• ਪਹਿਲੇ ਪੜਾਅ ਵਿੱਚ ਤੁਹਾਡੇ ਕੋਲ 4 ਅਭੇਦ ਹਨ ਜਿਨ੍ਹਾਂ ਵਿੱਚ 2 ਓਪਰੇਸ਼ਨਾਂ ਦੀ ਲਾਗਤ ਹੁੰਦੀ ਹੈ
• ਦੂਜੇ ਪੜਾਅ ਵਿੱਚ ਤੁਹਾਡੇ ਕੋਲ 2 ਅਭੇਦ ਹਨ ਜਿਨ੍ਹਾਂ ਵਿੱਚ 4 ਓਪਰੇਸ਼ਨਾਂ ਦੀ ਲਾਗਤ ਹੁੰਦੀ ਹੈ
• ਤੀਜੇ ਪੜਾਅ ਵਿੱਚ ਤੁਹਾਡੇ ਕੋਲ 1 ਅਭੇਦ ਹੈ ਜਿਸਦੀ ਕੀਮਤ 8 ਓਪਰੇਸ਼ਨ ਹੈ

ਕਿਉਂਕਿ ਇੱਥੇ ਲੌਗ(ਐਨ) ਕਦਮ ਹਨ, ਕੁੱਲ ਲਾਗਤ ਐਨ * log(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 ਲਈ ਸਾਰਣੀ ਵਿੱਚ ਵੇਖਦਾ ਹਾਂ।
• ਕਤਾਰ ID ਨੂੰ ਜਾਣਨਾ ਮੈਨੂੰ ਇਹ ਜਾਣਨ ਦੀ ਇਜਾਜ਼ਤ ਦਿੰਦਾ ਹੈ ਕਿ ਸਾਰਣੀ ਵਿੱਚ ਡੇਟਾ ਕਿੱਥੇ ਹੈ, ਇਸ ਲਈ ਮੈਂ ਇਸਨੂੰ ਤੁਰੰਤ ਪ੍ਰਾਪਤ ਕਰ ਸਕਦਾ ਹਾਂ।

ਅੰਤ ਵਿੱਚ, ਦੋਵੇਂ ਖੋਜਾਂ ਮੈਨੂੰ ਦਰਖਤ ਦੇ ਅੰਦਰਲੇ ਪੱਧਰਾਂ ਦੀ ਗਿਣਤੀ ਦਾ ਖਰਚਾ ਦੇਵੇਗੀ. ਜੇਕਰ ਤੁਸੀਂ ਅਭੇਦ ਕ੍ਰਮ ਬਾਰੇ ਭਾਗ ਨੂੰ ਧਿਆਨ ਨਾਲ ਪੜ੍ਹਦੇ ਹੋ, ਤਾਂ ਤੁਹਾਨੂੰ ਇਹ ਦੇਖਣਾ ਚਾਹੀਦਾ ਹੈ ਕਿ ਲੌਗ(N) ਪੱਧਰ ਹਨ। ਇਹ ਪਤਾ ਚਲਦਾ ਹੈ, ਖੋਜ ਲਾਗਤ ਲਾਗ(N), ਭੈੜਾ ਨਹੀਂ!

ਆਉ ਆਪਣੀ ਸਮੱਸਿਆ ਵੱਲ ਮੁੜਦੇ ਹਾਂ

ਪਰ ਇਹ ਬਹੁਤ ਅਮੂਰਤ ਹੈ, ਇਸ ਲਈ ਆਓ ਆਪਣੀ ਸਮੱਸਿਆ 'ਤੇ ਵਾਪਸ ਚਲੀਏ। ਇੱਕ ਸਧਾਰਨ ਪੂਰਨ ਅੰਕ ਦੀ ਬਜਾਏ, ਇੱਕ ਸਤਰ ਦੀ ਕਲਪਨਾ ਕਰੋ ਜੋ ਪਿਛਲੀ ਸਾਰਣੀ ਵਿੱਚ ਕਿਸੇ ਦੇ ਦੇਸ਼ ਨੂੰ ਦਰਸਾਉਂਦੀ ਹੈ। ਮੰਨ ਲਓ ਕਿ ਤੁਹਾਡੇ ਕੋਲ ਇੱਕ ਰੁੱਖ ਹੈ ਜਿਸ ਵਿੱਚ ਸਾਰਣੀ ਦਾ "ਦੇਸ਼" ਖੇਤਰ (ਕਾਲਮ 3) ਹੈ:

• ਜੇਕਰ ਤੁਸੀਂ ਜਾਣਨਾ ਚਾਹੁੰਦੇ ਹੋ ਕਿ ਯੂਕੇ ਵਿੱਚ ਕੌਣ ਕੰਮ ਕਰਦਾ ਹੈ
• ਤੁਸੀਂ ਨੋਡ ਪ੍ਰਾਪਤ ਕਰਨ ਲਈ ਰੁੱਖ ਨੂੰ ਦੇਖਦੇ ਹੋ ਜੋ ਗ੍ਰੇਟ ਬ੍ਰਿਟੇਨ ਨੂੰ ਦਰਸਾਉਂਦਾ ਹੈ
• "UKnode" ਦੇ ਅੰਦਰ ਤੁਹਾਨੂੰ UK ਵਰਕਰ ਰਿਕਾਰਡਾਂ ਦੀ ਸਥਿਤੀ ਮਿਲੇਗੀ।

ਜੇਕਰ ਤੁਸੀਂ ਐਰੇ ਨੂੰ ਸਿੱਧਾ ਵਰਤਦੇ ਹੋ ਤਾਂ ਇਸ ਖੋਜ ਲਈ N ਓਪਰੇਸ਼ਨਾਂ ਦੀ ਬਜਾਏ ਲਾਗ(N) ਓਪਰੇਸ਼ਨਾਂ ਦੀ ਲਾਗਤ ਆਵੇਗੀ। ਜੋ ਤੁਸੀਂ ਹੁਣੇ ਪੇਸ਼ ਕੀਤਾ ਸੀ ਡਾਟਾਬੇਸ ਸੂਚਕਾਂਕ.

ਤੁਸੀਂ ਫੀਲਡ ਦੇ ਕਿਸੇ ਵੀ ਸਮੂਹ (ਸਟਰਿੰਗ, ਨੰਬਰ, 2 ਲਾਈਨਾਂ, ਨੰਬਰ ਅਤੇ ਸਤਰ, ਮਿਤੀ...) ਲਈ ਇੱਕ ਇੰਡੈਕਸ ਟ੍ਰੀ ਬਣਾ ਸਕਦੇ ਹੋ ਜਦੋਂ ਤੱਕ ਤੁਹਾਡੇ ਕੋਲ ਕੁੰਜੀਆਂ (ਜਿਵੇਂ ਫੀਲਡ ਸਮੂਹਾਂ) ਦੀ ਤੁਲਨਾ ਕਰਨ ਲਈ ਕੋਈ ਫੰਕਸ਼ਨ ਹੈ ਤਾਂ ਜੋ ਤੁਸੀਂ ਸੈੱਟ ਕਰ ਸਕੋ। ਕੁੰਜੀਆਂ ਵਿਚਕਾਰ ਆਰਡਰ ਕਰੋ (ਜੋ ਕਿ ਡੇਟਾਬੇਸ ਵਿੱਚ ਕਿਸੇ ਵੀ ਬੁਨਿਆਦੀ ਕਿਸਮ ਲਈ ਕੇਸ ਹੈ)।

B+TreeIndex

ਹਾਲਾਂਕਿ ਇਹ ਰੁੱਖ ਇੱਕ ਖਾਸ ਮੁੱਲ ਪ੍ਰਾਪਤ ਕਰਨ ਲਈ ਵਧੀਆ ਕੰਮ ਕਰਦਾ ਹੈ, ਜਦੋਂ ਤੁਹਾਨੂੰ ਲੋੜ ਹੁੰਦੀ ਹੈ ਤਾਂ ਇੱਕ ਵੱਡੀ ਸਮੱਸਿਆ ਹੁੰਦੀ ਹੈ ਦੋ ਮੁੱਲਾਂ ਵਿਚਕਾਰ ਕਈ ਤੱਤ ਪ੍ਰਾਪਤ ਕਰੋ. ਇਸਦੀ ਕੀਮਤ O(N) ਹੋਵੇਗੀ ਕਿਉਂਕਿ ਤੁਹਾਨੂੰ ਟ੍ਰੀ ਵਿੱਚ ਹਰੇਕ ਨੋਡ ਨੂੰ ਦੇਖਣਾ ਹੋਵੇਗਾ ਅਤੇ ਜਾਂਚ ਕਰਨੀ ਪਵੇਗੀ ਕਿ ਕੀ ਇਹ ਇਹਨਾਂ ਦੋ ਮੁੱਲਾਂ ਦੇ ਵਿਚਕਾਰ ਹੈ (ਜਿਵੇਂ ਕਿ ਰੁੱਖ ਦੇ ਆਰਡਰਡ ਟ੍ਰਾਵਰਸਲ ਨਾਲ)। ਇਸ ਤੋਂ ਇਲਾਵਾ, ਇਹ ਓਪਰੇਸ਼ਨ ਡਿਸਕ I/O ਅਨੁਕੂਲ ਨਹੀਂ ਹੈ ਕਿਉਂਕਿ ਤੁਹਾਨੂੰ ਪੂਰਾ ਟ੍ਰੀ ਪੜ੍ਹਨਾ ਪੈਂਦਾ ਹੈ। ਸਾਨੂੰ ਕੁਸ਼ਲਤਾ ਨਾਲ ਚਲਾਉਣ ਦਾ ਤਰੀਕਾ ਲੱਭਣ ਦੀ ਲੋੜ ਹੈ ਸੀਮਾ ਦੀ ਬੇਨਤੀ. ਇਸ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ, ਆਧੁਨਿਕ ਡੇਟਾਬੇਸ ਬੀ + ਟ੍ਰੀ ਨਾਮਕ ਪਿਛਲੇ ਟ੍ਰੀ ਦੇ ਇੱਕ ਸੋਧੇ ਹੋਏ ਸੰਸਕਰਣ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹਨ। ਇੱਕ B+ ਰੁੱਖ ਦੇ ਰੁੱਖ ਵਿੱਚ:

• ਸਿਰਫ਼ ਸਭ ਤੋਂ ਹੇਠਲੇ ਨੋਡਸ (ਪੱਤੇ) ਸਟੋਰ ਜਾਣਕਾਰੀ (ਸਬੰਧਤ ਸਾਰਣੀ ਵਿੱਚ ਕਤਾਰਾਂ ਦੀ ਸਥਿਤੀ)
• ਬਾਕੀ ਨੋਡ ਇੱਥੇ ਹਨ ਰੂਟਿੰਗ ਲਈ ਸਹੀ ਨੋਡ ਨੂੰ ਖੋਜ ਦੌਰਾਨ.

ਜਿਵੇਂ ਕਿ ਤੁਸੀਂ ਦੇਖ ਸਕਦੇ ਹੋ, ਇੱਥੇ ਹੋਰ ਨੋਡ ਹਨ (ਦੋ ਵਾਰ). ਦਰਅਸਲ, ਤੁਹਾਡੇ ਕੋਲ ਵਾਧੂ ਨੋਡ ਹਨ, "ਫੈਸਲਾ ਨੋਡ", ਜੋ ਤੁਹਾਨੂੰ ਸਹੀ ਨੋਡ ਲੱਭਣ ਵਿੱਚ ਮਦਦ ਕਰੇਗਾ (ਜੋ ਸੰਬੰਧਿਤ ਸਾਰਣੀ ਵਿੱਚ ਕਤਾਰਾਂ ਦੀ ਸਥਿਤੀ ਨੂੰ ਸਟੋਰ ਕਰਦਾ ਹੈ)। ਪਰ ਖੋਜ ਦੀ ਗੁੰਝਲਤਾ ਅਜੇ ਵੀ O(log(N)) ਹੈ (ਸਿਰਫ਼ ਇੱਕ ਹੋਰ ਪੱਧਰ ਹੈ)। ਵੱਡਾ ਫਰਕ ਇਹ ਹੈ ਕਿ ਹੇਠਲੇ ਪੱਧਰ 'ਤੇ ਨੋਡ ਉਨ੍ਹਾਂ ਦੇ ਉੱਤਰਾਧਿਕਾਰੀ ਨਾਲ ਜੁੜੇ ਹੋਏ ਹਨ.

ਇਸ B+Tree ਨਾਲ, ਜੇਕਰ ਤੁਸੀਂ 40 ਅਤੇ 100 ਦੇ ਵਿਚਕਾਰ ਮੁੱਲ ਲੱਭ ਰਹੇ ਹੋ:

• ਤੁਹਾਨੂੰ ਸਿਰਫ਼ 40 (ਜਾਂ 40 ਤੋਂ ਬਾਅਦ ਸਭ ਤੋਂ ਨਜ਼ਦੀਕੀ ਮੁੱਲ ਜੇਕਰ 40 ਮੌਜੂਦ ਨਹੀਂ ਹੈ) ਦੀ ਖੋਜ ਕਰਨ ਦੀ ਲੋੜ ਹੈ ਜਿਵੇਂ ਕਿ ਤੁਸੀਂ ਪਿਛਲੇ ਟ੍ਰੀ ਨਾਲ ਕੀਤਾ ਸੀ।
• ਫਿਰ ਜਦੋਂ ਤੱਕ ਤੁਸੀਂ 40 ਤੱਕ ਨਹੀਂ ਪਹੁੰਚ ਜਾਂਦੇ ਹੋ, ਸਿੱਧੇ ਵਾਰਸ ਲਿੰਕਾਂ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹੋਏ 100 ਵਾਰਸ ਇਕੱਠੇ ਕਰੋ।

ਮੰਨ ਲਓ ਕਿ ਤੁਸੀਂ M ਉੱਤਰਾਧਿਕਾਰੀ ਲੱਭਦੇ ਹੋ ਅਤੇ ਰੁੱਖ ਵਿੱਚ N ਨੋਡ ਹਨ। ਕਿਸੇ ਖਾਸ ਨੋਡ ਨੂੰ ਲੱਭਣ ਲਈ ਲੌਗ(N) ਦੀ ਲਾਗਤ ਆਉਂਦੀ ਹੈ ਜਿਵੇਂ ਕਿ ਪਿਛਲੇ ਟ੍ਰੀ. ਪਰ ਇੱਕ ਵਾਰ ਜਦੋਂ ਤੁਸੀਂ ਇਹ ਨੋਡ ਪ੍ਰਾਪਤ ਕਰ ਲੈਂਦੇ ਹੋ, ਤਾਂ ਤੁਹਾਨੂੰ M ਓਪਰੇਸ਼ਨਾਂ ਵਿੱਚ ਉਹਨਾਂ ਦੇ ਉੱਤਰਾਧਿਕਾਰੀਆਂ ਦੇ ਸੰਦਰਭਾਂ ਦੇ ਨਾਲ M ਉੱਤਰਾਧਿਕਾਰੀ ਪ੍ਰਾਪਤ ਹੋਣਗੇ. ਇਸ ਖੋਜ ਦੀ ਕੀਮਤ ਸਿਰਫ਼ M+log(N) ਹੈ ਪਿਛਲੇ ਰੁੱਖ 'ਤੇ N ਓਪਰੇਸ਼ਨਾਂ ਦੇ ਮੁਕਾਬਲੇ ਓਪਰੇਸ਼ਨ। ਇਸ ਤੋਂ ਇਲਾਵਾ, ਤੁਹਾਨੂੰ ਪੂਰਾ ਟ੍ਰੀ (ਸਿਰਫ਼ M+log(N) ਨੋਡਜ਼ ਨੂੰ ਪੜ੍ਹਨ ਦੀ ਲੋੜ ਨਹੀਂ ਹੈ), ਜਿਸਦਾ ਮਤਲਬ ਹੈ ਘੱਟ ਡਿਸਕ ਵਰਤੋਂ। ਜੇਕਰ M ਛੋਟੀ ਹੈ (ਉਦਾਹਰਨ ਲਈ 200 ਕਤਾਰਾਂ) ਅਤੇ N ਵੱਡੀ ਹੈ (1 ਕਤਾਰਾਂ), ਤਾਂ ਇੱਕ ਵੱਡਾ ਅੰਤਰ ਹੋਵੇਗਾ।

ਪਰ ਇੱਥੇ ਨਵੀਆਂ ਸਮੱਸਿਆਵਾਂ ਹਨ (ਦੁਬਾਰਾ!). ਜੇਕਰ ਤੁਸੀਂ ਡੇਟਾਬੇਸ ਵਿੱਚ ਇੱਕ ਕਤਾਰ ਜੋੜਦੇ ਜਾਂ ਮਿਟਾਉਂਦੇ ਹੋ (ਅਤੇ ਇਸਲਈ ਸੰਬੰਧਿਤ B+Tree ਸੂਚਕਾਂਕ ਵਿੱਚ):

• ਤੁਹਾਨੂੰ B+Tree ਦੇ ਅੰਦਰ ਨੋਡਸ ਦੇ ਵਿਚਕਾਰ ਕ੍ਰਮ ਨੂੰ ਕਾਇਮ ਰੱਖਣਾ ਚਾਹੀਦਾ ਹੈ, ਨਹੀਂ ਤਾਂ ਤੁਸੀਂ ਇੱਕ ਅਣ-ਛਾਂਟ ਕੀਤੇ ਰੁੱਖ ਦੇ ਅੰਦਰ ਨੋਡਾਂ ਨੂੰ ਲੱਭਣ ਦੇ ਯੋਗ ਨਹੀਂ ਹੋਵੋਗੇ।
• ਤੁਹਾਨੂੰ B+Tree ਵਿੱਚ ਪੱਧਰਾਂ ਦੀ ਘੱਟੋ-ਘੱਟ ਸੰਭਾਵਿਤ ਸੰਖਿਆ ਰੱਖਣੀ ਚਾਹੀਦੀ ਹੈ, ਨਹੀਂ ਤਾਂ O(log(N)) ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ O(N) ਬਣ ਜਾਂਦੀ ਹੈ।

ਦੂਜੇ ਸ਼ਬਦਾਂ ਵਿੱਚ, ਬੀ+ ਟ੍ਰੀ ਸਵੈ-ਕ੍ਰਮਬੱਧ ਅਤੇ ਸੰਤੁਲਿਤ ਹੋਣਾ ਚਾਹੀਦਾ ਹੈ। ਖੁਸ਼ਕਿਸਮਤੀ ਨਾਲ, ਇਹ ਸਮਾਰਟ ਡਿਲੀਟ ਅਤੇ ਇਨਸਰਟ ਓਪਰੇਸ਼ਨਾਂ ਨਾਲ ਸੰਭਵ ਹੈ। ਪਰ ਇਹ ਇੱਕ ਲਾਗਤ 'ਤੇ ਆਉਂਦਾ ਹੈ: B+ ਟ੍ਰੀ ਲਾਗਤ O(log(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).

ਐਰੇ ਬਨਾਮ ਹੈਸ਼ ਟੇਬਲ

ਇੱਕ ਐਰੇ ਦੀ ਵਰਤੋਂ ਕਿਉਂ ਨਹੀਂ ਕਰਦੇ?

ਹਮ, ਚੰਗਾ ਸਵਾਲ।

• ਹੈਸ਼ ਟੇਬਲ ਹੋ ਸਕਦਾ ਹੈ ਅੰਸ਼ਕ ਤੌਰ 'ਤੇ ਮੈਮੋਰੀ ਵਿੱਚ ਲੋਡ ਕੀਤਾ ਗਿਆ, ਅਤੇ ਬਾਕੀ ਬਚੇ ਹਿੱਸੇ ਡਿਸਕ 'ਤੇ ਰਹਿ ਸਕਦੇ ਹਨ।
• ਇੱਕ ਐਰੇ ਦੇ ਨਾਲ ਤੁਹਾਨੂੰ ਮੈਮੋਰੀ ਵਿੱਚ ਲਗਾਤਾਰ ਸਪੇਸ ਦੀ ਵਰਤੋਂ ਕਰਨੀ ਚਾਹੀਦੀ ਹੈ। ਜੇਕਰ ਤੁਸੀਂ ਇੱਕ ਵੱਡੀ ਟੇਬਲ ਲੋਡ ਕਰ ਰਹੇ ਹੋ ਕਾਫ਼ੀ ਨਿਰੰਤਰ ਸਪੇਸ ਲੱਭਣਾ ਬਹੁਤ ਮੁਸ਼ਕਲ ਹੈ.
• ਹੈਸ਼ ਟੇਬਲ ਲਈ, ਤੁਸੀਂ ਉਹ ਕੁੰਜੀ ਚੁਣ ਸਕਦੇ ਹੋ ਜੋ ਤੁਸੀਂ ਚਾਹੁੰਦੇ ਹੋ (ਉਦਾਹਰਨ ਲਈ, ਦੇਸ਼ ਅਤੇ ਵਿਅਕਤੀ ਦਾ ਆਖਰੀ ਨਾਮ)।

ਵਧੇਰੇ ਜਾਣਕਾਰੀ ਲਈ, ਤੁਸੀਂ ਇਸ ਬਾਰੇ ਲੇਖ ਪੜ੍ਹ ਸਕਦੇ ਹੋ ਜਾਵਾਹੈਸ਼ਮੈਪ, ਜੋ ਕਿ ਹੈਸ਼ ਟੇਬਲ ਦਾ ਇੱਕ ਕੁਸ਼ਲ ਲਾਗੂਕਰਨ ਹੈ; ਤੁਹਾਨੂੰ ਇਸ ਲੇਖ ਵਿੱਚ ਸ਼ਾਮਲ ਸੰਕਲਪਾਂ ਨੂੰ ਸਮਝਣ ਲਈ Java ਨੂੰ ਸਮਝਣ ਦੀ ਲੋੜ ਨਹੀਂ ਹੈ।

ਸਰੋਤ: www.habr.com