Toplu Dizinleme Eniyilemesi

Önceki ders bölünme sürerken gelen 600 kaydı tek tek saydı ve iki şeyi sessizce varsaydı: her kayıt ayrı bir istektir ve kabul edilir edilmez aranabilir. İkisi de ölçülmemişti. Bir katalog partisi yığın hâlinde gelir; 600 kaydı 600 istekle göndermekle 12 istekle göndermek aynı şey değildir. Dizine giren belgenin aranabilir hâle gelmesi de anlık değildir: belge önce bir tampona yazılır ve ancak bir yenileme işlemi tamponu bir bölüte çevirdiğinde sorgulara görünür. Bu ders iki ayarı ayrı ölçer — parti boyu ve yenileme aralığı.

Düzenek

Bölüt, bir tampon dolusu belgeden oluşan değişmez bir ters dizindir; yeni belge var olan bir bölüte eklenmez, yeni bir bölüt doğar. Bir sorgu bütün bölütlere bakmak zorundadır: her bölütte terim başına bir sözlük araması yapar ve gönderi listelerini okur. Puanlama istatistiği bütün bölütlerden toplandığı için bölüt sayısı sırayı değil maliyeti değiştirir; sıra üzerindeki tek etki görünürlükten gelir.

Süre de ölçülüyor ama ham süre basılmıyor: süre ortama bağlıdır ve süreç içi model ağ taşımadığı için istek başına düşen ağ maliyetini ölçemez. Basılan şey bir eşiğin üstünde olup olmadığıdır; yükü taşıyan sayılar istek, bölüt, bayt ve sözlük aramasıdır.

AK7 — 600 kayıtlık bağış partisi kataloğa 50’lik isteklerle girer ve her istekten hemen sonra aynı sorgu koşar. Doğrusal etkilidir: istek boyu değişirse görünmeyen belge sayısı aynı yönde değişir. AK8 — yenileme arka planda her aralık belgede bir çalışır ve tamponu tek bir bölüte çevirir. Tamponda bekleyen belge sorguya görünmez; bu, modelin kuralıdır.

// kume/derlem.mjs — kutuphane katalogu derlemi ve ters dizin (onceki derslerle ayni uretec ve
// ayni tohum). dizinle() burada TEK BIR BOLUT kurar: bir bolut, bir tampon dolusu belgeden
// olusan degismez bir ters dizindir.
const ORTAK = ["kitap", "yazar", "eser", "metin", "bolum", "baski", "sayfa", "dil", "cilt", "yayin"];
const OZEL = {
  cocuk: ["masal", "resimli", "okul", "oyun", "hayvan", "cizgi"], oyku: ["kisa", "anlati", "derleme", "gunluk", "yalnizlik", "kasaba"],
  roman: ["kahraman", "kent", "kusak", "ev", "yolculuk", "mektup"], tarih: ["imparatorluk", "belge", "arsiv", "savas", "yuzyil", "vakayiname"],
  gezi: ["deniz", "yol", "harita", "sehir", "liman", "gemi"], siir: ["dize", "olcu", "imge", "ses", "sessizlik", "kafiye"],
  deneme: ["dusunce", "elestiri", "okuma", "zaman", "not", "soylesi"], bilim: ["olcum", "deney", "kuram", "veri", "gozlem", "denklem"],
};
const NADIR = ["fener", "kuyu", "ipek", "kule", "bahce", "kar", "ada", "koru", "tas", "cinar", "kirlangic", "demirci", "pusula", "kehribar"];
const KONU = Object.keys(OZEL);

export function derlem({ adet = 4000, tohum = 20260731 } = {}) {
  let s = tohum % 2147483647;
  const r = () => (s = (s * 48271) % 2147483647) / 2147483647;
  const sec = (a) => a[Math.floor(r() * a.length)], belge = [];
  for (let i = 1; i <= adet; i += 1) {
    const konu = sec(KONU), oz = OZEL[konu], soz = [sec(oz), sec(NADIR)];
    if (r() < 0.5) soz.push(sec(ORTAK));
    for (let j = 0, n = 10 + Math.floor(r() * 7); j < n; j += 1)
      soz.push(r() < 0.45 ? sec(ORTAK) : r() < 0.85 ? sec(oz) : sec(NADIR));
    belge.push({ id: i, konu, yil: 1990 + Math.floor(r() * 36), metin: [soz[0], soz[1], konu, ...soz.slice(2)].join(" ") });
  }
  return belge;
}

