হে হাবর! আমি নিবন্ধটির অনুবাদ আপনার দৃষ্টি আকর্ষণ করছি
"কিভাবে একটি রিলেশনাল ডাটাবেস কাজ করে".

যখন রিলেশনাল ডাটাবেসের কথা আসে তখন আমি সাহায্য করতে পারি না কিন্তু মনে হয় কিছু অনুপস্থিত। এগুলি সর্বত্র ব্যবহৃত হয়। ছোট এবং দরকারী SQLite থেকে শক্তিশালী টেরাডাটা পর্যন্ত অনেকগুলি বিভিন্ন ডেটাবেস উপলব্ধ রয়েছে৷ কিন্তু ডাটাবেস কিভাবে কাজ করে তা ব্যাখ্যা করে মাত্র কয়েকটি নিবন্ধ রয়েছে। কত কম ফলাফল আছে তা দেখতে আপনি "howdoesarelationaldatabasework" ব্যবহার করে নিজের জন্য অনুসন্ধান করতে পারেন। তাছাড়া, এই নিবন্ধগুলি ছোট। আপনি যদি লেটেস্ট Buzzy প্রযুক্তি (BigData, NoSQL বা JavaScript) খুঁজছেন, তাহলে তারা কীভাবে কাজ করে তা ব্যাখ্যা করে আপনি আরও গভীর নিবন্ধ খুঁজে পাবেন।

রিলেশনাল ডাটাবেস কি খুব পুরানো এবং খুব বিরক্তিকর বিশ্ববিদ্যালয়ের কোর্স, গবেষণাপত্র এবং বইয়ের বাইরে ব্যাখ্যা করা যায়?

একজন বিকাশকারী হিসাবে, আমি এমন কিছু ব্যবহার করা ঘৃণা করি যা আমি বুঝতে পারি না। এবং যদি ডাটাবেসগুলি 40 বছরেরও বেশি সময় ধরে ব্যবহার করা হয় তবে অবশ্যই একটি কারণ থাকতে হবে। বছরের পর বছর ধরে, আমি প্রতিদিন ব্যবহার করি এই অদ্ভুত ব্ল্যাক বক্সগুলিকে সত্যিকার অর্থে বুঝতে শত শত ঘন্টা ব্যয় করেছি। রিলেশনাল ডাটাবেস খুব আকর্ষণীয় কারণ তারা দরকারী এবং পুনরায় ব্যবহারযোগ্য ধারণার উপর ভিত্তি করে. আপনি যদি একটি ডাটাবেস বুঝতে আগ্রহী হন, কিন্তু এই বিস্তৃত বিষয়ে গভীরভাবে চিন্তা করার সময় বা প্রবণতা না পান তবে আপনার এই নিবন্ধটি উপভোগ করা উচিত।

যদিও এই নিবন্ধের শিরোনাম স্পষ্ট, এই নিবন্ধের উদ্দেশ্য কিভাবে ডাটাবেস ব্যবহার করতে হয় বুঝতে হয় না। তাই আপনার ইতিমধ্যেই জানা উচিত কিভাবে একটি সহজ সংযোগ অনুরোধ এবং মৌলিক প্রশ্ন লিখতে হয় সিআরইউডি; অন্যথায় আপনি এই নিবন্ধটি বুঝতে পারবেন না। এটি শুধুমাত্র আপনার জানা প্রয়োজন, আমি বাকি ব্যাখ্যা করব।

