Η παρούσα εργασία εξετάζει τεχνικές σχεδίασης και υλοποίησης δομών δεικτοδότησης σε NoSQL βάσεις δεδομένων, με έμφαση στα Log-Structured Merge Trees (LSM trees). Τα LSM trees χρησιμοποιούνται ευρέως σε σύγχρονα συστήματα αποθήκευσης, καθώς ευνοούν την υψηλή απόδοση στις εγγραφές μέσω προσωρινής αποθήκευσης στη μνήμη, περιοδικής μεταφοράς των δεδομένων σε αμετάβλητα αρχεία και συμπύκνωσης των αρχείων σε διαδοχικά επίπεδα.
Στο θεωρητικό μέρος παρουσιάζονται οι βασικές αρχές λειτουργίας των LSM δέντρων, οι σχεδιαστικοί συμβιβασμοί ως προς το κόστος ανάγνωσης, το κόστος εγγραφής και τη χρήση μνήμης, καθώς και τεχνικές που χρησιμοποιούνται για τη βελτίωση των αναζητήσεων, όπως τα φίλτρα Bloom, οι δείκτες οριοθέτησης και οι πολιτικές συμπύκνωσης. Παράλληλα, εξετάζονται αντιπροσωπευτικά παραγωγικά και ερευνητικά συστήματα που αξιοποιούν ή επεκτείνουν την αρχιτεκτονική των LSM δέντρων.
Στο πρακτικό μέρος σχεδιάστηκε και υλοποιήθηκε σε Python ένα πειραματικό key-value store εκπαιδευτικού χαρακτήρα. Στόχος της υλοποίησης είναι η απομόνωση των βασικών μηχανισμών ενός συστήματος αποθήκευσης που βασίζεται σε LSM δέντρα, ώστε να διερευνηθεί πώς διαφορετικές σχεδιαστικές επιλογές επηρεάζουν τη συμπεριφορά του συστήματος σε ελεγχόμενο περιβάλλον. Η υλοποίηση επιτρέπει τη μελέτη της συμπύκνωσης, της οργάνωσης των SSTables και της προαιρετικής χρήσης βοηθητικών δομών αναζήτησης, όπως τα φίλτρα Bloom και οι δείκτες οριοθέτησης.
Η αξιολόγηση πραγματοποιήθηκε με συνθετικούς φόρτους εργασίας (workloads) διαφορετικών χαρακτηριστικών, με σκοπό να εξεταστεί η επίδραση των πολιτικών συμπύκνωσης και των βοηθητικών δομών αναζήτησης στην απόδοση. Τα αποτελέσματα επιβεβαιώνουν ότι τα φίλτρα Bloom και οι δείκτες οριοθέτησης μειώνουν σημαντικά το κόστος ανάγνωσης και βελτιώνουν τη ρυθμαπόδοση, ιδιαίτερα όταν χρησιμοποιούνται συνδυαστικά. Συνολικά, η εργασία αναδεικνύει πώς οι επιμέρους επιλογές σχεδίασης αλληλεπιδρούν με τα χαρακτηριστικά του φόρτου εργασίας και οδηγούν σε διαφορετική πειραματική συμπεριφορά.

This thesis focuses on the design and implementation of indexing techniques for NoSQL storage systems, with particular emphasis on Log-Structured Merge Trees (LSM trees). LSM trees are a widely used storage architecture in modern key-value and NoSQL systems, especially in write-intensive environments, because they buffer updates in memory and later persist them as immutable sorted files that are reorganized through compaction.
The first part of the thesis introduces the structure and operation of LSM trees and discusses the main trade-offs involved in their design. Particular attention is given to the cost of reads, the cost of writes, memory usage, and the techniques used to balance them. These include Bloom filters, fence pointers, range filters, and compaction strategies such as tiering and leveling. The thesis also reviews representative production systems and recent research approaches that rely on or extend the LSM-tree model.
The second part presents the design and implementation of a small experimental key-value store in Python. The system is intended as an educational prototype that isolates the main mechanisms of an LSM-based storage engine in a controlled setting. It supports basic key-value operations, SSTable creation, tiering and leveling compaction, and optional lookup optimizations through Bloom filters and fence pointers.
The prototype is evaluated using synthetic workloads with different access patterns, including write-heavy, read-heavy, negative-lookup, and skewed-access scenarios. The results show that auxiliary lookup structures, especially when Bloom filters and fence pointers are combined, substantially reduce read cost and improve throughput. More broadly, the experiments illustrate how different design options affect the behavior of an LSM-based system under different workload conditions.