Bx-tree
কম্পিউটার বিজ্ঞানে, বিএক্স ট্রি হল এমন একটি প্রশ্ন যা গতিশীল বস্তুর জন্য দক্ষ বি + ট্রি-ভিত্তিক সূচক কাঠামো আপডেট করতে ব্যবহৃত হয়। সূচক কাঠামো বিএক্স-ট্রি-র মূল কাঠামো হল একটি বি + ট্রি যেখানে অভ্যন্তরীণ নোডগুলি একটি ডিরেক্টরি হিসাবে কাজ করে, যার প্রত্যেকটিতে তার ডান ভাইবোনের একটি পয়েন্টার থাকে। বিএক্স-ট্রি-র পূর্ববর্তী সংস্করণে, লিফ নোডগুলিতে চলন্ত-বস্তুর অবস্থানগুলি সূচীভুক্ত এবং সংশ্লিষ্ট সূচক সময় ছিল। অপ্টিমাইজড সংস্করণে, প্রতিটি লিফ নোড এন্ট্রিতে আইডি, বেগ, একক-মাত্রিক ম্যাপিং মান এবং বস্তুর সর্বশেষ আপডেট সময় থাকে। চলমান বস্তুর অবস্থান সংরক্ষণ না করে ফ্যানআউট বৃদ্ধি করা হয়, কারণ এগুলি ম্যাপিং মান থেকে প্রাপ্ত করা যেতে পারে। চলন্ত বস্তুর জন্য বি + ট্রি ব্যবহার অন্যান্য অনেক চলন্ত বস্তুর সূচক হিসাবে, একটি দ্বি-মাত্রিক চলন্ত বস্তুকে ও = (x, y), (vx, vy), টি) হিসাবে রৈখিক ফাংশন হিসাবে মডেল করা হয়, যেখানে (x, y) এবং (vx, vy) একটি নির্দিষ্ট সময়ে বস্তুর অবস্থান এবং বেগ, উদাহরণস্বরূপ t, অর্থাৎ, সর্বশেষ আপডেটের সময়। বি + ট্রি হল একক-মাত্রিক তথ্য সূচীকরণের জন্য একটি কাঠামো। বি + গাছকে একটি চলমান বস্তু সূচক হিসাবে গ্রহণ করার জন্য, বিএক্স-ট্রি একটি রৈখিককরণ কৌশল ব্যবহার করে যা টি সময়ে বস্তুর অবস্থানকে একক মাত্রিক মানে সংহত করতে সহায়তা করে। বিশেষত, বস্তুগুলি প্রথমে তাদের আপডেটের সময় অনুযায়ী ভাগ করা হয়। একই বিভাজনের মধ্যে থাকা বস্তুর জন্য, বিএক্স-ট্রি একটি নির্দিষ্ট সময়ে তাদের অবস্থান সংরক্ষণ করে যা রৈখিক ইন্টারপোলেশন দ্বারা অনুমান করা হয়। এটি করার মাধ্যমে, বিএক্স-ট্রি প্রতিটি বস্তুর আপডেট সময় সংরক্ষণ না করে একই বিভাজনের মধ্যে সমস্ত বস্তুর একটি সামঞ্জস্যপূর্ণ দৃশ্য রাখে। দ্বিতীয়ত, স্থানটি একটি গ্রিড দ্বারা বিভক্ত করা হয় এবং একটি বস্তুর অবস্থান একটি স্থান-ভরাট বক্ররেখা, যেমন, পেনো বা হিলবার্ট বক্ররেখা অনুসারে বিভাজনের মধ্যে রৈখিক করা হয়। পরিশেষে, পার্টিশন নম্বর (সময়ের তথ্য) এবং রৈখিক ক্রম (অবস্থানের তথ্য)-এর সংমিশ্রণে, একটি বস্তুকে বিএক্স-ট্রি-তে এক-মাত্রিক সূচক কী বিএক্সভ্যালু দিয়ে সূচীভুক্ত করা হয়ঃ এখানে সূচক-বিভাজন হল একটি সূচক বিভাজন যা আপডেট সময় দ্বারা নির্ধারিত হয় এবং এক্সআরপি হল সূচীভুক্ত সময়ে বস্তুর অবস্থানের স্থান-পূরণ বক্ররেখা মান, যা এক্স-এর বাইনারি মানকে নির্দেশ করে এবং "+" মানে সংযোগ। একটি বস্তু O ((7,2), (-0.1,0.05), 10), tmu = 120 দেওয়া হলে, O-এর জন্য Bx মান নিম্নরূপ গণনা করা যেতে পারে। উল্লিখিত হিসাবে পার্টিশন 0-এ O-কে সূচীভুক্ত করা হয়েছে। অতএব, সূচক বিভাজন = (00) 2। পার্টিশন 0-এর লেবেল টাইমস্ট্যাম্পে O-এর অবস্থান হল (1,5)। ক্রম = 3 সহ জেড-বক্ররেখা ব্যবহার করে, ও-এর জেড-মান, অর্থাৎ, এক্সরেপ হল (090011) 2। সূচক বিভাজন এবং এক্সআরপি সংযোগকারী, বিএক্সভ্যালু (00010011) 2 = 19। উদাহরণ ও (0,6), (0.2,-0.3), 10) এবং টিএমইউ = 120 তারপর পার্টিশনের লেবেল টাইমস্ট্যাম্পে ও-এর অবস্থানঃ? ??? সন্নিবেশ, হালনাগাদ এবং মুছে ফেলা একটি নতুন বস্তুর পরিপ্রেক্ষিতে, তার সূচক কী গণনা করা হয় এবং তারপর বস্তুটিকে বি + গাছের মতো বিএক্স-ট্রি-তে ঢোকানো হয়। একটি আপডেটে একটি মুছে ফেলার পরে একটি সন্নিবেশ থাকে। প্রতিটি সূচকের সর্বশেষতম কী রাখার জন্য একটি সহায়ক কাঠামো নিযুক্ত করা হয় যাতে কী অনুসন্ধান করে একটি বস্তু মুছে ফেলা যায়। গাছটিকে প্রভাবিত করার আগে সূচক কী গণনা করা হয়। এইভাবে, বিএক্স-ট্রি সরাসরি বি + গাছের ভাল বৈশিষ্ট্যগুলি উত্তরাধিকার সূত্রে পায় এবং দক্ষ আপডেট কর্মক্ষমতা অর্জন করে। প্রশ্ন পরিসীমা প্রশ্ন একটি পরিসীমা প্রশ্ন এমন সমস্ত বস্তু পুনরুদ্ধার করে যার অবস্থান বর্তমান সময়ের আগে নয় এমন সময়ে আয়তক্ষেত্রাকার সীমার মধ্যে পড়ে। বিএক্স-ট্রি প্রশ্নের উত্তর দেওয়ার জন্য অনুসন্ধান-উইন্ডো সম্প্রসারণ কৌশল ব্যবহার করে। যেহেতু বিএক্স-ট্রি কোনও বস্তুর অবস্থান তার আপডেটের সময়ের কিছু সময় পরে সংরক্ষণ করে, তাই সম্প্রসারণের ক্ষেত্রে দুটি ঘটনা জড়িত থাকেঃ একটি অবস্থানকে অবশ্যই পূর্ববর্তী সময়ে ফিরিয়ে আনতে হবে বা পরবর্তী সময়ে এগিয়ে নিয়ে যেতে হবে। মূল ধারণাটি হল অনুসন্ধান উইন্ডোটিকে বড় করা যাতে এটি এমন সমস্ত বস্তুগুলিকে আবদ্ধ করে যার অবস্থান তার লেবেল টাইমস্ট্যাম্পে অনুসন্ধান উইন্ডোর মধ্যে না থাকে তবে অনুসন্ধান টাইমস্ট্যাম্পে অনুসন্ধান উইন্ডোতে প্রবেশ করবে। বর্ধিতকরণের পরে, বর্ধিত অনুসন্ধান উইন্ডোতে পতিত বস্তুগুলি খুঁজে পেতে বিএক্স-ট্রি-র পার্টিশনগুলি অতিক্রম করতে হবে। প্রতিটি বিভাজনে, একটি স্থান-পূরণ বক্ররেখার ব্যবহারের অর্থ হল স্থানীয়, দ্বি-মাত্রিক স্থানে একটি পরিসীমা প্রশ্ন রূপান্তরিত, এক-মাত্রিক স্থানে পরিসীমা প্রশ্নের একটি সেট হয়ে ওঠে। তির্যক ডেটাসেটগুলির সম্প্রসারণের পরে অত্যধিক বড় অনুসন্ধান অঞ্চল এড়াতে, অনুসন্ধান অ্যালগরিদমের একটি অপ্টিমাইজেশন বিদ্যমান, যা অপ্রয়োজনীয় অনুসন্ধান বৃদ্ধি এড়ানোর মাধ্যমে অনুসন্ধান দক্ষতা উন্নত করে। কে নিকটতম প্রতিবেশী প্রশ্ন কে নিকটতম প্রতিবেশী প্রশ্ন কে উত্তর না পাওয়া পর্যন্ত ক্রমবর্ধমান বর্ধিত অনুসন্ধান অঞ্চলের সাথে পুনরাবৃত্তভাবে পরিসীমা প্রশ্ন সম্পাদন করে গণনা করা হয়। আরেকটি সম্ভাবনা হল দ্য আইডিস্ট্যান্স টেকনিক-এ অনুরূপ অনুসন্ধানের ধারণাগুলি ব্যবহার করা। অন্যান্য প্রশ্ন পরিসীমা প্রশ্ন এবং কে নিকটবর্তী প্রতিবেশী প্রশ্ন অ্যালগরিদমগুলি সহজেই ব্যবধানের প্রশ্ন, অবিচ্ছিন্ন প্রশ্ন ইত্যাদি সমর্থন করার জন্য প্রসারিত করা যেতে পারে। যেহেতু বিএক্স-ট্রি একটি বি + ট্রি সূচকের উপরে নির্মিত একটি সূচক, তাই সন্নিবেশ, মুছে ফেলা এবং অনুসন্ধান সহ বিএক্স-ট্রি-র সমস্ত ক্রিয়াকলাপ বি + ট্রি-র মতোই। এই ক্রিয়াকলাপগুলির বাস্তবায়নের কোনও পরিবর্তন করার প্রয়োজন নেই। একমাত্র পার্থক্য হল বিদ্যমান ডিবিএমএস-এ একটি সংরক্ষিত পদ্ধতি হিসাবে সূচক কী প্রাপ্ত করার পদ্ধতি বাস্তবায়ন করা। অতএব, কার্নেল স্পর্শ না করেই বিদ্যমান ডিবিএমএস-এ সহজেই বিএক্স-ট্রি সংহত করা যেতে পারে। স্প্যাড হল একটি জনপ্রিয় রিলেশনাল ডাটাবেস সিস্টেম মাইএসকিউএল-এর উপরে নির্মিত মুভিং অবজেক্ট ম্যানেজমেন্ট সিস্টেম, যা বস্তুর সূচীকরণের জন্য বিএক্স-ট্রি ব্যবহার করে। বাস্তবায়নে, মুভিং অবজেক্ট ডেটা রূপান্তরিত হয় এবং সরাসরি মাইএসকিউএল-এ সংরক্ষণ করা হয়, এবং প্রশ্নগুলি স্ট্যান্ডার্ড এসকিউএল বিবৃতিতে রূপান্তরিত হয় যা রিলেশনাল ইঞ্জিনে দক্ষতার সাথে প্রক্রিয়া করা হয়। সবচেয়ে গুরুত্বপূর্ণ বিষয় হল, এই সমস্তগুলি মাইএসকিউএল-এর মূল অংশে অনুপ্রবেশ না করেই সুন্দরভাবে এবং স্বাধীনভাবে অর্জন করা হয়। পারফরম্যান্স টিউনিং ডেটা স্ক্যু সহ সম্ভাব্য সমস্যা বিএক্স ট্রি দ্বিমাত্রিক অবস্থানকে এক-মাত্রিক কীতে ম্যাপ করার সময় স্থান বিভাজনের জন্য একটি গ্রিড ব্যবহার করে। এটি তির্যক তথ্য নিয়ে কাজ করার সময় অনুসন্ধান এবং আপডেট অপারেশন উভয় ক্ষেত্রেই কর্মক্ষমতার অবনতি ঘটাতে পারে। যদি গ্রিড কোষটি অতিরিক্ত আকারের হয়, তবে একটি কোষে অনেকগুলি বস্তু থাকে। যেহেতু একটি কোষের বস্তুগুলি সূচকের থেকে আলাদা করা যায় না, তাই অন্তর্নিহিত বি + ট্রি-তে কিছু ওভারফ্লো নোড থাকবে। ওভারফ্লো পৃষ্ঠাগুলির উপস্থিতি কেবল গাছের ভারসাম্য নষ্ট করে না, আপডেটের খরচও বাড়ায়। প্রশ্নগুলির ক্ষেত্রে, প্রদত্ত প্রশ্ন অঞ্চলের জন্য, বড় কোষ আরও বেশি ফলস পজিটিভ দেয় এবং প্রক্রিয়াকরণের সময় বাড়ায়। অন্যদিকে, যদি স্থানটি সূক্ষ্ম গ্রিডের সাথে ভাগ করা হয়, অর্থাৎ। ছোট কোষ, প্রতিটি কোষে কয়েকটি বস্তু থাকে। খুব কমই ওভারফ্লো পেজ রয়েছে যাতে আপডেটের খরচ কমানো যায়। একটি ক্যোয়ারিতে কম মিথ্যা পজিটিভ পাওয়া যায়। তবে, আরও কোষ অনুসন্ধান করা প্রয়োজন। অনুসন্ধান করা কোষের সংখ্যা বৃদ্ধি একটি প্রশ্নের কাজের চাপও বাড়ায়। ইন্ডেক্স টিউনিং এস. টি. টু. বি-ট্রি বি. এক্স-ট্রি-র কর্মক্ষমতা সুর করার জন্য একটি স্ব-টিউনিং কাঠামো প্রবর্তন করে যখন স্থানের ডেটা স্ক্যু এবং সময়ের সাথে ডেটা পরিবর্তন নিয়ে কাজ করে। মহাকাশে তথ্য তির্যক মোকাবেলা করার জন্য, এস. টি. টু. বি-ট্রি রেফারেন্স পয়েন্টগুলির একটি সেট ব্যবহার করে সমগ্র স্থানটিকে বিভিন্ন বস্তুর ঘনত্বের অঞ্চলে বিভক্ত করে। প্রতিটি অঞ্চল একটি পৃথক গ্রিড ব্যবহার করে যার কোষের আকার তার ভিতরের বস্তুর ঘনত্ব দ্বারা নির্ধারিত হয়। বিভিন্ন সময়ের ব্যবধান সম্পর্কে বিএক্স-ট্রি-র একাধিক পার্টিশন রয়েছে। সময়ের সাথে সাথে, প্রতিটি পার্টিশন পর্যায়ক্রমে বৃদ্ধি পায় এবং সঙ্কুচিত হয়। এস. টি. টু. বি-ট্রি এই বৈশিষ্ট্যটি ব্যবহার করে অনলাইনে সূচকটি সুর করতে যাতে সময়ের সাথে সাথে ডেটা পরিবর্তনের সাথে নিজেকে সামঞ্জস্য করতে স্থান বিভাজন সামঞ্জস্য করা যায়। বিশেষত, যখন একটি পার্টিশন সঙ্কুচিত হয়ে খালি হয়ে যায় এবং বাড়তে শুরু করে, তখন এটি সর্বশেষ তথ্য ঘনত্ব অনুযায়ী প্রতিটি রেফারেন্স পয়েন্টের জন্য একটি নতুন সেট রেফারেন্স পয়েন্ট এবং নতুন গ্রিড বেছে নেয়। টিউনিং একটি নির্দিষ্ট সময়ের মধ্যে সংগৃহীত সর্বশেষ পরিসংখ্যানের উপর ভিত্তি করে করা হয়, যাতে স্থান বিভাজনের উপায়টি সর্বশেষ তথ্য বিতরণের সাথে সর্বোত্তমভাবে খাপ খায় বলে মনে করা হয়। এই উপায়ে, এস. টি. টু. বি-ট্রি স্থান এবং সময়ের সাথে ডেটা পরিবর্তনের কারণে সৃষ্ট প্রভাবকে হ্রাস করবে বলে আশা করা হচ্ছে। আরও দেখুন বি + ট্রি হিলবার্ট কার্ভ জেড-অর্ডার (কার্ভ) রেফারেন্স বি-ট্রি