Evaluating established B⁺-tree access methods in a parallel processing environment

For å kunne fortsette å oppnå stadig større ytelse og gjennomstrømning, benytter datamaskiner i dag et økende antall prosesseringsenheter. Den moderne maskinvarearkitekturen krever horisontal skalerbarhet av applikasjoner og systemer som ønsker å operere mest mulig effektivt. Det å kunne skalere horisontalt innbefatter også evnen til å operere samtidig, og parallelt. Databasehåndteringssystemer (DBMSer) er komplekse systemer med en rik historie, samt en konstant søken etter forbedring på de områdene som muliggjør mest mulig effektiv håndtering av data, og behandling av forespørsler. Med det formålet å forbedre responstiden på den vanlige DBMS oppgaven som går ut på å få tak i poster som tilfredsstiller visse søkebetingelser, opprettes og benyttes supplerende behjelpelige tilgangsstrukturer kalt indekser. B/B⁺-treet er en ofte brukt databaseindeksstruktur. Denne strukturen ble først introdusert i 1970, en tid da de fleste datamaskiner bare hadde en enkelt prosesseringsenhet. Det finnes mange forsøk på å tilpasse og modifisere B/B⁺-treet slik at samspillet blir best mulig i møte med den moderne maskinvarearkitekturen, f.eks. [1]-[5]. Disse forsøkene er varierte både i tilnærming og teknikker benyttet. Denne masteroppgaven gjør sitt eget forsøk på å parallellisere de allerede etablerte tilgangsmetodene til B⁺-treet. Implementasjonen av det parallelle B⁺-treet som presenteres opprettholdes i minnet, benytter “thread pool” designmønsteret, og støtter batchprosessering av operasjoner gruppert etter type, så vel som enkeltoperasjoner. Dessuten kan Bloom-filtre valgfritt benyttes og essensielle variabler, som den øvre grensen av en nodes antall barn, antall tråder, og antall vanlige B⁺-tree, konfigureres. Resultatene som ble oppnådd på bakgrunn av å sammenligne ytelsen til den parallelle implementasjonen av B⁺-treet, og grunnlinjen etablert av det vanlige B⁺-treet som kun benytter en enkelt tråd, viser at beslutningen om å velge å utnytte tilgjengelig parallell prosesseringskapabilitet, bare vil være verdt det dersom graden av parallellitet er tilstrekkelig, og kostnaden indusert av oppgaveoppretting og håndtering blir ubetydelig sammenlignet med oppgaveutførelsestiden. Dette motiverer bruken av parallell batchprosessering og bruk av nytte-kostnadsanalyse for å beslutte når parallell utførelse skal foretas