Bx-tree
કોમ્પ્યુટર વિજ્ઞાનમાં, Bx વૃક્ષ એ એક ક્વેરી છે જેનો ઉપયોગ ગતિશીલ પદાર્થો માટે કાર્યક્ષમ B + વૃક્ષ-આધારિત અનુક્રમણિકા માળખાને અપડેટ કરવા માટે થાય છે. અનુક્રમણિકા માળખું Bx-વૃક્ષનું મૂળ માળખું એ B + વૃક્ષ છે જેમાં આંતરિક નોડ્સ ડિરેક્ટરી તરીકે કામ કરે છે, જેમાં દરેક તેના જમણા ભાઈ-બહેન માટે નિર્દેશક ધરાવે છે. બીએક્સ-ટ્રીના અગાઉના સંસ્કરણમાં, લીફ નોડ્સમાં મૂવિંગ-ઓબ્જેક્ટ સ્થાનો અનુક્રમિત અને અનુરૂપ અનુક્રમણિકા સમય હોય છે. ઓપ્ટિમાઇઝ્ડ વર્ઝનમાં, દરેક લીફ નોડ એન્ટ્રીમાં આઈડી, વેગ, એક-પરિમાણીય મેપિંગ મૂલ્ય અને ઓબ્જેક્ટનો નવીનતમ અપડેટ સમય હોય છે. ફરતી વસ્તુઓના સ્થાનોનો સંગ્રહ ન કરીને ફેનઆઉટમાં વધારો થાય છે, કારણ કે આ મેપિંગ મૂલ્યોમાંથી મેળવી શકાય છે. ગતિશીલ પદાર્થો માટે B + વૃક્ષનો ઉપયોગ અન્ય ઘણી ગતિશીલ પદાર્થોની અનુક્રમણિકાઓ માટે, દ્વિ-પરિમાણીય ગતિશીલ પદાર્થને O = ((x, y), (vx, vy), t) તરીકે રેખીય કાર્ય તરીકે મોડેલિંગ કરવામાં આવે છે, જ્યાં (x, y) અને (vx, vy) આપેલ સમયના ઉદાહરણ t પર પદાર્થનું સ્થાન અને વેગ છે, એટલે કે છેલ્લા અપડેટનો સમય. બી + વૃક્ષ એ એક-પરિમાણીય માહિતીને અનુક્રમિત કરવા માટેનું માળખું છે. B + વૃક્ષને ગતિશીલ પદાર્થ અનુક્રમણિકા તરીકે અપનાવવા માટે, Bx-વૃક્ષ એક રેખીય તકનીકનો ઉપયોગ કરે છે જે સમય t પર પદાર્થોના સ્થાનને એક પરિમાણીય મૂલ્યમાં એકીકૃત કરવામાં મદદ કરે છે. ખાસ કરીને, ઓબ્જેક્ટ્સને પહેલા તેમના અપડેટ સમય અનુસાર પાર્ટીશન કરવામાં આવે છે. સમાન પાર્ટીશનની અંદરની વસ્તુઓ માટે, Bx-વૃક્ષ આપેલ સમયે તેમના સ્થાનોનો સંગ્રહ કરે છે જેનો અંદાજ રેખીય પ્રક્ષેપણ દ્વારા કરવામાં આવે છે. આમ કરવાથી, બીએક્સ-ટ્રી દરેક ઓબ્જેક્ટના અપડેટ સમયને સંગ્રહિત કર્યા વિના સમાન પાર્ટીશનની અંદર તમામ ઓબ્જેક્ટનું સુસંગત દૃશ્ય રાખે છે. બીજું, જગ્યા ગ્રીડ દ્વારા વિભાજિત કરવામાં આવે છે અને ઑબ્જેક્ટનું સ્થાન જગ્યા ભરવાના વળાંક અનુસાર પાર્ટીશનોની અંદર રેખીય બને છે, દા. ત., પીનો અથવા હિલ્બર્ટ વળાંક. છેવટે, પાર્ટીશન નંબર (સમયની માહિતી) અને રેખીય ક્રમ (સ્થાનની માહિતી) ના સંયોજન સાથે, ઑબ્જેક્ટને એક-પરિમાણીય અનુક્રમણિકા કી Bx મૂલ્ય સાથે Bx-વૃક્ષમાં અનુક્રમિત કરવામાં આવે છેઃ અહીં અનુક્રમણિકા-વિભાજન એ અપડેટ સમય દ્વારા નિર્ધારિત અનુક્રમણિકા વિભાજન છે અને xrep એ અનુક્રમિત સમયે ઑબ્જેક્ટ સ્થિતિનું જગ્યા ભરવાનું વળાંક મૂલ્ય છે, જે x નું દ્વિસંગી મૂલ્ય સૂચવે છે, અને "+" એટલે જોડાણ. ઑબ્જેક્ટ O ((7,2), (-0.1,0.05), 10), tmu = 120 આપવામાં આવે તો, O માટે Bx મૂલ્ય નીચે પ્રમાણે ગણી શકાય. ઉલ્લેખ કર્યો છે તેમ O એ પાર્ટીશન 0 માં અનુક્રમિત થયેલ છે. તેથી, અનુક્રમણિકા વિભાજન = (00) 2. પાર્ટીશન 0 ના લેબલ ટાઇમસ્ટેમ્પ પર O ની સ્થિતિ (1,5) છે. ક્રમ = 3 સાથે ઝેડ-વળાંકનો ઉપયોગ કરીને, ઓનું ઝેડ-મૂલ્ય એટલે કે xrep એ (090011) 2 છે. અનુક્રમણિકા વિભાજન અને એક્સ. આર. પી. ને સંયોજિત કરતા, બી. એક્સ. વેલ્યુ (00010011) 2 = 19. ઉદાહરણ O ((0,6), (0.2,-0.3), 10) અને tmu = 120 પછી પાર્ટીશનના લેબલ ટાઇમસ્ટેમ્પ પર O ની સ્થિતિઃ? ??? દાખલ કરવું, અપડેટ કરવું અને કાઢી નાખવું નવી વસ્તુને જોતાં, તેની અનુક્રમણિકા કીની ગણતરી કરવામાં આવે છે અને પછી વસ્તુને B + વૃક્ષની જેમ Bx-વૃક્ષમાં દાખલ કરવામાં આવે છે. અપડેટમાં કાઢી નાંખવા પછી દાખલ કરવાનો સમાવેશ થાય છે. દરેક અનુક્રમણિકાની નવીનતમ કી રાખવા માટે સહાયક માળખાનો ઉપયોગ કરવામાં આવે છે જેથી કીની શોધ કરીને ઑબ્જેક્ટને કાઢી શકાય. વૃક્ષને અસર કરતા પહેલા અનુક્રમણિકા કીની ગણતરી કરવામાં આવે છે. આ રીતે, Bx-વૃક્ષ સીધા B + વૃક્ષના સારા ગુણધર્મોને વારસામાં મેળવે છે, અને કાર્યક્ષમ સુધારા પ્રદર્શન પ્રાપ્ત કરે છે. ક્વેરીઝ રેન્જ ક્વેરી એ બધી વસ્તુઓને પુનઃપ્રાપ્ત કરે છે જેનું સ્થાન વર્તમાન સમય પહેલાં નહીં પણ સમયે લંબચોરસ શ્રેણીમાં આવે છે. બીએક્સ-ટ્રી પ્રશ્નોના જવાબ આપવા માટે ક્વેરી-વિન્ડો એન્લાર્જમેન્ટ તકનીકનો ઉપયોગ કરે છે. બીએક્સ-ટ્રી ઑબ્જેક્ટના સ્થાનને તેના અપડેટ સમય પછી થોડા સમય માટે સંગ્રહિત કરે છે, તેથી વિસ્તરણમાં બે કિસ્સાઓનો સમાવેશ થાય છેઃ સ્થાનને કાં તો અગાઉના સમયે પાછું લાવવું જોઈએ અથવા પછીના સમયે આગળ વધારવું જોઈએ. મુખ્ય વિચાર ક્વેરી વિંડોને મોટું કરવાનો છે જેથી તે તમામ ઓબ્જેક્ટ્સને ઘેરી લે કે જેમની સ્થિતિ તેના લેબલ ટાઇમસ્ટેમ્પ પર ક્વેરી વિંડોની અંદર ન હોય પરંતુ ક્વેરી ટાઇમસ્ટેમ્પ પર ક્વેરી વિંડો દાખલ કરશે. વિસ્તરણ પછી, વિસ્તૃત ક્વેરી વિંડોમાં આવતી વસ્તુઓને શોધવા માટે Bx-વૃક્ષના પાર્ટીશનોને પાર કરવાની જરૂર છે. દરેક પાર્ટીશનમાં, જગ્યા ભરવાના વળાંકનો ઉપયોગ કરવાનો અર્થ એ છે કે મૂળ, દ્વિ-પરિમાણીય જગ્યામાં શ્રેણી ક્વેરી રૂપાંતરિત, એક-પરિમાણીય જગ્યામાં શ્રેણી ક્વેરીનો સમૂહ બની જાય છે. તિરાડ ડેટાસેટ્સમાં વિસ્તરણ પછી વધુ પડતા મોટા ક્વેરી ક્ષેત્રને ટાળવા માટે, ક્વેરી અલ્ગોરિધમનું ઓપ્ટિમાઇઝેશન અસ્તિત્વમાં છે, જે બિનજરૂરી ક્વેરી વિસ્તરણને ટાળીને ક્વેરી કાર્યક્ષમતામાં સુધારો કરે છે. K ની નજીકની પાડોશી ક્વેરી K ની નજીકની પડોશી ક્વેરીની ગણતરી, જ્યાં સુધી k જવાબો પ્રાપ્ત ન થાય ત્યાં સુધી શ્રેણી ક્વેરીઓ પુનરાવર્તિત રીતે વિસ્તૃત શોધ ક્ષેત્ર સાથે કરીને કરવામાં આવે છે. બીજી શક્યતા એ છે કે આઇડિસ્ટન્સ ટેકનીકમાં સમાન ક્વેરીંગ વિચારોનો ઉપયોગ કરવો. અન્ય પ્રશ્નો શ્રેણી ક્વેરી અને K નજીકના પડોશી ક્વેરી અલ્ગોરિધમ્સને અંતરાલ ક્વેરીઓ, સતત ક્વેરીઓ વગેરેને ટેકો આપવા માટે સરળતાથી વિસ્તૃત કરી શકાય છે. Bx-વૃક્ષ એ B + વૃક્ષ અનુક્રમણિકાની ટોચ પર બનેલો અનુક્રમણિકા હોવાથી, દાખલ કરવા, કાઢી નાખવા અને શોધ સહિત Bx-વૃક્ષની તમામ કામગીરીઓ B + વૃક્ષની જેમ જ હોય છે. આ કામગીરીઓના અમલીકરણમાં ફેરફાર કરવાની જરૂર નથી. એકમાત્ર તફાવત એ છે કે વર્તમાન DBMSમાં સંગ્રહિત પ્રક્રિયા તરીકે અનુક્રમણિકા કી મેળવવાની પ્રક્રિયાનો અમલ કરવો. તેથી, બીએક્સ-ટ્રીને કર્નલને સ્પર્શ કર્યા વિના હાલના ડીબીએમએસમાં સરળતાથી એકીકૃત કરી શકાય છે. સ્પેડ એ લોકપ્રિય રીલેશ્નલ ડેટાબેઝ સિસ્ટમ માયએસક્યુએલની ટોચ પર બનેલી મૂવિંગ ઓબ્જેક્ટ મેનેજમેન્ટ સિસ્ટમ છે, જે ઓબ્જેક્ટ્સને અનુક્રમિત કરવા માટે બીએક્સ-ટ્રીનો ઉપયોગ કરે છે. અમલીકરણમાં, મૂવિંગ ઓબ્જેક્ટ ડેટાને રૂપાંતરિત કરવામાં આવે છે અને સીધા જ માયએસક્યુએલ પર સંગ્રહિત કરવામાં આવે છે, અને ક્વેરીઓને પ્રમાણભૂત એસક્યુએલ સ્ટેટમેન્ટમાં રૂપાંતરિત કરવામાં આવે છે જે રિલેશનલ એન્જિનમાં અસરકારક રીતે પ્રક્રિયા કરવામાં આવે છે. સૌથી અગત્યનું, આ બધું માયએસક્યુએલ કોરમાં ઘૂસણખોરી કર્યા વિના સરસ રીતે અને સ્વતંત્ર રીતે પ્રાપ્ત થાય છે. ડેટા સ્ક્યુ સાથે પ્રદર્શન ટ્યુનિંગ સંભવિત સમસ્યા Bx વૃક્ષ એક-પરિમાણીય કીમાં દ્વિ-પરિમાણીય સ્થાનનું મેપિંગ કરતી વખતે જગ્યા વિભાજન માટે ગ્રીડનો ઉપયોગ કરે છે. આ સ્ક્યુડ ડેટા સાથે વ્યવહાર કરતી વખતે ક્વેરી અને અપડેટ કામગીરી બંનેમાં પ્રદર્શનમાં ઘટાડો લાવી શકે છે. જો ગ્રીડ કોષ મોટું હોય, તો કોષમાં ઘણી વસ્તુઓ સમાયેલી હોય છે. કોષની વસ્તુઓ અનુક્રમણિકાથી અલગ પડી શકતી નથી, તેથી અંતર્ગત B + વૃક્ષમાં કેટલાક ઓવરફ્લો નોડ્સ હશે. ઓવરફ્લો પૃષ્ઠોનું અસ્તિત્વ માત્ર વૃક્ષના સંતુલનને જ નષ્ટ કરતું નથી પણ સુધારા ખર્ચમાં પણ વધારો કરે છે. પ્રશ્નોની વાત કરીએ તો, આપેલ ક્વેરી ક્ષેત્ર માટે, મોટા કોષમાં વધુ ફોલ્સ પોઝિટિવ આવે છે અને પ્રક્રિયાનો સમય વધે છે. બીજી બાજુ, જો જગ્યા વધુ સારી ગ્રીડ સાથે વિભાજિત કરવામાં આવે છે, એટલે કે. નાના કોષો, દરેક કોષમાં થોડા પદાર્થો હોય છે. ત્યાં ભાગ્યે જ ઓવરફ્લો પૃષ્ઠો હોય છે જેથી અપડેટનો ખર્ચ ઓછો થાય. ક્વેરીમાં ઓછા ખોટા હકારાત્મક મેળવવામાં આવે છે. જોકે, વધુ કોષોની શોધ કરવાની જરૂર છે. શોધાયેલ કોષોની સંખ્યામાં વધારો પણ ક્વેરીનું કામનું ભારણ વધારે છે. ઇન્ડેક્સ ટ્યુનિંગ ST2B-ટ્રી અવકાશમાં ડેટા સ્ક્યુ અને સમય સાથે ડેટા ફેરફાર સાથે વ્યવહાર કરતી વખતે Bx-ટ્રીની કામગીરીને ટ્યુનિંગ કરવા માટે સ્વ-ટ્યુનિંગ માળખું રજૂ કરે છે. અવકાશમાં ડેટા સ્ક્યુ સાથે વ્યવહાર કરવા માટે, ST2B-વૃક્ષ સંદર્ભ બિંદુઓના સમૂહનો ઉપયોગ કરીને સમગ્ર જગ્યાને વિવિધ પદાર્થ ઘનતાના પ્રદેશોમાં વિભાજિત કરે છે. દરેક પ્રદેશ એક વ્યક્તિગત ગ્રીડનો ઉપયોગ કરે છે, જેના કોષનું કદ તેની અંદરની વસ્તુની ઘનતા દ્વારા નક્કી થાય છે. Bx-વૃક્ષમાં વિવિધ સમય અંતરાલોને લગતા બહુવિધ પાર્ટીશનો હોય છે. જેમ જેમ સમય પસાર થતો જાય છે તેમ તેમ દરેક પાર્ટીશન વધતું જાય છે અને વારાફરતી સંકોચાય છે. ST2B-વૃક્ષ આ સુવિધાનો ઉપયોગ અનુક્રમણિકાને ઑનલાઇન ટ્યુન કરવા માટે કરે છે જેથી સમય સાથે ડેટા ફેરફારોને સમાવવા માટે જગ્યા પાર્ટીશનિંગને સમાયોજિત કરી શકાય. ખાસ કરીને, જેમ જેમ પાર્ટીશન સંકોચાય છે અને ખાલી થવા લાગે છે અને વધવા લાગે છે, તે નવીનતમ ડેટા ઘનતા અનુસાર દરેક સંદર્ભ બિંદુ માટે સંદર્ભ બિંદુઓનો નવો સમૂહ અને નવી ગ્રીડ પસંદ કરે છે. ટ્યુનિંગ આપેલ સમયગાળા દરમિયાન એકત્રિત કરવામાં આવેલા તાજેતરના આંકડાઓ પર આધારિત છે, જેથી જગ્યા પાર્ટીશનિંગની રીત નવીનતમ ડેટા વિતરણમાં શ્રેષ્ઠ રીતે બંધબેસતું હોવાનું માનવામાં આવે છે. આ રીતે, ST2B-વૃક્ષ અવકાશમાં ડેટા સ્ક્યુ અને સમય સાથે ડેટા ફેરફારોને કારણે થતી અસરને ઘટાડવાની અપેક્ષા રાખે છે. બી + વૃક્ષ હિલ્બર્ટ વળાંક ઝેડ-ક્રમ (વળાંક) સંદર્ભો બી-વૃક્ષ પણ જુઓ.