Abstract-Main minne kapacitet har vuxit upp till en punkt där de flesta databaser passar in i RAM. För databassystem i huvudminnet är indexstrukturens prestanda en kritisk flaskhals. Traditionella in-minne datastrukturer som balanserade binära sökträd är inte effektiva på modern hårdvara, eftersom de inte optimalt utnyttja on-CPU caches. Hash tabeller, som ofta används för huvudminne index, är snabba men bara stöd punkt frågor. För att övervinna dessa brister presenterar vi ART, ett adaptivt radixträd (trie) för effektiv indexering i huvudminnet. Dess uppslagsprestanda överträffar högt avstämda, läsbara sökträd, samtidigt som den stöder mycket effektiva tillägg och raderingar också. Samtidigt är ART mycket utrymme effektiv och löser problemet med överdriven värsta fall rymdförbrukning, som plågar de flesta radix träd, genom att adaptivt välja kompakta och effektiva datastrukturer för interna noder. Även om ART:s prestanda är jämförbar med hashtabeller, upprätthåller den datan i sorterad ordning, vilket möjliggör ytterligare operationer som områdesskanning och prefixlookup.
Adaptive Radix Tree (ART) index föreslogs först i REF.
The adaptive radix tree: ARTful indexing for main-memory databases
{'venue': '2013 IEEE 29th International Conference on Data Engineering (ICDE)', 'journal': '2013 IEEE 29th International Conference on Data Engineering (ICDE)', 'mag_field_of_study': ['Computer Science']}