Vi föreslår en version av cache omedvetna sökträd som är enklare än tidigare förslag av Bender, Demaine och Farach-Colton och har samma komplexitet gränser, i synnerhet, vår datastruktur undviker användning av viktbalanserade B-träd, och kan implementeras som bara en uppsättning dataelement, utan användning av pekare. Strukturen förbättrar också utnyttjandet av utrymme. För lagring av n-element använder vårt förslag (1 + e)n gånger elementstorleken på minnet, och utför sökningar i värsta fall O(log B n)-minnesöverföringar, uppdateringar i avkortade O(log 2 n)/eB)-minnesöverföringar och avståndsförfrågningar i värsta fall O(log B n + k/B)-minnesöverföringar, där k är storleken på utmatningen. Den grundläggande idén med vår datastruktur är att upprätthålla ett dynamiskt binärt träd av höjdlogg n-l-O(1) med hjälp av befintliga metoder, bädda in detta träd i ett statiskt binärt träd, som i sin tur är inbäddat i en matris i en cache omedvetna mode, med van Emde Boas layout av Prokop. Vi undersöker också det praktiska i att cache omedvetna i området sökträd, genom att tillhandahålla en empirisk jämförelse av olika metoder för att lägga ut ett sökträd i minnet.
Icke desto mindre, i REF, index inbäddar hela PMA, efter ett binärt träd i van Emde Boas layout.
Cache oblivious search trees via binary trees of small height
{'venue': "SODA '02", 'journal': None, 'mag_field_of_study': ['Computer Science']}