আমি কিছু কম্পিউটার সায়েন্স বেসিক দিয়ে শুরু করব, যেমন অ্যালগরিদমের সময় জটিলতা (BigO)। আমি জানি আপনাদের মধ্যে কেউ কেউ এই ধারণাটিকে ঘৃণা করেন, কিন্তু এটি ছাড়া আপনি ডাটাবেসের ভিতরের জটিলতাগুলি বুঝতে সক্ষম হবেন না। যেহেতু এটি একটি বিশাল বিষয়, আমি ফোকাস করব আমি যা গুরুত্বপূর্ণ মনে করি: কিভাবে ডাটাবেস প্রক্রিয়া এসকিউএল অনুসন্ধান. আমি শুধু পরিচয় করিয়ে দেব মৌলিক ডাটাবেস ধারণাযাতে নিবন্ধের শেষে আপনি হুডের নীচে কী ঘটছে তা সম্পর্কে ধারণা পান।

যেহেতু এটি একটি দীর্ঘ এবং প্রযুক্তিগত নিবন্ধ যাতে প্রচুর অ্যালগরিদম এবং ডেটা স্ট্রাকচার জড়িত, তাই এটি পড়ার জন্য আপনার সময় নিন। কিছু ধারণা বোঝা কঠিন হতে পারে; আপনি তাদের এড়িয়ে যেতে পারেন এবং এখনও সাধারণ ধারণা পেতে পারেন।

আপনার মধ্যে আরও বেশি জ্ঞানীদের জন্য, এই নিবন্ধটি 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: আপনি যদি এই জটিলতার সম্মুখীন হন, তাহলে আপনার নিজেকে জিজ্ঞাসা করা উচিত যে এটি সত্যিই আপনার কার্যকলাপের ক্ষেত্র কিনা...

দ্রষ্টব্য: আমি আপনাকে বড় হে উপাধির প্রকৃত সংজ্ঞা দিইনি, শুধু একটি ধারণা। আপনি এই নিবন্ধটি পড়তে পারেন উইকিপিডিয়া বাস্তব (অ্যাসিম্পোটিক) সংজ্ঞার জন্য।

মার্জসর্ট

আপনি একটি সংগ্রহ বাছাই করার প্রয়োজন হলে আপনি কি করবেন? কি? আপনি 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-মেগাবাইট মেমরি বাফার সহ একটি মাল্টি-গিগাবাইট টেবিল সাজাতে হবে।

দ্রষ্টব্য: এই ধরনের অ্যালগরিদম বলা হয় বাহ্যিক সাজানোর.

• আপনি একাধিক প্রক্রিয়া/থ্রেড/সার্ভারে চালানোর জন্য এটি পরিবর্তন করতে পারেন।

উদাহরণস্বরূপ, ডিস্ট্রিবিউটেড মার্জ সর্ট হল মূল উপাদানগুলির মধ্যে একটি Hadoop (যা বড় ডেটার একটি কাঠামো)।

• এই অ্যালগরিদম সীসাকে সোনায় পরিণত করতে পারে (সত্যিই!)

এই সাজানোর অ্যালগরিদম বেশিরভাগ (যদি সব না) ডাটাবেসে ব্যবহৃত হয়, তবে এটি একমাত্র নয়। আপনি আরো জানতে চান, আপনি এটি পড়তে পারেন গবেষণা কাজ, যা সাধারণ ডাটাবেস বাছাই অ্যালগরিদমগুলির সুবিধা এবং অসুবিধাগুলি নিয়ে আলোচনা করে৷

অ্যারে, ট্রি এবং হ্যাশ টেবিল

এখন যেহেতু আমরা সময়ের জটিলতা এবং সাজানোর ধারণাটি বুঝতে পেরেছি, আমার আপনাকে 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, নোড বিদ্যমান. আমি নোডের ভিতরে সারি আইডি পুনরুদ্ধার করি (ছবিতে দেখানো হয়নি) এবং প্রদত্ত সারি আইডির জন্য টেবিলে তাকাই।
• সারি আইডি জানার ফলে আমি টেবিলে ডেটা ঠিক কোথায় আছে তা জানতে পারি, তাই আমি তাৎক্ষণিকভাবে এটি পুনরুদ্ধার করতে পারি।

