PH-tree
પીએચ-ટ્રી એ એક વૃક્ષ માહિતી માળખું છે જેનો ઉપયોગ ભૌગોલિક કોઓર્ડિનેટ્સ, બિંદુઓ, લક્ષણ વેક્ટર, લંબચોરસ અથવા બાઉન્ડિંગ બોક્સ જેવા બહુ-પરિમાણીય માહિતી (કી) ના અવકાશી અનુક્રમણિકા માટે થાય છે. પીએચ-ટ્રી એ સ્પેસ પાર્ટીશનિંગ ઇન્ડેક્સ છે જેની રચના ક્વાડટ્રી અથવા ઓક્ટ્રી જેવી જ હોય છે. જો કે, ક્વાડટ્રીઝથી વિપરીત, તે ટ્રીઝ પર આધારિત વિભાજન નીતિનો ઉપયોગ કરે છે અને ક્રિટ બીટ ટ્રીઝ જેવી જ છે જે કીઓની બીટ-રજૂઆત પર આધારિત છે. બીટ-આધારિત વિભાજન નીતિ, જ્યારે નોડ્સ માટે વિવિધ આંતરિક રજૂઆતોના ઉપયોગ સાથે જોડાય છે, ત્યારે ઉચ્ચ-પરિમાણીય ડેટા સાથે માપનીયતા પ્રદાન કરે છે. બીટ-પ્રતિનિધિત્વ વિભાજન નીતિ પણ મહત્તમ ઊંડાઈ લાદે છે, આમ અધોગતિ પામેલા વૃક્ષો અને પુનર્સંતુલનની જરૂરિયાતને ટાળે છે. ઝાંખી મૂળભૂત PH-વૃક્ષ એ એક અવકાશી અનુક્રમણિકા છે જે વપરાશકર્તા નિર્ધારિત મૂલ્યો માટે કીઓને મેપ કરે છે, જે પૂર્ણાંકો સાથે-પરિમાણીય વેક્ટર છે. પી. એચ. વૃક્ષ એ ક્રિટ બીટ વૃક્ષનું બહુ-પરિમાણીય સામાન્યીકરણ છે, એ અર્થમાં કે ક્રિટ બીટ વૃક્ષ એ-પરિમાણીય કીઓ સાથે પી. એચ. વૃક્ષની સમકક્ષ છે. ક્રિટ બીટ વૃક્ષની જેમ, અને મોટાભાગના અન્ય અવકાશી અનુક્રમણિકાઓથી વિપરીત, પીએચ-વૃક્ષ એ મલ્ટીમેપને બદલે નકશો છે. એ-ડાયમેન્શનલ પીએચ-ટ્રી એ નોડ્સનું એક વૃક્ષ છે જ્યાં દરેક નોડ પાર્ટીશનો તેને ચતુર્થાંશમાં વિભાજિત કરીને જગ્યા આપે છે (ઉચ્ચ પરિમાણીય ડેટા સાથે સંભવિત મોટા નોડ્સ કેવી રીતે સ્કેલ કરે છે તે માટે નીચે જુઓ). દરેક ચતુર્થાંશમાં મહત્તમ એક એન્ટ્રી હોય છે, ક્યાં તો કી-વેલ્યુ જોડી (પર્ણ ચતુર્થાંશ) અથવા કી-સબનોડ જોડી. કી-સબનોડની જોડી માટે, કી સબનોડના કેન્દ્રને રજૂ કરે છે. કી એ સબનોડ અને તેના ચાઈલ્ડ સબનોડ્સમાં તમામ કીનો સામાન્ય ઉપસર્ગ (બીટ-રજૂઆત) પણ છે. દરેક નોડમાં ઓછામાં ઓછી બે એન્ટ્રીઓ હોય છે, અન્યથા તે પેરેન્ટ નોડ સાથે મર્જ થઈ જાય છે. પી. એચ. વૃક્ષોના કેટલાક અન્ય માળખાકીય ગુણધર્મો આ પ્રમાણે છેઃ તેઓ-એરી વૃક્ષો છે. તેઓ સ્વાભાવિક રીતે અસંતુલિત છે પરંતુ અસંતુલન મર્યાદિત છે કારણ કે તેમની ઊંડાઈ કીઓની થોડી પહોળાઈ સુધી મર્યાદિત છે, દા. ત. 32 બીટ પૂર્ણાંકો સાથે-પરિમાણીય કી માટે 32. દાખલ કરવા અથવા દૂર કરવાની કામગીરીઓ બરાબર એક નોડને સંશોધિત કરે છે અને સંભવિત રીતે બીજા નોડને ઉમેરવા અથવા દૂર કરવા માટેનું કારણ બને છે. આ સહવર્તી અમલીકરણ માટે ઉપયોગી થઈ શકે છે. આનો અર્થ એ પણ છે કે ફેરફાર ખર્ચમાં થોડો તફાવત છે. તેમની રચના નિવેશ/દૂર કરવાના ક્રમથી સ્વતંત્ર છે. વિભાજન વ્યૂહરચના મોટાભાગના ક્વાડટ્રીની જેમ જ, પીએચ-ટ્રી એ નોડ્સનો એક પદાનુક્રમ છે જ્યાં દરેક નોડ તમામ પરિમાણોમાં જગ્યાને વિભાજિત કરે છે. આમ, નોડમાં દરેક ચતુર્થાંશ માટે એક સબનોડ હોઈ શકે છે. ચતુર્ભુજ ક્રમાંકન PH-વૃક્ષ વૃક્ષમાં તેમની સ્થિતિ નક્કી કરવા માટે બહુ-પરિમાણીય કીઓના બિટ્સનો ઉપયોગ કરે છે. સમાન અગ્રણી બિટ્સ ધરાવતી તમામ કીઓ વૃક્ષની એક જ શાખામાં સંગ્રહિત થાય છે. ઉદાહરણ તરીકે, સ્તર પરના નોડમાં, ચતુર્થાંશ નક્કી કરવા માટે કે જ્યાં કી દાખલ કરવી જોઈએ (અથવા દૂર કરવી અથવા ઉપર જોવી જોઈએ), તે કીના દરેક પરિમાણના 's' બીટને જુએ છે. 8 ચતુર્થાંશ (સમઘનની રચના) સાથે 3D નોડ માટે કીના પ્રથમ પરિમાણનો 's' બીટ નક્કી કરે છે કે લક્ષ્ય ચતુર્થાંશ સમઘનની ડાબી કે જમણી બાજુએ છે કે કેમ, બીજા પરિમાણનો 's' બીટ નક્કી કરે છે કે તે આગળ કે પાછળ છે, અને ત્રીજા પરિમાણનો 's' બીટ નીચે વિરુદ્ધ ટોચ નક્કી કરે છે, ચિત્ર જુઓ. 1D ઉદાહરણ 8 બીટ મૂલ્યો સાથે ત્રણ 1D કીઓ સાથેનું ઉદાહરણ છેઃ, અને. ખાલી વૃક્ષમાં અને તેમાં ઉમેરવાથી એક જ નોડમાં પરિણમે છે. બે કીઓ પ્રથમ તેમના છઠ્ઠા બીટમાં અલગ પડે છે તેથી નોડનું સ્તર (0 થી શરૂ કરીને) હોય છે. નોડમાં 5 બીટ ઉપસર્ગ છે જે બંને કીઓના સામાન્ય 5 બિટ્સનું પ્રતિનિધિત્વ કરે છે. નોડમાં બે ચતુર્થાંશ હોય છે, દરેક કી એક ચતુર્થાંશમાં સંગ્રહિત થાય છે. ત્રીજા કીને ઉમેરવાથી એક વધારાના નોડમાં પરિણામ મળે છે, જેમાં એક ચતુર્થાંશમાં મૂળ નોડ સબનોડ તરીકે હોય છે અને બીજો ચતુર્થાંશ નવી કી ધરાવે છે. 2D ઉદાહરણ 2D કીઓ સાથે દરેક નોડમાં ચતુર્થાંશ હોય છે. ચતુર્થાંશની સ્થિતિ જ્યાં કી સંગ્રહિત કરવામાં આવે છે તે કીઓના સંબંધિત બિટ્સમાંથી કાઢવામાં આવે છે, દરેક પરિમાણમાંથી એક બીટ. નોડના ચાર ચતુર્થાંશ 2D હાયપરક્યુબ બનાવે છે (ચતુર્થાંશ ખાલી હોઈ શકે છે). કીઓમાંથી કાઢવામાં આવેલા બિટ્સ માટે અને માટે હાયપરક્યુબ સરનામું બનાવે છે. તે અસરકારક રીતે નોડના હાયપરક્યુબમાં ચતુર્થાંશની સ્થિતિ છે. નોડ માળખું નોડમાં એન્ટ્રીઓનો ક્રમ હંમેશા ઝેડ-ક્રમને અનુસરે છે. નોડમાં એન્ટ્રીઓ, ઉદાહરણ તરીકે, કદના નિશ્ચિત કદના એરેમાં સંગ્રહિત કરી શકાય છે. તે પછી અસરકારક રીતે ચતુર્થાંશની એરે અનુક્રમણિકા છે. આ શોધવાની, દાખલ કરવાની અને દૂર કરવાની મંજૂરી આપે છે અને તેને સંગ્રહિત કરવાની જરૂર નથી. અવકાશ જટિલતા જોકે નોડ દીઠ છે, તેથી તે ઉચ્ચ પરિમાણીય માહિતી માટે ઓછી યોગ્ય છે. બીજો ઉકેલ એ છે કે ક્રમબદ્ધ સંગ્રહમાં એન્ટ્રીઓ સંગ્રહિત કરવી, જેમ કે ગતિશીલ એરે અને/અથવા બી-વૃક્ષો. આ લુકઅપ કામગીરીને ધીમી કરે છે પરંતુ મેમરીનો વપરાશ ઘટાડે છે. જે ઓછી મેમરીનો ઉપયોગ કરે છે તેના આધારે ફિક્સ્ડ અને ડાયનેમિક એરે રજૂઆત વચ્ચે સ્વિચ કરીને ન્યૂનતમ મેમરી વપરાશ માટે મૂળ અમલીકરણનો હેતુ છે. અન્ય અમલીકરણ ગતિશીલ રીતે બદલાતા નથી પરંતુ ઉચ્ચ પરિમાણીય ડેટા માટે ગતિશીલ એરે અને બી-ટ્રી માટે નિશ્ચિત એરેનો ઉપયોગ કરે છે. ઓપરેશન લુકઅપ, નિવેશ અને દૂર કરવાની કામગીરીઓ બધા ખૂબ સમાન રીતે કામ કરે છેઃ સાચો નોડ શોધો, પછી નોડ પર કામગીરી કરો. વિન્ડો ક્વેરીઝ અને-નજીકના-પડોશી શોધો વધુ જટિલ છે. લુકઅપ ઓપરેશન નક્કી કરે છે કે વૃક્ષમાં ચાવી અસ્તિત્વમાં છે કે નહીં. તે વૃક્ષની નીચે ચાલે છે અને દરેક નોડને તપાસે છે કે તેમાં ઉમેદવાર સબનોડ છે કે વપરાશકર્તા મૂલ્ય કે જે કી સાથે મેળ ખાય છે. ફંક્શન લુકઅપ (કી) એ એન્ટ્રી છે-ગેટ _ રૂટ _ એન્ટ્રી ()// જો વૃક્ષ ખાલી ન હોય તો રુટ એન્ટ્રીમાં રૂટ નોડ હોય છે જ્યારે એન્ટ્રી! = NIL & & & entry.is_subnode () નોડ કરો-entry.get_node () એન્ટ્રી-node.get_entry (કી) રીપીટ રીટર્ન એન્ટ્રી// એન્ટ્રી NIL ફંક્શન હોઈ શકે છે-ગેટ _ એન્ટ્રી (કી) એ નોડ છે-વર્તમાન નોડ-એચ-એક્સટ્રેક્ટ _ બિટ્સ _ એટ _ ડેપ્થ (કી, node.get_depth ()) એન્ટ્રી-node.get_entry_at (એચ) રીટર્ન એન્ટ્રી// એન્ટ્રી-NIL દાખલ કરી શકાય છે. ઓપરેશન લુકઅપ ફંક્શનની જેમ વૃક્ષને પાર કરે છે અને પછી કીને નોડમાં દાખલ કરે છે. ધ્યાનમાં લેવા માટે ઘણા કિસ્સાઓ છેઃ ચતુર્થાંશ ખાલી છે અને આપણે ફક્ત ચતુર્થાંશમાં નવી એન્ટ્રી દાખલ કરી શકીએ છીએ અને પાછા આવી શકીએ છીએ. ચતુર્થાંશમાં એક કી સાથે વપરાશકર્તા એન્ટ્રી છે જે નવી એન્ટ્રી જેવી જ છે. આવી અથડામણનો સામનો કરવાની એક રીત એ છે કે ધ્વજ પરત કરવો જે નિષ્ફળ નિવેશ સૂચવે છે. જો વૃક્ષને નોડની એન્ટ્રી તરીકે સંગ્રહ સાથે મલ્ટી-મેપ તરીકે લાગુ કરવામાં આવે, તો તે સંગ્રહમાં નવું મૂલ્ય ઉમેરવામાં આવે છે. ચતુર્થાંશમાં એક અલગ કી સાથે એન્ટ્રી (વપરાશકર્તા એન્ટ્રી અથવા સબનોડ એન્ટ્રી) હોય છે. આ કિસ્સામાં હાલની એન્ટ્રીને નવા સબનોડ સાથે બદલવાની જરૂર છે જે જૂની અને નવી એન્ટ્રી ધરાવે છે. ફંક્શન ઇન્સર્ટ (નોડ, કી, વેલ્યુ) લેવલ છે node.get_level ()// લેવલ એ 0 છે રુટ માટે node.get_level ()/(કી, લેવલ) એન્ટ્રી માટે node.get_entry (એચ) જો એન્ટ્રી = = NIL તો// કેસ 1. એન્ટ્રી _ ન્યૂ> ક્રિએટ _ એન્ટ્રી (કી, વેલ્યુ) node.set_entry (એચ, એન્ટ્રી _ ન્યૂ) નહીં તો! entry.is_subnode () & & entry.get_key () = = કી તો// કેસ 2. અથડામણ, ત્યાં પહેલેથી જ એક એન્ટ્રી રીટર્ન છે, જો રીટર્ન રીમૂવ રીમૂવલ દાખલ કરવા માટે ઊલટું કામ કરે છે, તો વધારાની મર્યાદા સાથે, જો બેથી ઓછી એન્ટ્રીઓ રહે તો કોઈપણ સબનોડને દૂર કરવો પડે છે. બાકીની એન્ટ્રી પેરેન્ટ નોડ પર ખસેડવામાં આવે છે. વિન્ડો ક્વેરીઝ વિન્ડોઝ ક્વેરીઝ એ એવા ક્વેરીઝ છે જે લંબચોરસ અક્ષ-સંરેખિત હાયપરબોક્સની અંદર આવેલી તમામ કીઓ પરત કરે છે. તેમને દ્વિ-પરિમાણીય બિંદુઓ તરીકે વ્યાખ્યાયિત કરી શકાય છે અને જે ક્વેરી બોક્સના "નીચલા ડાબા" અને "ઉપલા જમણા" ખૂણાઓનું પ્રતિનિધિત્વ કરે છે. તુચ્છ અમલીકરણ નોડની તમામ એન્ટ્રીઓને પાર કરે છે (રુટ નોડથી શરૂ કરીને) અને જો એન્ટ્રી તેની સાથે મેળ ખાય તો તે કાં તો તેને પરિણામ સૂચિમાં ઉમેરે છે (જો તે વપરાશકર્તા એન્ટ્રી હોય તો) અથવા તેને પુનરાવર્તિત રીતે પસાર કરે છે (જો તે સબનોડ હોય તો). ફંક્શન ક્વેરી (નોડ, મિનિમ, મેક્સ, રિઝલ્ટ લિસ્ટ) એ ફોરચ એન્ટ્રી છે જો entry.is_subnode () હોય તો પછી જો entry.get_prefix ()> = મિનિમ અને entry.get_prefix () <= મેક્સિમ હોય તો ક્વેરી (entry.get_subnode (), મિનિમ, મેક્સિમ, રિઝલ્ટ લિસ્ટ) સમાપ્ત થાય છે જો અન્યથા જો entry.get_key ()> = મિનિમ અને entry.get_key () <= મેક્સિમ તો result_list.add (એન્ટ્રી) સમાપ્ત થાય છે જો સમાપ્ત થાય છે જો પુનરાવર્તન વળતર ક્વેરી સમયની જટિલતાનો સચોટ અંદાજ કાઢવા માટે વિશ્લેષણમાં પરિમાણીયતા શામેલ કરવાની જરૂર છે. નોડમાં તમામ એન્ટ્રીઓને પાર કરવા અને તેની સરખામણી કરવા માટે સમયની જટિલતા હોય છે કારણ કે-પરિમાણીય કીની દરેક સરખામણીમાં સમય લાગે છે. નોડ્સમાં એન્ટ્રીઓ હોઈ શકે છે, તેથી આ વધતી પરિમાણીયતા સાથે સારી રીતે માપવામાં આવતું નથી. હાયપરક્યુબ સરનામાનો ઉપયોગ કરીને આ અભિગમને કેવી રીતે સુધારી શકાય તેની વિવિધ રીતો છે. લઘુતમ અને મહત્તમ ચતુર્થાંશના સરનામાંઓ માટે લઘુતમ અને મહત્તમ મૂલ્યો શોધવાનો વિચાર છે જેથી શોધ ક્વેરી બોક્સ સાથે ઓવરલેપ ન થાય તેવા કેટલાક ચતુર્થાંશને ટાળી શકે. ચાલો નોડનું કેન્દ્ર હોઈએ (આ નોડના ઉપસર્ગની બરાબર છે) અને દરેક બિટ્સ સાથે બે બીટ સ્ટ્રિંગ્સ હોઈએ. ઉપરાંત, 's' અને 'અને' ના 'th' પરિમાણને સૂચવતી સબસ્ક્રિપ્ટને પણ દર્શાવવા દો. દો અને. પછી દરેક પરિમાણ માટે "હોય છે જ્યાં નોડનો" નીચલો "અડધો ભાગ અને તેમાંના તમામ ચતુર્થાંશ ક્વેરી બોક્સ સાથે ઓવરલેપ થતા નથી. તેવી જ રીતે, દરેક પરિમાણ માટે એક "છે જ્યાં" ઉપલા "અડધા ક્વેરી બોક્સ સાથે ઓવરલેપ થતું નથી. અને પછી નોડમાં સૌથી નીચો અને સૌથી ઊંચો પ્રસ્તુત કરો જેને પાર કરવાની જરૂર છે. ક્વેરી બોક્સ સાથે અથવા તેને છેદતા ન હોય તેવા ચતુર્થાંશ. તેનો પુરાવો ઉપલબ્ધ છે. આ સાથે, ઉપરોક્ત ક્વેરી કાર્યને સુધારી શકાય છેઃ કાર્ય ક્વેરી (નોડ, લઘુત્તમ, મહત્તમ, પરિણામ _ સૂચિ) એ h _ min છે | | | | | | | | | | | | | | | | | | | | | | | | | નોડમાં કબજા હેઠળના ચતુર્થાંશના વિતરણના આધારે આ અભિગમ ના થી લઈને લગભગ તમામ મુખ્ય સરખામણીઓ સુધી ગમે ત્યાં ટાળવાની મંજૂરી આપશે. આ સરેરાશ મુસાફરીના સમયને ઘટાડે છે પરંતુ પરિણામી જટિલતા હજુ પણ છે. ક્વેરી બોક્સ સાથે ઓવરલેપ માટે ક્વાડ્રન્ટ્સ તપાસો અને ત્યાં હજુ પણ એવા ક્વાડ્રન્ટ્સ હોઈ શકે છે જે ક્વેરી બોક્સ સાથે ઓવરલેપ થતા નથી. વિચારઃ અને દરેકમાં દરેક પરિમાણો માટે એક બીટ હોય છે જે સૂચવે છે કે ક્વેરી બોક્સ તે પરિમાણમાં નોડના નીચલા/ઉપલા અડધા સાથે ઓવરલેપ થાય છે કે કેમ. આનો ઉપયોગ-પરિમાણીય કીઓની તુલના કર્યા વિના ક્વેરી બોક્સ સાથે ચતુર્થાંશ ઓવરલેપ થાય છે કે કેમ તે ઝડપથી તપાસવા માટે થઈ શકે છેઃ ક્વેરી બોક્સ સાથે ચતુર્થાંશ ઓવરલેપ થાય છે જો તેમાંના દરેક 'બીટ' માટે અનુરૂપ 'બીટ ઇન' હોય અને દરેક 'બીટ' માટે અનુરૂપ 'બીટ ઇન' હોય. 64 બીટ રજિસ્ટરવાળા CPU પર આમ-પરિમાણીય કીઓ સુધી ઓવરલેપ થાય છે કે કેમ તે તપાસવું શક્ય છે. વિધેય છે _ ઓવરલેપ (એચ, એચ _ મિનિટ, એચ _ મેક્સ) એ વળતર (એચ | એચ _ મિનિટ) છે અને જો ચતુર્થાંશ અને ક્વેરી ઓવરલેપ થાય તો એચ _ મેક્સ = = એચ// નું મૂલ્યાંકન 'સાચું' થાય છે. ફંક્શન ક્વેરી (નોડ, મિનિમ, મેક્સ, રિઝલ્ટ લિસ્ટ) એ h _ min છે કે દરેક એન્ટ્રી માટે h _ mx ની ગણતરી કરો node.get_entries_range (h _ મિનિટ, h _ mx) માટે h _ mx ની ગણતરી કરો entry.get_h (); જો (h | h _ મિનિટ) & h _ mx = = h તો// જો ચતુર્થાંશ અને ક્વેરી ઓવરલેપ થાય તો 'સાચું' નું મૂલ્યાંકન કરે છે. [.] અંત જો પુનરાવર્તન વળતર પરિણામી સમયની જટિલતાની સરખામણી સંપૂર્ણ પુનરાવર્તન સાથે કરવામાં આવે છે. મોટા નોડ્સ સાથેના ઉચ્ચ પરિમાણો માટે બધા દ્વારા પુનરાવર્તન કરવાનું ટાળવું પણ શક્ય છે અને તેના બદલે ક્વેરી બોક્સ સાથે ઓવરલેપ થતા આગામી ઉચ્ચની સીધી ગણતરી કરો. પ્રથમ પગલું ક્વેરી બોક્સ સાથે કોઈ ઓવરલેપ ન હોય તેવા તમામ ચતુર્થાંશ માટે આપેલ "-બિટ્સ" મૂકે છે. બીજું પગલું અનુકૂલિત અને ઉમેરાયેલા "-બિટ્સ" માં વધારો કરે છે જે ઓવરફ્લોને ટ્રિગર કરે છે જેથી બિન-ઓવરલેપિંગ ચતુર્થાંશને છોડવામાં આવે. છેલ્લું પગલું ઓવરફ્લોને ટ્રિગર કરવા માટે ઉપયોગમાં લેવાતા તમામ અનિચ્છનીય બિટ્સને દૂર કરે છે. તર્કનું વિગતવાર વર્ણન કરવામાં આવ્યું છે. ગણતરી નીચે પ્રમાણે કામ કરે છેઃ કાર્ય વૃદ્ધિ _ એચ (એચ _ ઇનપુટ, એચ _ મિનિટ, એચ _ મેક્સ) એ એચ _ આઉટ = એચ _ ઇનપુટ | (~ એચ _ મેક્સ)// પૂર્વ-માસ્ક એચ _ આઉટ + = 1// વૃદ્ધિ એચ _ આઉટ = (એચ _ આઉટ અને એચ _ મેક્સ) | એચ _ મિનિટ// પોસ્ટ-માસ્ક રીટર્ન એચ _ આઉટ ફરીથી, આ માટે મોટાભાગના સીપીયુ પર કરી શકાય છે. નોડને પાર કરવા માટે પરિણામી સમય જટિલતા છે. આ શ્રેષ્ઠ રીતે કામ કરે છે જો ક્વેરી બોક્સ સાથે ઓવરલેપ થતા મોટાભાગના ચતુર્થાંશ એન્ટ્રી સાથે જોડાયેલા હોય. - નજીકના પડોશીઓની નજીકની પડોશી શોધોને પ્રમાણભૂત અલ્ગોરિધમ્સનો ઉપયોગ કરીને અમલમાં મૂકી શકાય છે. ફ્લોટિંગ પોઇન્ટ કીઓ PH-વૃક્ષ માત્ર પૂર્ણાંક મૂલ્યોને સંગ્રહિત કરી શકે છે. ફ્લોટિંગ પોઇન્ટ મૂલ્યોને તેમને પૂર્ણાંક આપતા પૂર્ણાંકો તરીકે સંગ્રહિત કરી શકાય છે. જો કે, લેખકો ચોકસાઇ ગુમાવ્યા વિના અભિગમની દરખાસ્ત પણ કરે છે. ફ્લોટિંગ પોઇન્ટ મૂલ્યના 32 અથવા 64 બિટ્સને ફક્ત પૂર્ણાંક તરીકે (32 અથવા 64 બિટ્સ સાથે) અર્થઘટન કરીને ફ્લોટિંગ પોઇન્ટ મૂલ્યને નુકસાન વિના પૂર્ણાંક મૂલ્ય (અને પાછળ) માં નુકસાન વિનાનું રૂપાંતર કરી શકાય છે. IEEE 754 જે રીતે ફ્લોટિંગ પોઇન્ટ મૂલ્યોને એન્કોડ કરે છે તેના કારણે, પરિણામી પૂર્ણાંક મૂલ્યો ઓછામાં ઓછા હકારાત્મક મૂલ્યો માટે મૂળ ફ્લોટિંગ પોઇન્ટ મૂલ્યો જેવા જ ક્રમ ધરાવે છે. નકારાત્મક મૂલ્યો માટે ઓર્ડર બિન-સાઇન બિટ્સને ઊંધી કરીને પ્રાપ્ત કરી શકાય છે. જાવામાં ઉદાહરણ અમલીકરણઃ લાંબા એન્કોડ (ડબલ મૂલ્ય) {લાંબા r = Double.doubleToRawLongBits (મૂલ્ય); વળતર (r> = 0)? r: r ^ 0x7fffffffffffffffLFFL;} C + + માં ઉદાહરણ અમલીકરણઃ std:: int64 _ t એન્કોડ (ડબલ વેલ્યુ) {std:: int64 _ t r; memcpy (& r, & વેલ્યુ, સાઈઝઓફ (r)); રીટર્ન r> = 0? r: r ^ 0x7fffffffffffffffffffLFFL;} એન્કોડિંગ (અને ઇન્વર્સ ડીકોડિંગ) તમામ ફ્લોટિંગ પોઇન્ટ મૂલ્યો માટે લોસલેસ છે. ઓર્ડર વ્યવહારમાં સારી રીતે કામ કરે છે, જેમાં અને સામેલ છે. જો કે, પૂર્ણાંક પ્રતિનિધિત્વ પણ સામાન્ય તુલનાત્મક મૂલ્ય (અનંત કરતાં નાનું) માં ફેરવાય છે, અનંતતા એકબીજા સાથે તુલનાત્મક હોય છે અને તેના કરતા મોટી હોય છે. તેનો અર્થ એ કે, ઉદાહરણ તરીકે, ક્વેરી શ્રેણી ની કિંમત સાથે મેળ ખાતી નથી. ક્વેરી શ્રેણી સાથે મેળ કરવા માટે હોવી જરૂરી છે. હાયપરબોક્સ કીઓ વોલ્યુમ (અક્ષ-સંરેખિત હાયપર-બોક્સ) ને કી તરીકે સંગ્રહિત કરવા માટે, અમલીકરણ સામાન્ય રીતે ખૂણાના પ્રતિનિધિત્વનો ઉપયોગ કરે છે જે બૉક્સના દ્વિ-પરિમાણીય લઘુત્તમ અને મહત્તમ ખૂણાઓને પરિમાણો સાથે એક જ કીમાં રૂપાંતરિત કરે છે, ઉદાહરણ તરીકે તેમને એકબીજા સાથે જોડીનેઃ આ સર્ચઅપ, ઇન્સર્ટ અને દૂર કરવાની કામગીરી માટે તુચ્છ રીતે કામ કરે છે. વિન્ડો ક્વેરીઝને-ડાયમેન્શનલ વેક્ટરમાંથી-ડાયમેન્શનલ વેક્ટરમાં રૂપાંતરિત કરવાની જરૂર છે. ઉદાહરણ તરીકે, વિન્ડો ક્વેરી માટે કે જે ક્વેરી બોક્સની અંદરના તમામ બોક્સ સાથે સંપૂર્ણપણે મેળ ખાય છે, ક્વેરી કીઓ છેઃ વિન્ડો ક્વેરી ઓપરેશન માટે કે જે ક્વેરી બોક્સ સાથે આંતરછેદ કરતા તમામ બોક્સ સાથે મેળ ખાય છે, ક્વેરી કીઓ છેઃ માપનીયતા એન્ટ્રીઓ કરતાં ઓછા ઉચ્ચ પરિમાણોમાં, પીએચ-ટ્રીમાં માત્ર એક જ નોડ હોઈ શકે છે, જે અસરકારક રીતે ઝેડ-ઓર્ડર વળાંક સાથે બી-ટ્રીમાં "અધોગતિ" કરે છે. ઉમેરો/દૂર કરો/શોધ કામગીરી બાકી છે અને વિન્ડો ક્વેરીઓ ચતુર્થાંશ ફિલ્ટર્સનો ઉપયોગ કરી શકે છે. જો કે, આ પરિમાણીયતાના શાપને ટાળી શકતું નથી, કારણ કે ઉચ્ચ પરિમાણીય માહિતી અથવા પી. એચ.-વૃક્ષ સંપૂર્ણ સ્કેન કરતાં સહેજ વધુ સારી છે. યુઝ રિસર્ચે મોટા અને ઝડપથી બદલાતા ડેટાસેટ્સ સાથે ઝડપી ઉમેરો/દૂર કરો/ચોક્કસ-મેળ ખાતી કામગીરીની જાણ કરી છે. વિન્ડો ક્વેરીઝ ખાસ કરીને નાની બારીઓ અથવા મોટા ડેટાસેટ માટે સારી રીતે કામ કરતી હોવાનું દર્શાવવામાં આવ્યું છે. પીએચ-ટ્રી મુખ્યત્વે મેમરીમાં ઉપયોગ માટે યોગ્ય છે. નોડ્સનું કદ (એન્ટ્રીઓની સંખ્યા) નિશ્ચિત હોય છે જ્યારે ડિસ્ક પર પૃષ્ઠના કદ સાથે નોડના કદને સંરેખિત કરવા માટે રૂપરેખાંકિત કરી શકાય તેવા નોડના કદ સાથેના અનુક્રમણિકાઓથી સતત સંગ્રહને ફાયદો થાય છે. આર-વૃક્ષો જેવા અન્ય અવકાશી અનુક્રમણિકાઓ સાથે આ સરળ છે. અમલીકરણ જાવાઃ મૂળ શોધક C + + દ્વારા GitHub રીપોઝીટરીઃ મૂળ શોધક C + + દ્વારા GitHub રીપોઝીટરીઃ GitHub રીપોઝીટરી C + +: GitHub રીપોઝીટરી બાયનરી સ્પેસ પાર્ટીશનિંગ બાયનરી ટાઇલિંગ k-d ટ્રી ઓક્ટ્રી ક્વાડટ્રી R-ટ્રી UB-ટ્રી અવકાશી ડેટાબેઝ બાહ્ય લિંક્સ PH-ટ્રી વેબસાઇટ વિગતવાર વર્ણન, ઉદાહરણો અને કામગીરીની સરખામણી સાથે સંદર્ભો વૃક્ષો (ડેટા સ્ટ્રક્ચર્સ) ડેટાબેઝ અનુક્રમણિકા તકનીકો ભૌમિતિક ડેટા સ્ટ્રક્ચર્સ