export function dizinle(belge) {
  const gonderi = new Map(), uzunluk = new Map();
  let bayt = 0;
  for (const d of belge) {
    const t = d.metin.split(" "), sayim = new Map();
    for (const x of t) sayim.set(x, (sayim.get(x) ?? 0) + 1);
    uzunluk.set(d.id, t.length);
    for (const [x, n] of sayim) {
      if (!gonderi.has(x)) { gonderi.set(x, []); bayt += x.length + 4; }   // sozluk girisi
      gonderi.get(x).push([d.id, n]); bayt += 8;
    }
  }
  const ort = [...uzunluk.values()].reduce((a, b) => a + b, 0) / (belge.length || 1);
  return { gonderi, uzunluk, N: belge.length, ort, bayt };
}

// Puanlama: terim sikligi, ters belge sikligi ve belge uzunlugu. YEREL puanlamada df ve ortalama
// uzunluk yalniz bu dizinden okunur; kuresel verilirse butun derlemin istatistigi kullanilir.
export function ara(dz, terim, k, kuresel = null) {
  const N = kuresel ? kuresel.N : dz.N, ort = kuresel ? kuresel.ort : dz.ort, puan = new Map();
  let taranan = 0;
  for (const t of terim) {
    const g = dz.gonderi.get(t) ?? [];
    const df = kuresel ? kuresel.df.get(t) ?? 0 : g.length;
    const idf = Math.log(1 + (N - df + 0.5) / (df + 0.5));
    for (const [id, tf] of g) {
      taranan += 1;
      const norm = tf + 1.2 * (0.25 + 0.75 * dz.uzunluk.get(id) / ort);
      puan.set(id, (puan.get(id) ?? 0) + idf * tf * 2.2 / norm);
    }
  }
  const sirali = [...puan].sort((a, b) => b[1] - a[1] || a[0] - b[0]).slice(0, k);
  return { aday: sirali.map(([id, p]) => ({ id, p })), taranan, eslesen: puan.size };
}

// kume/toplu.mjs — tek tek dizinleme ile toplu dizinlemenin ve yenileme araliginin olculmesi.
// Dizin SUREC ICI BIR MODELDIR: belgeler once bir tampona yazilir, YENILEME tamponu degismez
// bir bolute cevirir ve belge ancak o an sorgulara gorunur olur. Puanlama istatistigi butun
// bolutlerden toplanir, boylece bolut sayisi sirayi degil yalnizca maliyeti degistirir.
import { derlem, dizinle, ara } from "./derlem.mjs";

const N = 4000, YENI = 600, ISTEK = 50, K = 10, OLCUM = 100, SORGU = ["kisa", "oyku", "yalnizlik"];
const s = (x, n) => String(x).padStart(n);

const bos = () => ({ bolut: [], tampon: [], istek: 0, arama: 0 });
const ekle = (D, parti) => { D.istek += 1; D.tampon.push(...parti); };
const yenile = (D) => { if (D.tampon.length) { D.bolut.push(dizinle(D.tampon)); D.tampon = []; } };

function sor(D, terim, k) {
  const df = new Map();
  let n = 0, uz = 0;
  for (const b of D.bolut) {                       // birinci gecis: bolutler arasi istatistik
    n += b.N; uz += b.ort * b.N;
    for (const t of terim) { D.arama += 1; const g = b.gonderi.get(t); if (g) df.set(t, (df.get(t) ?? 0) + g.length); }
  }
  const kur = { df, N: n, ort: uz / n }, puan = [];
  for (const b of D.bolut) { D.arama += terim.length; puan.push(...ara(b, terim, Infinity, kur).aday); }
  puan.sort((a, b) => b.p - a.p || a.id - b.id);
  return { ilk: puan.slice(0, k).map((x) => x.id), eslesen: puan.length, gorunen: n };
}

// N belgeyi parti boyunda isteklerle gonder; her `aralik` belgede bir yenileme calisir.
function kur(belge, parti, aralik) {
  const D = bos();
  for (let i = 0; i < belge.length; i += parti) {
    ekle(D, belge.slice(i, i + parti));
    if ((i + parti) % aralik === 0 || i + parti >= belge.length) yenile(D);
  }
  return D;
}