শেষ পর্যন্ত, উভয় অনুসন্ধানই আমাকে গাছের ভিতরের স্তরের সংখ্যা ব্যয় করবে। আপনি যদি মার্জ সাজানোর অংশটি মনোযোগ সহকারে পড়েন, তাহলে আপনাকে দেখতে হবে যে সেখানে লগ(N) স্তর রয়েছে। দেখা যাচ্ছে, অনুসন্ধান খরচ লগ(N), খারাপ না!

আমাদের সমস্যায় ফিরে আসা যাক

কিন্তু এটি খুবই বিমূর্ত, তাই আসুন আমাদের সমস্যায় ফিরে আসি। একটি সাধারণ পূর্ণসংখ্যার পরিবর্তে, একটি স্ট্রিং কল্পনা করুন যা পূর্ববর্তী সারণিতে কারো দেশের প্রতিনিধিত্ব করে। ধরা যাক আপনার কাছে একটি গাছ আছে যাতে টেবিলের "দেশ" ক্ষেত্র (কলাম 3) রয়েছে:

• যুক্তরাজ্যে কারা কাজ করেন জানতে চাইলে
• গ্রেট ব্রিটেনের প্রতিনিধিত্ব করে এমন নোড পেতে আপনি গাছের দিকে তাকান
• "UKnode" এর ভিতরে আপনি UK কর্মীদের রেকর্ডের অবস্থান খুঁজে পাবেন।

যদি আপনি সরাসরি অ্যারে ব্যবহার করেন তবে N অপারেশনের পরিবর্তে এই অনুসন্ধানের জন্য লগ(N) অপারেশন খরচ হবে। আপনি এইমাত্র উপস্থাপন করেছেন ডাটাবেস সূচক.

আপনি যে কোনো গ্রুপের ক্ষেত্রের জন্য একটি সূচী গাছ তৈরি করতে পারেন (স্ট্রিং, সংখ্যা, 2 লাইন, সংখ্যা এবং স্ট্রিং, তারিখ...) যতক্ষণ না আপনার কাছে কীগুলির তুলনা করার জন্য একটি ফাংশন থাকে (যেমন ফিল্ড গ্রুপ) যাতে আপনি সেট করতে পারেন চাবি মধ্যে অর্ডার (যা ডাটাবেসের কোন মৌলিক ধরনের ক্ষেত্রে)।

B+TreeIndex

যদিও এই গাছটি একটি নির্দিষ্ট মান পাওয়ার জন্য ভাল কাজ করে, আপনার প্রয়োজনের সময় একটি বড় সমস্যা রয়েছে দুটি মানের মধ্যে একাধিক উপাদান পান. এর জন্য O(N) খরচ হবে কারণ আপনাকে গাছের প্রতিটি নোডের দিকে তাকাতে হবে এবং এটি এই দুটি মানের মধ্যে আছে কিনা তা পরীক্ষা করতে হবে (যেমন গাছের একটি আদেশকৃত ট্রাভার্সাল সহ)। তাছাড়া, এই অপারেশনটি ডিস্ক I/O বন্ধুত্বপূর্ণ নয় যেহেতু আপনাকে পুরো গাছটি পড়তে হবে। আমাদের দক্ষতার সাথে কার্যকর করার একটি উপায় খুঁজে বের করতে হবে পরিসীমা অনুরোধ. এই সমস্যা সমাধানের জন্য, আধুনিক ডাটাবেসগুলি B+Tree নামক পূর্ববর্তী গাছের একটি পরিবর্তিত সংস্করণ ব্যবহার করে। একটি বি + ট্রি গাছে:

• শুধুমাত্র সর্বনিম্ন নোড (পাতা) দোকান তথ্য (সম্পর্কিত টেবিলে সারিগুলির অবস্থান)
• বাকি নোড এখানে আছে রাউটিং এর জন্য সঠিক নোডে অনুসন্ধানের সময়.

