System för datahantering i minnesformat, t.ex. värdekedjor, har blivit en viktig infrastruktur i dagens stora databehandling och molntjänster. De förlitar sig på effektiva indexstrukturer för att få tillgång till data. Medan oordnade index, såsom hash tabeller, kan utföra punkt sökning med O(1) tid, kan de inte användas i många scenarier där intervall frågor måste stödjas. Många beställda index, såsom B+ träd och hoppa över listan, har en O (log N ) uppslagningskostnad, där N är antal nycklar i ett index. För en beställd index värd miljarder nycklar, kan det ta mer än 30 nyckel-jämförare i en uppslagning, vilket är en storleksordning som är dyrare än den på en hash tabell. Med tillgång till stort minne och snabbt nätverk i dagens datacenter, denna O (log N ) tid tar en tung avgift på program som förlitar sig på beställda index. I detta papper introducerar vi en ny ordnad indexstruktur, som heter Wormhole, som tar O(log L) värsta fall tid för att slå upp en nyckel med en längd av L. Den låga kostnaden uppnås genom att samtidigt utnyttja styrkor av tre indexstrukturer, nämligen hash bord, prefix träd, och B+ träd, för att orkestrera ett enda snabbbeställd index. Maskhålets räckvidd kan utföras genom en linjär scanning av en lista efter en första uppslagning. Denna förbättring av tillgänglighetseffektiviteten sker inte till ett pris av nedsatt rymdeffektivitet. Istället är Wormholes indexutrymme jämförbart med B+-trädets och skip-listans. Experimentella resultat visar att Wormhole outperforms hoppa lista, B+ träd, ART, och Masstree med upp till 8.4×, 4.9×, 4.3×, och 6,6× i termer av nyckel uppslagning genomströmning, respektive.
Maskhål REF är en variant av B-träd som ersätter B-trädets inre noder med en hashtabell kodad trie.
Wormhole: A Fast Ordered Index for In-memory Data Management
{'venue': "EuroSys '19", 'journal': None, 'mag_field_of_study': ['Computer Science']}