// Sure olcumu: dizinleme + OLCUM sorgu. Ham sure ORTAMA BAGLIDIR, bu yuzden asagida yalnizca
// esigin ustunde mi altinda mi oldugu basilir. Uc kosumun en kucugu alinir.
function sure(parti, aralik) {
  let en = Infinity;
  for (let k = 0; k < 3; k += 1) {
    const t0 = process.hrtime.bigint();
    const D = kur(taban, parti, aralik);
    for (let q = 0; q < OLCUM; q += 1) sor(D, SORGU, K);
    en = Math.min(en, Number(process.hrtime.bigint() - t0));
  }
  return en;
}

const taban = derlem({ adet: N });
console.log(`${N} belge, tohum 20260731. Sorgu "kisa oyku yalnizlik", son liste ${K}.`);
console.log("Sure ORTAMA BAGLIDIR; ham sure yerine yalnizca esikli bir oran basilir.\n");
console.log("parti | yenileme araligi | istek | bolut | dizin bayt | sorgu basina sozluk aramasi");
console.log("------|------------------|-------|-------|------------|----------------------------");
for (const [parti, aralik] of [[1, 1], [1, 500], [500, 500], [1000, 1000], [500, N]]) {
  const D = kur(taban, parti, aralik);
  D.arama = 0;
  sor(D, SORGU, K);
  console.log(`${s(parti, 5)} | ${s(aralik, 16)} | ${s(D.istek, 5)} | ${s(D.bolut.length, 5)} | ` +
    `${s(D.bolut.reduce((t, b) => t + b.bayt, 0), 10)} | ${s(D.arama, 27)}`);
}
sure(500, 500);                                    // isinma kosumu
const oran = sure(1, 1) / sure(500, 500);
console.log(`\ndizinleme + ${OLCUM} sorgu suresi, tek tek (1/1) bolu toplu (500/500): ` +
  `${oran > 2 ? "2 kattan buyuk" : "2 kat ve altinda"} (ham sure ortama baglidir, basilmaz)`);

// Gorunurluk: 4000 belgelik dizine 600 kayitlik bagis partisi 50'lik isteklerle giriyor ve her
// istekten hemen sonra ayni sorgu kosuluyor. Yenileme arka planda her `aralik` belgede bir
// calisir; yenilenmemis belgeler tamponda bekler ve sorguya gorunmez.
const parti = derlem({ adet: 9000, tohum: 20260801 }).filter((d) => d.konu === "oyku")
  .slice(0, YENI).map((d, i) => ({ ...d, id: N + i + 1 }));
const olcut = sor(kur([...taban, ...parti], 500, 500), SORGU, K);
console.log(`\nyenileme araligi (${YENI} kayitlik parti ${ISTEK}'lik isteklerle giriyor, her istekten sonra bir sorgu):`);
console.log(`olcut: parti tumuyle gorunurken eslesen ${olcut.eslesen}, ilk 5: ${olcut.ilk.slice(0, 5).join(" ")}`);
console.log("aralik | eklenen bolut | ort. gorunmeyen | son sorguda eslesen | eksik | ilk 10 ortak | sozluk aramasi | ilk 5 sonuc");
for (const aralik of [1, 75, 250, YENI * 2]) {
  const D = kur(taban, 500, 500), tabanBolut = D.bolut.length;
  let gorunmez = 0, gorunur = 0, son = null;
  for (let g = ISTEK; g <= YENI; g += ISTEK) {
    const hedef = Math.floor(g / aralik) * aralik;
    while (gorunur < hedef) {                      // her yenileme bir bolut yaratir
      ekle(D, parti.slice(gorunur, gorunur + aralik)); yenile(D); gorunur += aralik;
    }
    D.arama = 0;
    son = sor(D, SORGU, K);
    gorunmez += g - gorunur;
  }
  console.log(`${s(aralik > YENI ? "yok" : aralik, 6)} | ${s(D.bolut.length - tabanBolut, 13)} | ` +
    `${s((gorunmez / (YENI / ISTEK)).toFixed(1), 15)} | ${s(son.eslesen, 19)} | ${s(olcut.eslesen - son.eslesen, 5)} | ` +
    `${s(son.ilk.filter((x) => olcut.ilk.includes(x)).length + "/10", 12)} | ${s(D.arama, 14)} | ${son.ilk.slice(0, 5).join(" ")}`);
}
console.log(`\nkosumdan bagimsiz: istek sayisi = belge / parti boyu, bolut sayisi = belge / yenileme` +
  ` araligi, sorgu basina sozluk aramasi = bolut x terim x 2.`);

