Analiza Bloomovog filtra u sustavu za upravljanje bazama podataka PostgreSQL

master's thesis

• Title (english): Bloom filter analysis in the PostgreSQL database management system
• Author: Blaž Solić
• Mentor: Boris Vrdoljak (mentor)
• Committee member: Boris Vrdoljak (predsjednik povjerenstva)
• Committee member: Igor Mekterović (član povjerenstva)
• Committee member: Ljiljana Brkić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2024-07-09, Croatia

Abstract

Rad istražuje i analizira upotrebu Bloomovog filtra kao alternativnog indeksa u sustavu za upravljanje bazama podataka PostgreSQL, uspoređujući ga s klasičnim indeksima temeljenim na B-stablima. Bloomov filtar je vjerojatnosna struktura podataka koja efikasno podržava brzu pretragu podataka, posebno korisnu u situacijama gdje je potrebno smanjiti prostornu potrošnju memorije.

U sklopu rada implementiran je sustav koristeći programske jezike Python i Go, koji integrira Bloomov filtar kao dodatni podatkovni sloj. Analizirana je učinkovitost, složenost i performansa sustava u usporedbi s klasičnim indeksima, istražujući prednosti kao što su brzina pretrage i smanjenje memorije, ali i mane kao što je pojavljivanje lažno pozitivnih rezultata.

Abstract (english)

This paper investigates and analyzes the use of the Bloom filter as an alternative index in the PostgreSQL database management system, comparing it with classic B-tree-based indexes. A Bloom filter is a probabilistic data structure that effectively supports fast data searching, especially useful in situations where it is necessary to reduce spatial memory consumption.

As part of the paper, a system that integrates the Bloom filter as an additional data layer was implemented using the programming languages Python and Go. The efficiency, complexity, and performance of the system compared to classical indexes are analyzed while investigating advantages such as search speed and memory reduction but also disadvantages such as the occurrence of false positives.

• Keywords: Bloomov filtar; PostgreSQL; indeksi; bloom indeks; B-stablo
• Keywords (english): Bloom filter; PostgreSQL; indexes; bloom index; B-tree
• Language: croatian
• URN:NBN: urn:nbn:hr:168:375127
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2024-10-12 22:08:01