Comparing memeory-based data structures to conventional relational databases in terms of speed, memory usage, concurrency capabilities and simplicity of implementation

Abstract

Diplomityössä tutkitaan Movila Detection -nimisen päätelaitetunnistusohjelmiston sisäisen päätelaitetietokannan tietorakenteen suunnittelun ongelmaa. Movila Detection on päätelaitetunnistusohjelmisto, joka toimii web-palvelimen liitännäisenä. Web-palvelimella, johon liitännäinen on asennettu, mobiilit päätelaitteet kuten matkapuhelimet ja PDAt ja niiden ominaisuudet voidaan tunnistaa vaikuttamatta kuitenkaan merkittävästi web-palvelimen suorituskykyyn. Movila Detection on myös Movila Oy:n päätuote.

Tyypillisiä ja laajalti käytettyjä tietorakenteita on kolmesta eri kategoriasta. Kategoriat ovat puurakenteet, trie-rakenteet ja hajarakenteet. Myös kolme eri relaatiotietokantaa käydään läpi. Tietorakenteiden toteutus kerrotaan lyhyesti ja tietorakenteet ja relaatiotietokannat evaluoidaan pääasiassa nopeuden, muistin käytön ja rinnakkaisajo-ominaisuuksien perusteella. Myös joitakin tietorakenteita Java APlsta käytetään referenssinä. Tietorakenteiden ja -kantojen testaus tehdään todellisessa ympäristössä todellisella datalla, joka on kerätty yhtiön ylläpitämistä web-sivuista.

Testejä on 5 eri tyyppiä: hakutesti, osa-avainhakutesti, lisäystesti, muistinkulutustesti ja rinnakkaisuustesti. Puurakenteet, trie-rakenteet ja hajarakenteet kaikki tarjosivat hyvän suorituskyvyn hauissa. Trie-rakenteet suoriutuivat hyvin kaikissa testeissä, koska ne tukevat merkkijonoarvoisia avaimia natiivisti. Relaatiotietokannat olivat pääasiassa hitaita. Java APIsta referenssiksi otetut tietorakenteet olivat yleensä parhaiten suoriutuvien rakenteiden joukossa testeissä.