Internettillämpningar förlitar sig i allt högre grad på skalbara datastrukturer som måste stödja hög genomströmning och lagra enorma mängder data. Dessa datastrukturer kan vara svåra att genomföra på ett effektivt sätt. De senaste förslagen har övervunnit detta problem genom att överge allmängiltigheten och införa specialiserade gränssnitt och funktioner (t.ex. Dynamo [4]). Vi presenterar utformningen av en mer allmän och flexibel lösning: ett feltolerant och skalbart distribuerat B-träd. Utöver de vanliga B-tree operationer, vår B-tree ger några viktiga praktiska funktioner: transaktioner för atomiskt utföra flera operationer i ett eller flera B-trees, online migration av B-tree noder mellan servrar för lastbalansering, och dynamisk tillägg och borttagning av servrar för att stödja inkrementell tillväxt av systemet. Vår design är konceptuellt enkel. Istället för att använda komplexa konvergens- och låsprotokoll, använder vi distribuerade transaktioner för att göra ändringar i B-tree noder. Vi visar hur man utökar B-trädet och behåller ytterligare information så att dessa transaktioner genomförs snabbt och effektivt. Vår design bygger på en underliggande distribuerad datadelningstjänst, Sinfonia [1], som ger feltolerans och en lätt distribuerad atomisk primitiv. Vi använder denna primitiva för att göra våra transaktioner. Vi implementerade vårt B-träd och visar att det fungerar jämförbart med ett existerande B-träd med öppen källkod och att det skalar till hundratals maskiner. Vi anser att vårt tillvägagångssätt är allmänt och att det lätt kan användas för att genomföra andra distribuerade datastrukturer.
Arbetet i REF presenterade en mer allmän och flexibel indexstruktur: ett feltolerant och skalbart distribuerat B-träd för molnsystem.
A practical scalable distributed B-tree
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}