4000 belge, tohum 20260731. Sorgu "kisa oyku yalnizlik", son liste 10.
Sure ORTAMA BAGLIDIR; ham sure yerine yalnizca esikli bir oran basilir.

parti | yenileme araligi | istek | bolut | dizin bayt | sorgu basina sozluk aramasi
------|------------------|-------|-------|------------|----------------------------
    1 |                1 |  4000 |  4000 |     813787 |                       24000
    1 |              500 |  4000 |     8 |     387960 |                          48
  500 |              500 |     8 |     8 |     387960 |                          48
 1000 |             1000 |     4 |     4 |     384984 |                          24
  500 |             4000 |     8 |     1 |     382752 |                           6

dizinleme + 100 sorgu suresi, tek tek (1/1) bolu toplu (500/500): 2 kattan buyuk (ham sure ortama baglidir, basilmaz)

yenileme araligi (600 kayitlik parti 50'lik isteklerle giriyor, her istekten sonra bir sorgu):
olcut: parti tumuyle gorunurken eslesen 1115, ilk 5: 4457 4534 4544 3159 3544
aralik | eklenen bolut | ort. gorunmeyen | son sorguda eslesen | eksik | ilk 10 ortak | sozluk aramasi | ilk 5 sonuc
     1 |           600 |             0.0 |                1115 |     0 |        10/10 |           3648 | 4457 4534 4544 3159 3544
    75 |             8 |            25.0 |                1115 |     0 |        10/10 |             96 | 4457 4534 4544 3159 3544
   250 |             2 |            95.8 |                1015 |   100 |         8/10 |             60 | 4457 3159 3544 2689 2362
   yok |             0 |           325.0 |                 515 |   600 |         6/10 |             48 | 3159 3544 2689 2362 3370

kosumdan bagimsiz: istek sayisi = belge / parti boyu, bolut sayisi = belge / yenileme araligi, sorgu basina sozluk aramasi = bolut x terim x 2.

İki Ayrı Eksen

Birinci tablonun ilk satırı en kötü durumdur: her belge ayrı bir istekle gelir ve her istekten sonra yenileme çalışır. Sonuç 4000 istek, 4000 bölüt, 813.787 bayt dizin ve tek bir sorgu için 24.000 sözlük araması. Beşinci satır aynı derlemi 8 istekle ve tek bir bölütle dizinliyor: 382.752 bayt ve sorgu başına 6 arama. Aynı 4000 belge, aynı sıra, dört bin kat daha az sözlük araması.

Baytın iki katına çıkmasının sebebi gönderi listeleri değil sözlüktür: derlemin 80 terimi 4000 bölütte 4000 kez yeniden yazılır. Bölüt başına sabit bir maliyet vardır ve bölüt sayısı arttıkça bu maliyet toplamı büyütür.

İkinci satır dersin asıl ayrımını veriyor. Parti boyu 1 ama yenileme aralığı 500: istek sayısı yine 4000, buna karşın bölüt sayısı 8, bayt 387.960 ve arama 48. Parti boyu istek sayısını belirler, yenileme aralığı bölüt sayısını. İkisi ayrı ayarlardır ve ayrı şeylere mal olur. Toplu dizinleme, istek başına düşen ağ ve ayrıştırma yükünü azaltır; süreç içi model bu yükü taşımadığı için burada basılan süre oranı yalnızca bölüt maliyetini gösterir — dizinleme ve yüz sorgu birlikte ölçüldüğünde tek tek yerleşim, toplu yerleşimin iki katından uzun sürüyor.

Yenileme Aralığı: Görünürlük ve Verim

İkinci tablo 4000 belgelik dizine 600 kayıtlık bir bağış partisini 50’lik isteklerle sokuyor ve her istekten hemen sonra aynı sorguyu koşuyor. Ölçüt, partinin tamamı görünürken dönen yanıt: 1115 eşleşme ve ilk beşte 4457, 4534, 4544.

Aralık 1 iken hiçbir belge beklemiyor: ortalama görünmeyen 0,0 ve son sorgu ölçütle birebir aynı. Bedeli 600 yeni bölüt ve sorgu başına 3648 sözlük aramasıdır — yenilemesiz durumun 76 katı, çünkü her sorgu birer belgelik altı yüz bölüte tek tek bakıyor.

Aralık 75 bu dersin en dengeli satırıdır: 8 bölüt, ortalama 25 belge tamponda bekliyor, ama son sorgu yine 1115 eşleşme ve 10/10 veriyor. Görünürlük gecikmesi var, sonuç doğruluğu yok olmuyor; sorgu maliyeti 96 aramada kalıyor.

Aralık 250’de gecikme kümeye geçiyor. Ortalama 95,8 belge görünmez durumda ve son sorgu 1015 belge döndürüyor: 100 kayıt eksik. İlk on 8/10’a düşüyor ve ilk beş değişiyor — 4534 ile 4544 listeden çıkıyor, yerlerine daha eski kayıtlar giriyor. Yenileme kapalıyken tablo en uca gidiyor: ortalama 325 belge görünmez, son sorgu 515 belgeyle yanıt veriyor, 600 kaydın tamamı eksik ve ilk beşte bağış partisinden tek bir kitap yok. Sorgu en ucuz hâlinde, 48 arama; dönen liste ise partinin hiç gelmediği bir kataloğun listesi.

Takas iki uçlu değildir. Aralığı kısaltmak görünürlük gecikmesini düşürür ama bölüt üretir; uzatmak sorguyu ucuzlatır ama dönen kümeyi geriye çeker. Ortada, gecikmenin ölçüldüğü ama sonuca yansımadığı bir aralık vardır: bu derlemde 75.

Özet

• Aynı 4000 belge tek tek dizinlendiğinde 4000 istek, 4000 bölüt, 813.787 bayt ve sorgu başına 24.000 sözlük araması üretti; 500’lük partilerle ve tek yenilemeyle 8 istek, 1 bölüt, 382.752 bayt ve 6 arama üretti.
• Bayt artışı gönderi listelerinden değil sözlükten geliyor: 80 terim 4000 bölütte yineleniyor.
• Parti boyu istek sayısını, yenileme aralığı bölüt sayısını belirler; parti 1 ile aralık 500 birleştiğinde istek 4000 kalırken bölüt 8’e iniyor.
• Dizinleme ile yüz sorgu birlikte ölçüldüğünde tek tek yerleşim toplu yerleşimin iki katından uzun sürdü; ham süre ortama bağlı olduğu için yalnızca eşik basıldı.
• Yenileme aralığı 1 iken görünmeyen belge 0 ama sorgu başına arama 3648; aralık 75 iken ortalama 25 belge bekliyor ve sonuç hâlâ 10/10.
• Aralık 250’de son sorgu 100 kaydı kaçırdı ve ilk beşten 4534 ile 4544 düştü; yenileme kapalıyken 600 kaydın tamamı eksik kaldı ve ilk on 6/10’a indi.

Sonraki Adım

Bu ders bölütü ucuz bir yan ürün gibi ele aldı ve yalnızca sayısını saydı. Tablolar bunun sürmeyeceğini gösteriyor: tek tek dizinleme 4000 bölüt bıraktı, yenileme aralığı 1 olan yerleşim 600 bölüt ekledi ve her yeni bölüt sorgu başına sabit bir maliyet daha getirdi. Bölütler değişmez olduğu için silinen bir belge de yerinde durur, yalnızca silinmiş işaretlenir; dizin büyüdükçe okunmayan gönderi girişleri birikir. Bu yükün geri alınmasının tek yolu bölütleri birleştirmektir. Sonraki ders küçük bölütleri büyük bölütlere dönüştürmenin arka plan maliyetini ölçer: birleştirme sırasında okunan ve yeniden yazılan bayt, silinmiş belgelerin geri kazandırdığı yer ve birleştirme sürerken sorgu başına düşen bölüt sayısının nasıl değiştiği.