🌐 Canlı tanıtım sitesi: https://toxpox.github.io/CardCatalog/ · kaynak:
docs/
Bir kütüphane otomasyon sisteminin çekirdek veri yönetim birimi. 1.000.000 kitap kaydı üzerinde title / author / category sorgularını mikrosaniye mertebesinde yanıtlar, tam CRUD destekler, ~28 MB RAM kullanır ve ikili snapshot ile ~6 ms içinde yeniden başlar.
İndeks omurgası bitmap ters indeks; depolama kolonsal ve dictionary-encoded.
Harici bağımlılık yok: C++20 STL + POSIX mmap (Windows'ta düz-okuma fallback).
CLI'daki RSS/RAM ölçümü Linux'a özgü /proc/self/status üzerinden yapılır.
| Katman | Seçim |
|---|---|
| Depolama | kolonsal SoA + u8 dictionary kod (3 B kod + 2 B yıl / kayıt) |
| Birincil indeks (id) | örtük: offset = id-1 (id hiç saklanmaz) |
| İkincil indeks | her alan değeri için yoğun word-wise bitmap (~152 bitmap) |
| Bileşik sorgu | bitmap'lerin word-wise AND'i (AVX2'ye vektörlenir) |
| Sayım (count) | tombstone yokken önbellekli kardinalite → O(1); silme sonrası deleted bitmap'i düşülür |
| Title prefix | sıralı başlık sözlüğü (binary search) + bitmap OR |
| Silme | tek "deleted" bitmap (tombstone, ANDNOT) |
| Yükleme | mmap/düz-okuma + iki geçişli ayrıştırma; büyük yüklerde çok-threadli |
| Kalıcılık | ikili snapshot (kolon + sözlük; bitmap yüklemede kurulur) |
İndeks seçimi neden bitmap? Alan kardinalitesi çok düşük (78/59/15) ve sonuç
kümeleri büyük (bir kategori ~66K kayıt) → bu, klasik bitmap ters indeks senaryosu;
kesişim/birleşim word-wise AND/OR ile mikrosaniyede çözülür. ID'ler 1…N ardışık
olduğundan id'yi hiç saklamayıp offset = id-1 kullanıyoruz.
Veri seti (books_dataset.txt) bu klasörün bir üstünde beklenir.
make # -O3 -march=native -flto -pthread (bitmap döngüleri AVX2'ye vektörlenir)
make demo # yükle + sorgular + CRUD + snapshot turu
make bench # 10K / 100K / 1M ölçeklerinde zaman + RAM + sorgu
make repl # interaktif kabuk (prefix dahil)
make test # dogrulama testleri (Unix'te /tmp altinda fixture uretir)CMake ile: cmake -B build -DCMAKE_BUILD_TYPE=Release && cmake --build build && (cd build && ctest)
Not: Linux ve macOS'ta veri dosyası mmap ile okunur. Windows derlemelerinde aynı yükleme yolu
std::ifstream tabanlı düz-okuma fallback kullanır; CLI çıktısındaki "mmap" etiketi bu durumda
teknik olarak fallback okuma yolunu temsil eder. RAM/RSS satırı Linux dışı platformlarda anlamlı
olmayabilir.
get <id> title <deger> author <deger> category <deger> prefix <baslangic>
and <baslik> | <yazar> | <kategori> insert <baslik>|<yazar>|<kategori>|<yil>
update <id>|<baslik>|<yazar>|<kategori>|<yil> delete <id> compact save <dosya> stats
| Ölçü | 10K | 100K | 1M |
|---|---|---|---|
| Yükleme (mmap+paralel+indeks) | 4.0 ms | 5.3 ms | 41 ms |
| RAM (RSS toplam) | 4.7 MB | 6.9 MB | 28 MB |
| İndeks+kolon (yalnız) | 0.23 MB | 2.3 MB | 23 MB |
get_by_id |
0.047 µs | 0.024 µs | 0.025 µs |
count (önbellekli, O(1)) |
0.033 µs | 0.026 µs | 0.024 µs |
query_category |
0.16 µs | 0.44 µs | 5.0 µs |
query_author |
0.20 µs | 0.60 µs | 5.0 µs |
| compound (word-wise AND) | 0.29 µs | 0.93 µs | 8.8 µs |
| prefix "The" (358K sonuç) | 1.1 µs | 9.4 µs | 90 µs |
| snapshot kaydet / yükle | — | — | 1.2 ms / 6.3 ms |
include/bitmap.hpp yoğun word-wise bitmap (AND/OR/ANDNOT/popcount/iter)
include/engine.hpp SoA + sözlük + bitmap + CRUD + snapshot arayüzü
src/engine.cpp mmap/düz-okuma yükleme, kodlama, indeks, CRUD, snapshot
src/main.cpp CLI: demo / bench / repl + RAM ölçümü
Makefile · CMakeLists.txt