PH-tree
পিএইচ-ট্রি হল একটি বৃক্ষ তথ্য কাঠামো যা ভৌগোলিক স্থানাঙ্ক, বিন্দু, বৈশিষ্ট্য ভেক্টর, আয়তক্ষেত্র বা বাউন্ডিং বাক্সের মতো বহুমাত্রিক তথ্যের (কী) স্থানিক সূচীকরণের জন্য ব্যবহৃত হয়। পিএইচ-ট্রি হল একটি চতুর্ভুজ বা অষ্টকের অনুরূপ কাঠামো সহ স্থান বিভাজন সূচক। যাইহোক, চতুর্ভুজের বিপরীতে, এটি ট্রাই-এর উপর ভিত্তি করে এবং ক্রিট বিট গাছের অনুরূপ একটি বিভাজন নীতি ব্যবহার করে যা কীগুলির বিট-উপস্থাপনার উপর ভিত্তি করে। বিট-ভিত্তিক বিভাজন নীতি, যখন নোডের জন্য বিভিন্ন অভ্যন্তরীণ উপস্থাপনা ব্যবহারের সাথে মিলিত হয়, তখন উচ্চ-মাত্রিক তথ্যের সাথে মাপযোগ্যতা প্রদান করে। বিট-রিপ্রেজেন্টেশন বিভাজন নীতিও সর্বাধিক গভীরতা আরোপ করে, এইভাবে অবক্ষয়িত গাছ এবং পুনরায় ভারসাম্য বজায় রাখার প্রয়োজনীয়তা এড়ানো হয়। সংক্ষিপ্ত বিবরণ মৌলিক পিএইচ-ট্রি হল একটি স্থানিক সূচক যা ব্যবহারকারীর সংজ্ঞায়িত মানগুলিতে পূর্ণসংখ্যা সহ-মাত্রিক ভেক্টর কীগুলিকে ম্যাপ করে। পিএইচ-ট্রি হল একটি ক্রিট বিট গাছের একটি বহুমাত্রিক সাধারণীকরণ এই অর্থে যে একটি ক্রিট বিট ট্রি-মাত্রিক কী সহ একটি পিএইচ-গাছের সমতুল্য। ক্রিট বিট গাছের মতো, এবং অন্যান্য স্থানিক সূচকগুলির মতো নয়, পিএইচ-ট্রি একটি মাল্টিম্যাপের পরিবর্তে একটি মানচিত্র। একটি-মাত্রিক পিএইচ-ট্রি হল নোডের একটি গাছ যেখানে প্রতিটি নোড বিভাজন স্থানটিকে চতুর্ভুজে বিভক্ত করে (উচ্চ মাত্রিক তথ্য সহ সম্ভাব্য বড় নোডগুলি কতটা স্কেল করে তার জন্য নীচে দেখুন)। প্রতিটি কোয়াড্রেন্টে সর্বাধিক একটি এন্ট্রি থাকে, হয় একটি কী-ভ্যালু পেয়ার (লিফ কোয়াড্রেন্ট) অথবা একটি কী-সাবনোড পেয়ার। একটি কী-সাবনোড জুটির জন্য, কীটি সাবনোডের কেন্দ্রকে উপস্থাপন করে। সাবনোড এবং এর চাইল্ড সাবনোডের সমস্ত কী-এর সাধারণ উপসর্গ (বিট-উপস্থাপনা) হল কী। প্রতিটি নোডে কমপক্ষে দুটি এন্ট্রি থাকে, অন্যথায় এটি প্যারেন্ট নোডের সাথে মিশে যায়। পিএইচ-গাছের অন্যান্য কিছু কাঠামোগত বৈশিষ্ট্য হলঃ এগুলি হল-আরি গাছ। এগুলি সহজাতভাবে ভারসাম্যহীন তবে ভারসাম্যহীনতা সীমাবদ্ধ কারণ তাদের গভীরতা কীগুলির বিট প্রস্থের মধ্যে সীমাবদ্ধ, যেমন। 32 বিট পূর্ণসংখ্যা সহ একটি-মাত্রিক কী-এর জন্য 32। সন্নিবেশ বা অপসারণ ক্রিয়াকলাপের ফলে ঠিক একটি নোড পরিবর্তন করা হয় এবং সম্ভাব্যভাবে একটি দ্বিতীয় নোড যুক্ত বা অপসারণ করা হয়। এটি সমবর্তী বাস্তবায়নের জন্য কার্যকর হতে পারে। এর অর্থ হল সংশোধন ব্যয়ের ক্ষেত্রে সামান্য পরিবর্তন। তাদের গঠন সন্নিবেশ/অপসারণ ক্রম থেকে স্বাধীন। বিভাজন কৌশল বেশিরভাগ চতুর্ভুজের মতো, পিএইচ-ট্রি নোডের একটি শ্রেণিবিন্যাস যেখানে প্রতিটি নোড সমস্ত মাত্রায় স্থানটি বিভক্ত করে। সুতরাং, একটি নোডে প্রতিটি চতুর্থাংশের জন্য একটি করে সাবনোড থাকতে পারে। চতুর্ভুজ সংখ্যায়ন পি. এইচ-ট্রি বহু-মাত্রিক কীগুলির বিটগুলি ব্যবহার করে গাছে তাদের অবস্থান নির্ধারণ করে। যে সমস্ত চাবিগুলির শীর্ষস্থানীয় বিট রয়েছে সেগুলি গাছের একই শাখায় সংরক্ষণ করা হয়। উদাহরণস্বরূপ, স্তরে একটি নোডে, চতুর্থাংশ নির্ধারণ করতে যেখানে একটি কী ঢোকানো উচিত (বা সরানো বা উপরে দেখা), এটি কীটির প্রতিটি মাত্রার 's বিট'-এর দিকে তাকায়। 8টি চতুর্ভুজ (একটি ঘনক্ষেত্র গঠন) সহ একটি থ্রিডি নোডের জন্য চাবিটির প্রথম মাত্রার 'এস' বিট নির্ধারণ করে যে লক্ষ্য চতুর্ভুজটি ঘনক্ষেত্রের বাম বা ডানদিকে রয়েছে কিনা, দ্বিতীয় মাত্রার 'এস' বিট নির্ধারণ করে যে এটি সামনে বা পিছনে রয়েছে কিনা, এবং তৃতীয় মাত্রার 'এস' বিট নীচে বনাম উপরে নির্ধারণ করে, ছবি দেখুন। 1ডি উদাহরণ 8 বিট মান সহ তিনটি 1ডি কী সহঃ, এবং। একটি খালি গাছে যোগ করার ফলে একটি একক নোড তৈরি হয়। দুটি কী প্রথমে তাদের 6ষ্ঠ বিটে পৃথক হয় তাই নোডের একটি স্তর থাকে (0 দিয়ে শুরু করে)। নোডের একটি 5 বিট উপসর্গ রয়েছে যা উভয় কী-এর সাধারণ 5 বিটের প্রতিনিধিত্ব করে। নোডের দুটি চতুর্থাংশ রয়েছে, প্রতিটি কী একটি চতুর্থাংশে সংরক্ষণ করা হয়। একটি তৃতীয় কী যোগ করার ফলে একটি অতিরিক্ত নোডে একটি চতুর্থাংশে মূল নোডটি সাবনোড হিসাবে এবং অন্য চতুর্থাংশে নতুন কী রয়েছে। 2ডি উদাহরণ 2ডি কী দিয়ে প্রতিটি নোডে চতুর্ভুজ থাকে। চতুর্থাংশের অবস্থান যেখানে একটি কী সংরক্ষণ করা হয় তা প্রতিটি মাত্রা থেকে এক বিট করে কীগুলির সংশ্লিষ্ট বিটগুলি থেকে বের করা হয়। নোডের চারটি চতুর্ভুজ একটি 2ডি হাইপারকিউব গঠন করে (চতুর্ভুজ খালি হতে পারে)। কীগুলি থেকে যে বিটগুলি বের করা হয় তা হাইপারকিউব ঠিকানা গঠন করে, জন্য এবং জন্য। কার্যকরভাবে নোডের হাইপারকিউবে চতুর্ভুজের অবস্থান। নোড কাঠামো একটি নোডে এন্ট্রিগুলির ক্রম সর্বদা জেড-অর্ডারিং অনুসরণ করে। উদাহরণস্বরূপ, একটি নোডে প্রবেশগুলি নির্দিষ্ট আকারের অ্যারেতে সংরক্ষণ করা যেতে পারে। তারপর কার্যকরভাবে একটি চতুর্থাংশের অ্যারে সূচক। এটি সন্ধান, সন্নিবেশ এবং অপসারণের অনুমতি দেয় এবং সংরক্ষণ করার কোনও প্রয়োজন নেই। স্থান জটিলতা যদিও প্রতি নোডে হয়, তাই এটি উচ্চ মাত্রিক তথ্যের জন্য কম উপযুক্ত। আরেকটি সমাধান হল একটি সাজানো সংগ্রহে এন্ট্রি সংরক্ষণ করা, যেমন গতিশীল অ্যারে এবং/অথবা বি-গাছ। এটি সন্ধানের ক্রিয়াকলাপকে ধীর করে দেয় তবে মেমরি খরচকে হ্রাস করে। মূল বাস্তবায়নের লক্ষ্য হল কম মেমরি ব্যবহার করে স্থির এবং গতিশীল অ্যারে উপস্থাপনার মধ্যে স্যুইচ করে ন্যূনতম মেমরি খরচ করা। অন্যান্য বাস্তবায়নগুলি গতিশীলভাবে পরিবর্তিত হয় না তবে উচ্চ মাত্রিক তথ্যের জন্য নির্দিষ্ট অ্যারে, গতিশীল অ্যারে এবং বি-ট্রি ব্যবহার করে। অপারেশন লুকআপ, সন্নিবেশ এবং অপসারণ অপারেশনগুলি খুব একইভাবে কাজ করেঃ সঠিক নোডটি খুঁজে বের করুন, তারপরে নোডে অপারেশনটি সম্পাদন করুন। উইন্ডো প্রশ্ন এবং-নিকটতম-প্রতিবেশী অনুসন্ধানগুলি আরও জটিল। লুকআপ অপারেশন নির্ধারণ করে যে গাছের মধ্যে কোনও চাবি রয়েছে কিনা। এটি গাছের নিচে চলে যায় এবং প্রতিটি নোড পরীক্ষা করে যে এতে একটি প্রার্থী সাবনোড বা কী-এর সাথে মেলে এমন একটি ব্যবহারকারী মান রয়েছে কিনা। ফাংশন লুকআপ (কী) হল এন্ট্রি-গেট _ রুট _ এন্ট্রি ()// যদি ট্রি খালি না থাকে তবে রুট এন্ট্রিতে এন্ট্রির সময় একটি রুট নোড থাকে! = এনআইএল এবং & entry.is_subnode () ডু নোড-entry.get_node () এন্ট্রি-node.get_entry (কী) রিপিট রিটার্ন এন্ট্রি// এন্ট্রি-টি এনআইএল ফাংশন হতে পারে গেট _ এন্ট্রি (কী) হল নোড-বর্তমান নোড এইচ-এক্সট্র্যাক্ট _ বিটস _ অ্যাট _ ডেপথ (কী, node.get_depth ()) এন্ট্রি-node.get_entry_at (এইচ) রিটার্ন এন্ট্রি// এন্ট্রি-টি নিল হতে পারে। অপারেশনটি লুকআপ ফাংশনের মতো ট্রি অতিক্রম করে এবং তারপর কীটি নোডে ঢোকায়। বিবেচনা করার মতো বেশ কয়েকটি বিষয় রয়েছেঃ চতুর্থাংশটি খালি এবং আমরা কেবল চতুর্থাংশে একটি নতুন এন্ট্রি সন্নিবেশ করতে পারি এবং ফিরে আসতে পারি। চতুর্থাংশে একটি কী সহ একটি ব্যবহারকারী এন্ট্রি রয়েছে যা নতুন এন্ট্রির অনুরূপ। এই ধরনের সংঘর্ষ মোকাবেলা করার একটি উপায় হল একটি পতাকা ফেরত দেওয়া যা ব্যর্থ সন্নিবেশ নির্দেশ করে। যদি ট্রিটি নোডের এন্ট্রি হিসাবে একটি সংগ্রহ সহ মাল্টি-ম্যাপ হিসাবে প্রয়োগ করা হয়, তবে সেই সংগ্রহে নতুন মান যোগ করা হয়। চতুর্থাংশে একটি ভিন্ন কী সহ একটি এন্ট্রি (ব্যবহারকারী এন্ট্রি বা সাবনোড এন্ট্রি) রয়েছে। এই ক্ষেত্রে একটি নতুন সাবনোডের সাথে বিদ্যমান এন্ট্রি প্রতিস্থাপন করা প্রয়োজন যা পুরানো এবং নতুন এন্ট্রি ধারণ করে। ফাংশন সন্নিবেশ (নোড, কী, মান) স্তরের জন্য node.get_level ()// স্তর হল 0, মূলের জন্য node.get_level ()// স্তরের জন্য node.get_entry (এইচ) যদি প্রবেশ = = এনআইএল হয় তাহলে// কেস 1. প্রবেশ _ নতুন → তৈরি _ প্রবেশ (কী, মান) node.set_entry (এইচ, এন্ট্রি _ নতুন) অন্যথায় যদি! entry.is_subnode () & & entry.get_key () = = তারপর// কেস 2। সংঘর্ষ, ইতিমধ্যে একটি এন্ট্রি রিটার্ন রয়েছে-ব্যর্থ _ সন্নিবেশ অন্য// কেস 3. স্তর _ পার্থক্য-প্রাপ্ত _ স্তর _ পার্থক্য (কী, entry.get_key ()) এন্ট্রি _ নতুন-বিদ্যমান এন্ট্রি এবং নতুন এন্ট্রি সহ তৈরি _ এন্ট্রি (কী, মান)/নতুন সাবনোড-তৈরি _ নোড (স্তর _ পার্থক্য, এন্ট্রি, এন্ট্রি _ নতুন) node.set_entry (এইচ, সাবনোড _ নতুন) শেষ যদি রিটার্ন রিমুভ রিমুভাল সন্নিবেশের বিপরীতভাবে কাজ করে, অতিরিক্ত সীমাবদ্ধতা সহ যে কোনও সাবনোড অপসারণ করতে হবে যদি দুটি এন্ট্রির চেয়ে কম থাকে। অবশিষ্ট এন্ট্রিটি প্যারেন্ট নোডে স্থানান্তরিত হয়। উইন্ডোজ প্রশ্নগুলি হল এমন প্রশ্ন যা আয়তক্ষেত্রাকার অক্ষ-সারিবদ্ধ হাইপারবক্সের ভিতরে থাকা সমস্ত কীগুলি ফেরত দেয়। এগুলিকে দ্বি-মাত্রিক বিন্দু হিসাবে সংজ্ঞায়িত করা যেতে পারে এবং যা অনুসন্ধান বাক্সের "নীচের বাম" এবং "উপরের ডান" কোণগুলিকে প্রতিনিধিত্ব করে। একটি তুচ্ছ বাস্তবায়ন একটি নোডের সমস্ত এন্ট্রিগুলিকে অতিক্রম করে (রুট নোড থেকে শুরু করে) এবং যদি কোনও এন্ট্রি এটির সাথে মেলে তবে এটি ফলাফলের তালিকায় যোগ করে (যদি এটি ব্যবহারকারীর এন্ট্রি হয়) বা পুনরাবৃত্তভাবে এটি অতিক্রম করে (যদি এটি একটি সাবনোড হয়)। ফাংশন ক্যোয়ারি (নোড, মিনিম, ম্যাক্স, রেজাল্ট _ লিস্ট) হল ফোর্যাচ এন্ট্রি node.get_entries () যদি entry.is_subnode () হয় তাহলে যদি entry.get_prefix ()> = মিনিম এবং entry.get_prefix () <= ম্যাক্স হয় তাহলে কোয়েরি (entry.get_subnode (), মিনিম, ম্যাক্স, রেজাল্ট _ লিস্ট) শেষ হয় যদি অন্যথায় যদি entry.get_key ()> = মিনিম এবং entry.get_key () <= ম্যাক্স হয় তাহলে result_list.add (এন্ট্রি) শেষ হয় যদি শেষ হয় যদি পুনরাবৃত্তি করা হয়। একটি নোডে সমস্ত এন্ট্রি অনুসন্ধান এবং তুলনা করার একটি সময় জটিলতা রয়েছে কারণ-মাত্রিক কী-এর সাথে প্রতিটি তুলনা করতে সময় লাগে। যেহেতু নোডগুলিতে এন্ট্রি পর্যন্ত থাকতে পারে, তাই এটি ক্রমবর্ধমান মাত্রার সাথে ভালভাবে পরিমাপ করে না। হাইপারকিউব ঠিকানা ব্যবহার করে এই পদ্ধতির উন্নতি করার বিভিন্ন উপায় রয়েছে। ন্যূনতম এবং সর্বাধিক ধারণাটি হল চতুর্থাংশের ঠিকানাগুলির জন্য ন্যূনতম এবং সর্বাধিক মানগুলি খুঁজে বের করা যাতে অনুসন্ধানটি এমন কিছু চতুর্থাংশ এড়াতে পারে যা অনুসন্ধান বাক্সের সাথে ওভারল্যাপ করে না। ধরা যাক একটি নোডের কেন্দ্র (এটি নোডের উপসর্গের সমান) এবং প্রতিটি বিট সহ দুটি বিট স্ট্রিং। এছাড়াও, এর সাথে সাবস্ক্রিপ্টটি 's বিট এবং এবং এর' তম মাত্রা নির্দেশ করে। যাক এবং। তারপর প্রতিটি মাত্রার জন্য একটি "রয়েছে যেখানে নোডের" নীচের "অর্ধেক এবং এর সমস্ত চতুর্ভুজ অনুসন্ধান বাক্সের সাথে ওভারল্যাপ করে না। একইভাবে, প্রতিটি মাত্রার জন্য একটি "রয়েছে যেখানে" উপরের "অর্ধেক প্রশ্ন বাক্সের সাথে ওভারল্যাপ করে না। এবং তারপরে একটি নোডে সর্বনিম্ন এবং সর্বোচ্চ উপস্থাপন করুন যা অতিক্রম করা প্রয়োজন। কোয়েরি বাক্সের সাথে চতুর্ভুজগুলি ছেদ করে বা ছেদ করে না। একটি প্রমাণ পাওয়া যায়। এর সাহায্যে, উপরের ক্যোয়ারি ফাংশনটিকে উন্নত করা যেতে পারেঃ ফাংশন ক্যোয়ারি (নোড, মিনিম, ম্যাক্স, রেজাল্ট _ লিস্ট) হল h _ min, h _ min, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h _ m, h একটি নোডে অধিকৃত চতুর্ভুজের বিতরণের উপর নির্ভর করে এই পদ্ধতিটি না থেকে প্রায় সমস্ত মূল তুলনা এড়ানোর অনুমতি দেবে। এটি গড় যাতায়াতের সময় হ্রাস করে তবে ফলস্বরূপ জটিলতা এখনও রয়েছে। কোয়াড্রেন্টগুলি অনুসন্ধান বাক্সের সাথে ওভারল্যাপের জন্য পরীক্ষা করুন এবং এখনও এমন কোয়াড্রেন্ট থাকতে পারে যা অনুসন্ধান বাক্সের সাথে ওভারল্যাপ করে না। ধারণাঃ এবং প্রতিটি মাত্রার জন্য একটি বিট থাকে যা নির্দেশ করে যে প্রশ্ন বাক্সটি সেই মাত্রায় একটি নোডের নীচের/উপরের অর্ধেকের সাথে ওভারল্যাপ করে কিনা। - মাত্রিক কীগুলির তুলনা না করে একটি চতুর্ভুজ অনুসন্ধান বাক্সের সাথে ওভারল্যাপ করে কিনা তা দ্রুত পরীক্ষা করার জন্য এটি ব্যবহার করা যেতে পারেঃ একটি চতুর্থাংশ অনুসন্ধান বাক্সের সাথে ওভারল্যাপ করে যদি প্রতিটি বিটের জন্য একটি সংশ্লিষ্ট বিট থাকে এবং প্রতিটি বিটের জন্য একটি সংশ্লিষ্ট বিট থাকে। 64 বিট রেজিস্টার সহ একটি সিপিইউতে এইভাবে-মাত্রিক কীগুলির ওভারল্যাপ পরীক্ষা করা সম্ভব। ফাংশন হল _ ওভারল্যাপ (এইচ, এইচ _ মিনিট, এইচ _ ম্যাক্স) হল রিটার্ন (এইচ। এইচ _ মিনিট) এবং এইচ _ ম্যাক্স = = এইচ// মূল্যায়ন করে 'সত্য' যদি চতুর্ভুজ এবং প্রশ্ন ওভারল্যাপ হয়। ফাংশন ক্যোয়ারি (নোড, মিনিম, ম্যাক্স, রেজাল্ট _ লিস্ট) হল h _ মিনিট-প্রতিটি এন্ট্রির জন্য h _ ম্যাক্স গণনা করুন node.get_entries_range (h _ মিনিট, h _ ম্যাক্স)-এর জন্য h _ ম্যাক্স গণনা করুন entry.get_h (); যদি (h। h _ মিনিট) & h _ ম্যাক্স = = h হয় তবে// 'সত্য' হিসাবে মূল্যায়ন করা হয় যদি চতুর্ভুজ এবং প্রশ্ন ওভারল্যাপ হয়। [.] শেষ যদি পুনরাবৃত্তি রিটার্ন ফলস্বরূপ সময় জটিলতা পূর্ণ পুনরাবৃত্তির সাথে তুলনা করা হয়। অনুসন্ধান বাক্সের সাথে ওভারল্যাপ হওয়া চতুর্ভুজগুলি অতিক্রম করুন বৃহত্তর নোডের সাথে উচ্চতর মাত্রার জন্য সকলের মধ্য দিয়ে পুনরাবৃত্তি এড়ানো এবং পরিবর্তে প্রশ্ন বাক্সের সাথে ওভারল্যাপ হওয়া পরবর্তী উচ্চতরটি সরাসরি গণনা করা সম্ভব। প্রথম ধাপটি প্রশ্ন বাক্সের সাথে কোনও ওভারল্যাপ নেই এমন সমস্ত চতুর্থাংশের জন্য একটি প্রদত্ত অংশে "-বিট" রাখে। দ্বিতীয় ধাপটি অভিযোজিত এবং যোগ করা বিটগুলিকে বৃদ্ধি করে একটি ওভারফ্লো ট্রিগার করে যাতে নন-ওভারল্যাপিং চতুর্ভুজগুলি বাদ দেওয়া হয়। শেষ ধাপটি ওভারফ্লো ট্রিগার করার জন্য ব্যবহৃত সমস্ত অবাঞ্ছিত বিটগুলি সরিয়ে দেয়। যুক্তিটি বিস্তারিতভাবে বর্ণনা করা হয়েছে। গণনাটি নিম্নরূপ কাজ করেঃ ফাংশন ইনক্রিমেন্ট _ এইচ (এইচ _ ইনপুট, এইচ _ মিনিট, এইচ _ ম্যাক্স) হল এইচ _ আউট = এইচ _ ইনপুট। (~ এইচ _ ম্যাক্স)// প্রি-মাস্ক এইচ _ আউট + = 1// ইনক্রিমেন্ট এইচ _ আউট = (এইচ _ আউট এবং এইচ _ ম্যাক্স)। এইচ _ মিনিট// পোস্ট-মাস্ক রিটার্ন এইচ _ আউট আবার, এর জন্য বেশিরভাগ সিপিইউতে করা যেতে পারে। একটি নোড অতিক্রম করার ফলস্বরূপ সময় জটিলতা হল। এটি সবচেয়ে ভাল কাজ করে যদি অনুসন্ধান বাক্সের সাথে ওভারল্যাপ করা বেশিরভাগ চতুর্ভুজ একটি এন্ট্রি দিয়ে দখল করা থাকে। - নিকটতম প্রতিবেশী নিকটতম প্রতিবেশী অনুসন্ধানগুলি স্ট্যান্ডার্ড অ্যালগরিদম ব্যবহার করে প্রয়োগ করা যেতে পারে। ভাসমান বিন্দু চাবি পিএইচ-ট্রি শুধুমাত্র পূর্ণসংখ্যার মান সংরক্ষণ করতে পারে। ভাসমান বিন্দুর মানগুলি একটি পূর্ণসংখ্যা হিসাবে পূর্ণসংখ্যা হিসাবে সংরক্ষণ করা যেতে পারে। যাইহোক, এর লেখকরা নির্ভুলতা না হারিয়ে একটি পদ্ধতির প্রস্তাবও দিয়েছেন। ক্ষতিহীন রূপান্তর একটি ভাসমান বিন্দুর মানকে কোনও ক্ষতি ছাড়াই একটি পূর্ণসংখ্যায় (এবং পিছনে) রূপান্তরিত করা যদি নির্ভুলতা অর্জন করা যায় তবে ভাসমান বিন্দুর মানের 32 বা 64 বিটকে কেবল একটি পূর্ণসংখ্যা হিসাবে (32 বা 64 বিট সহ) ব্যাখ্যা করে। আই. ই. ই. ই 754 যেভাবে ভাসমান বিন্দুর মানগুলিকে এনকোড করে, তার ফলে প্রাপ্ত পূর্ণসংখ্যার মানগুলির মূল ভাসমান বিন্দুর মানগুলির মতো একই ক্রম থাকে, অন্তত ধনাত্মক মানগুলির জন্য। অ-সাইন বিটগুলি উল্টে দিয়ে নেতিবাচক মানগুলির জন্য অর্ডার করা যেতে পারে। জাভাতে উদাহরণ বাস্তবায়নঃ দীর্ঘ এনকোড (দ্বিগুণ মান) {দীর্ঘ r = Double.doubleToRawLongBits (মান); রিটার্ন (r> = 0)? r: r ^ 0x7FffffffffffffFLFFL;} C + +: std:: int64 _ t এনকোড (দ্বিগুণ মান) {std:: int64 _ t r; memcpy (& r, & মান, সাইজোফ (r)); রিটার্ন r> = 0? r: r ^ 0x7fffffffffffffffffffFFFFL;} এনকোডিং (এবং বিপরীত ডিকোডিং) সমস্ত ভাসমান বিন্দু মানের জন্য ক্ষতিহীন। অর্ডারটি অনুশীলনে এবং সহ ভাল কাজ করে। যাইহোক, পূর্ণসংখ্যার উপস্থাপনাও একটি স্বাভাবিক তুলনীয় মানে পরিণত হয় (অনন্তের চেয়ে ছোট), অসীমগুলি একে অপরের সাথে তুলনীয় এবং তার চেয়ে বড়। এর অর্থ হল, উদাহরণস্বরূপ, একটি অনুসন্ধানের পরিসীমা এর মানের সাথে মেলে না। অনুসন্ধানের পরিসরের সঙ্গে মেলে ধরার জন্য প্রয়োজন। হাইপারবক্স কীগুলি ভলিউমগুলি (অক্ষ-সারিবদ্ধ হাইপার-বক্সগুলি) কী হিসাবে সংরক্ষণ করার জন্য, বাস্তবায়নগুলি সাধারণত কোণের উপস্থাপনা ব্যবহার করে যা একটি বাক্সের দ্বি-মাত্রিক ন্যূনতম এবং সর্বাধিক কোণগুলিকে মাত্রাযুক্ত একক কীতে রূপান্তরিত করে, উদাহরণস্বরূপ সেগুলি ইন্টারলিভ করে। এটি অনুসন্ধান, সন্নিবেশ এবং অপসারণ ক্রিয়াকলাপের জন্য তুচ্ছভাবে কাজ করে। উইন্ডো প্রশ্নগুলিকে-মাত্রিক ভেক্টর থেকে-মাত্রিক ভেক্টর-এ রূপান্তরিত করতে হবে। উদাহরণস্বরূপ, একটি উইন্ডো ক্যোয়ারির জন্য যা সম্পূর্ণরূপে ক্যোয়ারি বাক্সের অভ্যন্তরে থাকা সমস্ত বাক্সের সাথে মেলে, কোয়ারি কীগুলি হলঃ একটি উইন্ডো কোয়ারি অপারেশনের জন্য যা একটি কোয়ারি বাক্সের সাথে ছেদ করা সমস্ত বাক্সের সাথে মেলে, কোয়ারি কীগুলি হলঃ স্কেলাবিলিটি উচ্চ মাত্রায় এন্ট্রির চেয়ে কম, একটি পিএইচ-ট্রি শুধুমাত্র একটি নোড থাকতে পারে, কার্যকরভাবে জেড-অর্ডার বক্ররেখা সহ একটি বি-ট্রি-তে "অবনমিত" হতে পারে। যোগ/অপসারণ/সন্ধানের ক্রিয়াকলাপগুলি রয়ে গেছে এবং উইন্ডো প্রশ্নগুলি চতুর্ভুজ ফিল্টারগুলি ব্যবহার করতে পারে। যাইহোক, এটি মাত্রার অভিশাপ এড়াতে পারে না, কারণ একটি পিএইচ-ট্রি সহ উচ্চ মাত্রার তথ্য সম্পূর্ণ স্ক্যানের চেয়ে সামান্য ভাল। ইউজেস রিসার্চ বড় এবং দ্রুত পরিবর্তনশীল ডেটাসেটের সঙ্গে দ্রুত অ্যাড/রিমুভ/অ্যাক্ট-ম্যাচ ক্রিয়াকলাপের কথা জানিয়েছে। উইন্ডো প্রশ্নগুলি বিশেষত ছোট উইন্ডো বা বড় ডেটাসেটের জন্য ভাল কাজ করে বলে দেখানো হয়েছে পিএইচ-ট্রি মূলত ইন-মেমরি ব্যবহারের জন্য উপযুক্ত। নোডের আকার (এন্ট্রির সংখ্যা) স্থির থাকে এবং স্থায়ী স্টোরেজ ডিস্কে পৃষ্ঠার আকারের সাথে নোডের আকার সারিবদ্ধ করতে কনফিগারযোগ্য নোডের আকারের সূচকগুলি থেকে উপকৃত হয়। আর-ট্রি-র মতো অন্যান্য স্থানিক সূচকগুলির ক্ষেত্রে এটি সহজতর। বাস্তবায়ন জাভাঃ মূল উদ্ভাবক সি + +-এর গিটহাব সংগ্রহস্থলঃ মূল উদ্ভাবক সি + +-এর গিটহাব সংগ্রহস্থলঃ গিটহাব সংগ্রহস্থল সি + +: গিটহাব সংগ্রহস্থল আরও দেখুন বাইনারি স্পেস পার্টিশনিং বাইনারি টাইলিং কে-ডি ট্রি অক্ট্রি কোয়াডট্রি আর-ট্রি ইউবি-ট্রি স্থানিক ডাটাবেস বিস্তারিত বিবরণ, উদাহরণ এবং কর্মক্ষমতা তুলনা সহ পিএইচ-ট্রি ওয়েবসাইটের বাহ্যিক লিঙ্ক রেফারেন্স ট্রি (ডেটা স্ট্রাকচার) ডাটাবেস সূচক কৌশল জ্যামিতিক ডেটা স্ট্রাকচার