আপনি দেখতে পাচ্ছেন, এখানে আরও নোড রয়েছে (দুইবার)। প্রকৃতপক্ষে, আপনার অতিরিক্ত নোড আছে, "সিদ্ধান্ত নোড", যা আপনাকে সঠিক নোড খুঁজে পেতে সাহায্য করবে (যা সংশ্লিষ্ট টেবিলে সারিগুলির অবস্থান সংরক্ষণ করে)। কিন্তু অনুসন্ধান জটিলতা এখনও 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-এর ভিতরে নোডগুলির মধ্যে শৃঙ্খলা বজায় রাখতে হবে, অন্যথায় আপনি একটি unsorted গাছের ভিতরে নোডগুলি খুঁজে পেতে সক্ষম হবেন না।
• আপনাকে অবশ্যই B+Tree-এ ন্যূনতম সম্ভাব্য সংখ্যক স্তর রাখতে হবে, অন্যথায় O(log(N)) সময়ের জটিলতা O(N) হয়ে যাবে।

অন্য কথায়, B+Tree অবশ্যই স্ব-ক্রম এবং ভারসাম্যপূর্ণ হতে হবে। সৌভাগ্যবশত, এটি স্মার্ট ডিলিট এবং ইনসার্ট অপারেশনের মাধ্যমে সম্ভব। কিন্তু এটি একটি খরচে আসে: একটি B+ গাছে সন্নিবেশ এবং মুছে ফেলার খরচ O(log(N))। এই কারণেই আপনারা কেউ কেউ শুনেছেন অনেকগুলি সূচক ব্যবহার করা ভাল ধারণা নয়. সত্যিই, আপনি একটি টেবিলে একটি সারির দ্রুত সন্নিবেশ/আপডেট/মুছে ফেলার গতি কমিয়ে দিচ্ছেনকারণ ডাটাবেসকে প্রতিটি সূচকের জন্য একটি ব্যয়বহুল O(log(N)) অপারেশন ব্যবহার করে টেবিলের সূচী আপডেট করতে হবে। অধিকন্তু, সূচী যোগ করার অর্থ হল আরও কাজের চাপ লেনদেন ব্যবস্থাপক (প্রবন্ধের শেষে বর্ণনা করা হবে)।

আরো বিস্তারিত জানার জন্য, আপনি উইকিপিডিয়া নিবন্ধ দেখতে পারেন B+গাছ. আপনি যদি একটি ডাটাবেসে B+Tree বাস্তবায়নের উদাহরণ চান, তাহলে একবার দেখুন এই নিবন্ধটি и এই নিবন্ধটি একটি নেতৃস্থানীয় 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).

অ্যারে বনাম হ্যাশ টেবিল

কেন একটি অ্যারে ব্যবহার করবেন না?

হুম, ভালো প্রশ্ন।

• হ্যাশ টেবিল হতে পারে আংশিকভাবে মেমরি লোড, এবং অবশিষ্ট অংশগুলি ডিস্কে থাকতে পারে।
• একটি অ্যারের সাথে আপনাকে অবশ্যই মেমরিতে সংলগ্ন স্থান ব্যবহার করতে হবে। আপনি যদি একটি বড় টেবিল লোড করা হয় পর্যাপ্ত অবিচ্ছিন্ন স্থান খুঁজে পাওয়া খুব কঠিন.
• একটি হ্যাশ টেবিলের জন্য, আপনি যে কীটি চান তা নির্বাচন করতে পারেন (উদাহরণস্বরূপ, দেশ এবং ব্যক্তির শেষ নাম)।

আরো তথ্যের জন্য, আপনি সম্পর্কে নিবন্ধ পড়তে পারেন জাভাহ্যাশ মানচিত্র, যা একটি হ্যাশ টেবিলের একটি দক্ষ বাস্তবায়ন; এই নিবন্ধে কভার করা ধারণাগুলি বোঝার জন্য আপনাকে জাভা বোঝার দরকার নেই।

উত্স: www.habr.com