Belajar Data Structure - Tren Modern 2026 & Concurrent/Persistent DS

#Pendahuluan

Setelah di episode 25 kita memahami memory layout, cache, dan space-time tradeoff, pada episode ini kita melihat tren modern 2026 dan bagaimana data structure ber-evolusi untuk memenuhi kebutuhan era multi-core, AI/ML, dan distributed systems. Fondasi yang kalian pelajari di episode 0-25 tetap relevan — tetapi aplikasi dan implementasinya terus berubah.

Data structure tahun 2026 bukan lagi sekadar array dan tree klasik. Vector database, lock-free concurrent structures, dan immutable/persistent data structures menjadi mainstream. Memahami tren ini memberi kalian keunggulan kompetitif dalam membangun sistem modern.

#Persistent/Immutable Data Structures

#Konsep

Persistent data structure adalah struktur data yang tidak pernah diubah — setiap "perubahan" menghasilkan versi baru. Ini memungkinkan:

• Versioning: akses ke semua versi sebelumnya
• Thread safety: tidak ada race condition karena tidak ada mutasi
• Undo/redo: gratis — semua versi tersedia
• Structural sharing: versi baru berbagi bagian yang tidak berubah dengan versi lama

#Structural Sharing

Structural sharing adalah teknik di mana versi baru dari tree hanya membuat node baru di jalur perubahan, sementara subtree yang tidak berubah di-share dengan versi lama. Ini mengurangi overhead memori secara dramatis.

Structural sharing pada persistent tree

class PersistentNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right
 
def update(node, path, new_value):
    if not path:
        return PersistentNode(new_value)
    if path[0] == 'left':
        return PersistentNode(node.value, update(node.left, path[1:], new_value), node.right)
    else:
        return PersistentNode(node.value, node.left, update(node.right, path[1:], new_value))
 
# Build tree v1
v1 = PersistentNode(1, PersistentNode(2), PersistentNode(3))
 
# Update tanpa mengubah v1
v2 = update(v1, ['left', 'left'], 10)
 
# v1 dan v2 berbagi subtree kanan (node 3)
print(v1.right.value)  # 3
print(v2.right.value)  # 3 (shared)

#Contoh di Production

• Git: setiap commit adalah snapshot tree yang berbagi node dengan commit sebelumnya
• Clojure: semua data structure persistent
• Rust Vec: bisa di-clone dengan structural sharing (meskipun mutable)
• Redux (React): state history untuk undo/redo

#Lock-Free/Concurrent Data Structures

#Masalah: Multi-Thread

Di era multi-core, banyak thread mengakses data structure yang sama secara bersamaan. Lock tradisional (mutex) menciptakan bottleneck — hanya satu thread yang bisa mengakses data structure pada satu waktu.

#Solusi: Lock-Free

Lock-free data structures menggunakan operasi atomik (CAS: Compare-And-Swap) untuk memastikan konsistensi tanpa lock.

#CAS Operation

Conceptual CAS operation

class LockFreeStack:
    def __init__(self):
        self.head = None
 
    def push(self, value):
        node = Node(value)
        while True:
            old_head = self.head
            node.next = old_head
            if CAS(self, 'head', old_head, node):
                break
 
    def pop(self):
        while True:
            old_head = self.head
            if old_head is None:
                return None
            new_head = old_head.next
            if CAS(self, 'head', old_head, new_head):
                return old_head.value

#Contoh Lock-Free Structures

• Concurrent skip list: ordered data structure untuk concurrent access
• Concurrent hash map: Java ConcurrentHashMap, Go sync.Map
• Lock-free queue: Michael-Scott queue
• Atomic operations: Python threading.local(), Go atomic package

#Vector Similarity Search (HNSW, IVF)

#Meningkatnya Kebutuhan AI/ML

Dengan booming AI/ML, vector similarity search menjadi sangat penting. Setiap dokumen, gambar, atau audio bisa di-embed menjadi vector, lalu dicari berdasarkan kemiripan (cosine similarity, Euclidean distance).

#HNSW (Hierarchical Navigable Small World)

HNSW adalah graph-based index yang membangun hierarchy dari graph navigable. Search dimulai dari level paling atas, navigasi ke node terdekat, lalu turun ke level berikutnya.

• Kompleksitas: O(log n) untuk search
• Akurasi: sangat tinggi (recall > 99%)
• Memory: tinggi (menyimpan graph)

#IVF (Inverted File Index)

IVF mempartisi vektor ke dalam cluster menggunakan k-means. Search hanya dilakukan pada cluster terdekat.

• Kompleksitas: O(n/k) di mana k = jumlah cluster
• Akurasi: menengah (recall ~95%)
• Memory: rendah (hanya menyimpan centroids + vectors)

#Perbandingan

#Vector Database

• Pinecone: managed vector database
• Milvus: open-source, distributed
• Weaviate: GraphQL-based
• pgvector: PostgreSQL extension

#DS di Production Systems

#Database Internals

• LSM-Tree + WAL: write-optimized storage (RocksDB, LevelDB)
• B+ Tree index: read-optimized (MySQL InnoDB, PostgreSQL)
• Hash index: point lookup (Redis, Memcached)

#Search Engine

• Inverted index: mapping term → document IDs
• BK-tree: fuzzy string matching
• Trie: autocomplete dan suggestion

#Operating System

• Red-black tree: Linux CFS scheduler
• Radix tree: page cache
• Bitmap: free block tracking

#Praktik: Ilustrasi Structural Sharing

Git-like snapshot dengan structural sharing

class FileNode:
    def __init__(self, name, content=None):
        self.name = name
        self.content = content
        self.children = {}
 
class Snapshot:
    def __init__(self, root=None):
        self.root = root or FileNode("root")
 
    def update_file(self, path, content):
        new_root = FileNode(self.root.name)
        self._copy_tree(self.root, new_root)
        node = new_root
        for part in path[:-1]:
            if part not in node.children:
                node.children[part] = FileNode(part)
            node = node.children[part]
        node.children[path[-1]] = FileNode(path[-1], content)
        return Snapshot(new_root)
 
    def _copy_tree(self, old, new):
        for name, child in old.children.items():
            new_child = FileNode(child.name, child.content)
            new.children[name] = new_child
            self._copy_tree(child, new_child)
 
v1 = Snapshot()
v2 = v1.update_file(["docs", "readme.md"], "# Hello")
v3 = v2.update_file(["docs", "readme.md"], "# Hello World")
 
# v1, v2, v3 semua berdiri sendiri tetapi berbagi data yang tidak berubah

#Penutup

Inti yang harus dibawa pulang:

• Persistent/immutable DS: tidak pernah diubah, semua versi tersedia, structural sharing hemat memori.
• Lock-free DS: CAS operation untuk concurrent access tanpa bottleneck.
• Vector similarity search: HNSW (akurat, tinggi memori) vs IVF (cepat, hemat memori).
• DS di production: LSM-Tree, B+ Tree, inverted index, red-black tree.
• Tren 2026: vector DB (Pinecone, Milvus), concurrent DS, persistent structures.

Di episode 27 selanjutnya (episode terakhir!) kita akan membahas roadmap, karir, dan refleksi akhir — rekap seluruh series, checklist kemampuan, rekomendasi buku dan sumber belajar, serta bagaimana data structure menjadi bahasa universal interview teknis di industri. Selamat datang di babak akhir perjalanan kita!