Dizinleme

Önceki dersin üç boru hattı aynı yanıtı üç ayrı bedelle üretti, ama ortak bir yanları vardı: üçü de ilk aşamada derlemin tamamını, 20.000 belgeyi okudu. Aşama sırası işlenen kaydı ve tutulan belleği değiştirdi, okunan belge sayısını değiştirmedi. Onu değiştiren tek yapı dizindir.

Dizinin kuramı burada kurulmaz. İlişkisel Veritabanı Yönetimi kursunun Dizinler ve Bölümleme konusu ağaç, karma ve ters dizini, sütun sırasını ve kısmi dizinin kazancını ölçtü; sıralı bir yapının hangi soruya yanıt verdiği orada sayılara bağlandı ve o sayılar burada geçerlidir. Bu dersin sorusu dizinin üstüne kurulduğu veridir. İlişkisel bir satırda dizinlenen sütun tek bir değer taşır; belge modelinde aynı alan bir dizi olabilir, iç içe bir belgenin içinde durabilir ya da belgelerin yalnız bir bölümünde bulunabilir. Üç durumun üçü de dizin girişinin sayısını değiştirir, ve giriş sayısı hem yeri hem yazma bedelini belirler.

Bir Belge, Birden Çok Giriş

Dizin girişi bir anahtar değeri ile o değeri taşıyan belgeye bir başvurudan oluşur. İlişkisel dizinde bu ilişki birebirdir: bir satır bir giriş üretir. Bir yol dizinin içine indiğinde ilişki bire çok olur — beş kopyası olan bir kitap, kopya.sube dizininde beş giriş üretir. Buna çoklu giriş (multikey) denir ve önceki dersteki varoluşsal kuralın depolama tarafındaki karşılığıdır: yol birden çok değere ulaşıyorsa, dizin o değerlerin hepsini ayrı ayrı adreslemek zorundadır.

Aynı belgede aynı anahtarın iki kez üretilmesi durumunda dizin tek giriş tutar; üç kopyası da Kadıköy’de olan bir kitap kopya.sube dizininde bir kez görünür. Aşağıdaki gerçekleştirim üç kararı da taşır: çoklu giriş, bileşik anahtar ve kısmi koşul.

// dizin.mjs — belge dizini. Bir yol dizinin icine indiginde tek belge birden cok giris
// uretir: coklu giris. Bilesik anahtar, oge duzeyi anahtar ve kismi kosul desteklenir.
// Giris bayti 01. dersin kodlama kuralindan gelir; her giris ayrica belgeye 8 baytlik
// bir basvuru tasir.
const BASVURU = 8;

export function bayt(d) {
  if (d === null || d === undefined) return 0;
  if (typeof d === "boolean") return 1;
  if (typeof d === "number") return Number.isInteger(d) ? 4 : 8;
  if (typeof d === "string") return 4 + Buffer.byteLength(d) + 1;
  const oge = Array.isArray(d) ? d.map((v, i) => [String(i), v]) : Object.entries(d);
  return 5 + oge.reduce((t, [a, v]) => t + 2 + Buffer.byteLength(a) + bayt(v), 0);
}

// Yoldaki degerler: yol bir diziye rastlarsa ogelerine iner.
export function degerler(kok, yol) {
  let kume = [kok];
  for (const ad of yol.split(".")) {
    const sonraki = [];
    for (const d of kume)
      for (const o of Array.isArray(d) ? d : [d])
        if (o && typeof o === "object" && !Array.isArray(o) && ad in o) sonraki.push(o[ad]);
    kume = sonraki;
  }
  return kume.flatMap((v) => (Array.isArray(v) ? v : [v]));
}

export class Dizin {
  // alanlar: anahtari kuran yollar. oge: verilirse anahtar o dizinin OGESI uzerinde
  // kurulur ve yollar ogeye goredir. kosul: verilirse yalniz kosulu saglayan belge ya da
  // oge dizine girer -- kismi dizin.
  constructor(ad, { alanlar, oge = null, kosul = null }) {
    Object.assign(this, { ad, alanlar, oge, kosul });
    this.giris = new Map();                         // anahtar -> belge anahtari dizisi
    this.ham = 0;                                   // tekillestirmeden onceki giris
    this.taranan = 0;
  }
  anahtarlar(belge) {                               // bir belgenin urettigi anahtarlar
    const kaynak = this.oge
      ? degerler(belge, this.oge).filter((o) => !this.kosul || this.kosul(o))
      : !this.kosul || this.kosul(belge) ? [belge] : [];
    const cikan = [];
    for (const k of kaynak) {
      let carpim = [[]];
      for (const alan of this.alanlar) {
        const d = degerler(k, alan);
        carpim = carpim.flatMap((on) => (d.length ? d : [null]).map((v) => [...on, v]));
      }
      cikan.push(...carpim);
    }
    return cikan;
  }
  kur(belgeler) {
    for (const b of belgeler) {
      const uretilen = this.anahtarlar(b).map((a) => JSON.stringify(a));
      this.ham += uretilen.length;
      for (const a of new Set(uretilen)) {           // ayni belgede ayni anahtar bir kez
        if (!this.giris.has(a)) this.giris.set(a, []);
        this.giris.get(a).push(b._k);
      }
    }
    return this;
  }
  get sayi() {
    return [...this.giris.values()].reduce((t, v) => t + v.length, 0);
  }
  get bayt() {
    let n = 0;
    for (const [a, k] of this.giris)
      n += k.length * (JSON.parse(a).reduce((t, v) => t + bayt(v), 0) + BASVURU);
    return n;
  }
  ara(...anahtar) {                                  // tam anahtarla arama
    const k = this.giris.get(JSON.stringify(anahtar)) ?? [];
    this.taranan += k.length;
    return k;
  }
}

oge seçeneği belge modeline özgü olan ayrımı taşır. alanlar: ["kopya.sube", "kopya.durum"] ile kurulan bileşik dizin iki yolu ayrı ayrı çözer ve değerlerinin çarpımını alır; oge: "kopya" ile kurulan dizin ise anahtarı her kopyanın kendi içinde kurar. İkisi aynı iki alanı taşır ve farklı soruya yanıt verir.

Yedi Dizin, Aynı Katalog

NS7 (varsayım): katalog 20.000 kitap belgesidir, her kitabın 1–5 kopyası ve 2–4 etiketi vardır, tohum 424242’dir. NS13 (varsayım): bir dizin girişi anahtar değerinin kodlanmış hâline ek olarak 8 baytlık bir belge başvurusu taşır ve düğüm doluluğu tam sayılır. Gerekçe: başvuru genişliği ile doluluk motora göre değişir; ikisi de dizinler arasındaki oranı değiştirmez, yalnız mutlak baytı ölçekler.

Ölçülen iş, önceki iki dersin sorusudur: Kadıköy şubesinde onarımdaki kopyası olan kitaplar. Yanıt dört yoldan alınır ve her yolda taranan dizin girişi ile okunan belge sayılır. Ardından, ikinci dersin üçüncü işi olan 5.000 kopya durumu değişikliği dizin bakımı açısından iki kararla koşturulur.

// dizin-olcum.mjs — ayni katalog uzerinde yedi dizin kurulur, ayni soru dort yoldan
// yanitlanir ve 5.000 durum degisikliginin dizin bakimi iki kararla sayilir.
// Ayni dizinde dizin.mjs bulunur.
import { Dizin, bayt } from "./dizin.mjs";

let cekirdek = 424242;                                   // gorunur tohum
const rast = () => (cekirdek = (cekirdek * 1103515245 + 12345) % 2147483648) / 2147483648;
const SUBE = ["Merkez", "Bahcelievler", "Kadikoy", "Beyoglu", "Konak", "Nilufer"];
const DURUM = ["rafta", "oduncte", "onarimda"];
const ETIKETLER = ["roman", "tarih", "cocuk", "siir", "bilim", "basvuru"];

const KATALOG = [];
for (let i = 1; i <= 20000; i += 1) {
  const kopya = [], etiket = [];
  for (let j = 0, n = 1 + Math.floor(rast() * 5); j < n; j += 1)
    kopya.push({ barkod: `B${String(i * 10 + j).padStart(7, "0")}`,
      sube: SUBE[Math.floor(rast() * 6)], durum: DURUM[Math.floor(rast() * 3)] });
  for (let j = 0, n = 2 + Math.floor(rast() * 3); j < n; j += 1)
    etiket.push(ETIKETLER[Math.floor(rast() * 6)]);
  KATALOG.push({ _k: `K-${String(i).padStart(5, "0")}`, yazar: `Yazar ${i % 4000}`,
    yayin_yili: 1950 + (i % 75), etiket, kopya });
}
const HARITA = new Map(KATALOG.map((b) => [b._k, b]));
const DERLEM = KATALOG.reduce((t, b) => t + bayt(b), 0);
const KOPYA = KATALOG.reduce((t, b) => t + b.kopya.length, 0);
console.log(`katalog ${KATALOG.length} belge, ${KOPYA} kopya, derlem ${DERLEM} bayt`);

const [yazarD, etiketD, subeD, durumD, carpimD, ogeD, kismiD] = [
  new Dizin("yazar", { alanlar: ["yazar"] }),
  new Dizin("etiket", { alanlar: ["etiket"] }),
  new Dizin("kopya.sube", { alanlar: ["kopya.sube"] }),
  new Dizin("kopya.durum", { alanlar: ["kopya.durum"] }),
  new Dizin("etiket + kopya.sube", { alanlar: ["etiket", "kopya.sube"] }),
  new Dizin("oge(sube,durum)", { alanlar: ["sube", "durum"], oge: "kopya" }),
  new Dizin("kismi oge(sube)", { alanlar: ["sube"], oge: "kopya",
    kosul: (o) => o.durum === "onarimda" }),
].map((d) => d.kur(KATALOG));
const DIZINLER = [yazarD, etiketD, subeD, durumD, carpimD, ogeD, kismiD];

for (const d of DIZINLER)
  console.log(`${d.ad.padEnd(19)} ham ${String(d.ham).padStart(6)}` +
    `  giris ${String(d.sayi).padStart(6)}  belge basina ${(d.sayi / 20000).toFixed(2)}` +
    `  ${String(d.bayt).padStart(7)} bayt  derlemin %${(100 * d.bayt / DERLEM).toFixed(1)}`);

// Ayni soru: Kadikoy subesinde onarimdaki kopyasi olan kitaplar.
const OGE = (k) => k.sube === "Kadikoy" && k.durum === "onarimda";
const dogru = KATALOG.filter((b) => b.kopya.some(OGE)).length;
const suz = (anahtarlar) => anahtarlar.filter((k) => HARITA.get(k).kopya.some(OGE)).length;
console.log(`kosulu saglayan kopya ${KATALOG.reduce((t, b) => t + b.kopya.filter(OGE).length, 0)}` +
  `, bu kopyalari tasiyan belge ${dogru}`);

const kesisim = new Set(subeD.ara("Kadikoy"));
const B = durumD.ara("onarimda").filter((k) => kesisim.has(k));
const C = ogeD.ara("Kadikoy", "onarimda");
const D = kismiD.ara("Kadikoy");
const yollar = [
  ["A tarama", 0, KATALOG.map((b) => b._k)],
  ["B iki tek alan dizini", subeD.taranan + durumD.taranan, B],
  ["C oge duzeyi bilesik", ogeD.taranan, C],
  ["D kismi oge dizini", kismiD.taranan, D],
];
for (const [ad, taranan, kume] of yollar)
  console.log(`${ad.padEnd(22)} taranan giris ${String(taranan).padStart(6)}` +
    `  okunan belge ${String(kume.length).padStart(5)}  sonuc ${suz(kume)}`);

// 5.000 kopyanin durumu degisir: dizin bakimi iki kararla sayilir.
const anahtarKumesi = (d, b) => [...new Set(d.anahtarlar(b).map((a) => JSON.stringify(a)))];
const fark = (a, b) => a.filter((v) => !b.includes(v)).length
  + b.filter((v) => !a.includes(v)).length;
let farkli = 0, tam = 0, gercek = 0;
for (let i = 0; i < 5000; i += 1) {
  const kitap = KATALOG[(i * 7) % KATALOG.length];
  const hedef = kitap.kopya[i % kitap.kopya.length];
  const eski = DIZINLER.map((d) => anahtarKumesi(d, kitap));
  if (hedef.durum !== "rafta") gercek += 1;
  hedef.durum = "rafta";
  const yeni = DIZINLER.map((d) => anahtarKumesi(d, kitap));
  for (let j = 0; j < DIZINLER.length; j += 1) {
    farkli += fark(eski[j], yeni[j]);
    tam += eski[j].length + yeni[j].length;
  }
}
console.log(`5.000 durum degisikliginin ${gercek} tanesi degeri gercekten degistiriyor`);
console.log(`  fark bakimi             ${farkli} giris yazmasi`);
console.log(`  belge yeniden dizinleme ${tam} giris yazmasi, ${(tam / farkli).toFixed(1)} kat`);

katalog 20000 belge, 59494 kopya, derlem 6388114 bayt
yazar               ham  20000  giris  20000  belge basina 1.00   454450 bayt  derlemin %7.1
etiket              ham  59730  giris  50179  belge basina 2.51   911722 bayt  derlemin %14.3
kopya.sube          ham  59494  giris  47982  belge basina 2.40   976310 bayt  derlemin %15.3
kopya.durum         ham  59494  giris  38997  belge basina 1.95   766544 bayt  derlemin %12.0
etiket + kopya.sube ham 177480  giris 120042  belge basina 6.00  3664167 bayt  derlemin %57.4
oge(sube,durum)     ham  59494  giris  55516  belge basina 2.78  1777092 bayt  derlemin %27.8
kismi oge(sube)     ham  20021  giris  18752  belge basina 0.94   381997 bayt  derlemin %6.0
kosulu saglayan kopya 3508, bu kopyalari tasiyan belge 3340
A tarama               taranan giris      0  okunan belge 20000  sonuc 3340
B iki tek alan dizini  taranan giris  21248  okunan belge  6033  sonuc 3340
C oge duzeyi bilesik   taranan giris   3340  okunan belge  3340  sonuc 3340
D kismi oge dizini     taranan giris   3340  okunan belge  3340  sonuc 3340
5.000 durum degisikliginin 3311 tanesi degeri gercekten degistiriyor
  fark bakimi             10840 giris yazmasi
  belge yeniden dizinleme 173994 giris yazmasi, 16.1 kat

Giriş Sayısının Bedeli

İlk satırlar dizin boyutunun kaynağını verir. yazar dizini belge başına tam bir giriş üretir ve derlemin %7,1’i kadar yer tutar; bu, ilişkisel bir dizinin oranıdır. etiket dizini 59.730 ham giriş üretir, tekilleştirmeden sonra 50.179 kalır — belge başına 2,51. Aradaki 9.551 giriş aynı etiketin bir kitapta iki kez yazılmasından gelir ve dizin bunu tek girişe indirir. kopya.durum dizininde tekilleştirme daha da güçlüdür: 59.494 ham giriş 38.997’ye iner, çünkü üç değerli bir alanda bir kitabın birden çok kopyasının aynı durumda olması sıradandır.

Beşinci satır dersin en sert sayısıdır. etiket ile kopya.sube tek bir bileşik dizinde birleştirildiğinde giriş sayısı toplam değil çarpım olur: 177.480 ham giriş, 120.042 tekil giriş, belge başına altı. Dizin 3.664.167 bayt tutar, yani derlemin %57,4’ü. İki dizi alanının aynı bileşik dizinde bulunmasının motorlar tarafından engellenmesinin nedeni budur; engel bir kolaylık değil, bu çarpımın önlenmesidir. Aynı iki alan ayrı iki dizinde tutulduğunda toplam 98.161 giriş ve 1.888.032 bayt eder — yarısından az.

Aynı Ögede Olma Koşulu

Dört yol aynı 3.340 belgeyi döndürür; ayrıldıkları yer bu yanıta ulaşmak için okunan belgedir. Tarama 20.000 belge okur. İki tek alan dizininin kesişimi 21.248 giriş tarar ve 6.033 belge okur — üçüncü dersin belge düzeyi bağlaç sayısının tam olarak kendisi. Dizin kesişimi “Kadıköy’de kopyası olan” ile “onarımda kopyası olan” kümelerini keser ve koşulların aynı kopyada karşılandığını doğrulayamaz; o doğrulamayı belgeyi okuyarak yapmak zorundadır. Fazladan okunan 2.693 belge bu yüzden okunur.

Öge düzeyi bileşik dizin bu işi dizinin içinde yapar. Anahtar her kopyanın kendi şubesi ve durumundan kurulduğu için ("Kadikoy", "onarimda") araması doğrudan 3.340 belge başvurusu verir; taranan giriş sayısı da 3.340’tır. Koşulu sağlayan kopya sayısı 3.508’dir — aradaki 168 kopya, aynı kitabın aynı şubede onarımdaki ikinci kopyasıdır ve dizin bunları tek girişe indirmiştir. Okunan belge sayısı taramaya göre altıda bire, dizin kesişimine göre 1,8 kat düşer ve okunan her belge sonuca kalır.

Bedeli boyuttur: bu dizin 1.777.092 bayt, derlemin %27,8’i. Kısmi dizin aynı yanıtı çok daha ucuza verir. durum alanı onarimda olan kopyalar 59.494’ün 20.021’idir; yalnız onları kapsayan dizin 18.752 giriş ve 381.997 bayt tutar, derlemin %6’sı. Aynı arama aynı 3.340 belgeyi aynı sayıda giriş tarayarak döndürür. Kısıtı, kapsadığı koşulun sorguda bulunmasıdır: bu dizin “Kadıköy’de raftaki kopyalar” sorusuna hiçbir şey söyleyemez, çünkü o kopyalar dizinde yoktur.

Yazmanın Bedeli

Son üç satır dizinin öteki yüzüdür. 5.000 kopya durum değişikliğinin 3.311’i değeri gerçekten değiştirir. Değişen anahtarları hesaplayıp yalnız onları yazan bakım yedi dizin için 10.840 giriş yazması yapar — denenen değişiklik başına 2,17. Aynı işi belgenin bütün girişlerini silip yeniden üreterek yapan bakım 173.994 giriş yazması yapar, 16,1 kat. Fark ikinci dersin bulgusuyla aynı kökten gelir: gömülü şemada bir kopyanın durumu değiştiğinde kitabın tamamı yeniden yazılır, ve yeniden yazılan bir belgenin bütün dizin girişlerini yeniden üretmek en kolay uygulamadır. Depo hangi alanın değiştiğini biliyorsa bu 16 katın tamamından kaçınır; bilmiyorsa dizin sayısı arttıkça yazma bedeli doğrusal büyür.

Dizin başına düşen paya bakıldığında karar netleşir: yedi dizinin toplamı 8.932.282 bayt, derlemin 1,4 katı. Belge modelinde dizin, alan başına değil giriş başına ücretlendirilir ve giriş sayısını belirleyen şey şemanın kendisidir.

Özet

• Bir yol dizinin içine indiğinde tek belge birden çok dizin girişi üretir; kopya.sube dizini 20.000 belgeden 59.494 ham, tekilleştirmeden sonra 47.982 giriş üretir.
• İki dizi alanını tek bileşik dizinde birleştirmek girişleri toplamaz, çarpar: 120.042 giriş ve derlemin %57,4’ü kadar yer.
• İki tek alan dizininin kesişimi koşulların aynı ögede karşılandığını doğrulayamaz; 6.033 belge okur, bunların 2.693’ü sonuca kalmaz.
• Öge düzeyi bileşik dizin aynı yanıtı 3.340 giriş tarayıp 3.340 belge okuyarak verir; kısmi dizin aynı yanıtı derlemin %27,8’i yerine %6’sı kadar yer kaplayarak verir.
• Değişen anahtarı hesaplayan bakım 5.000 güncellemeye 10.840 giriş yazması harcar, belgeyi bütünüyle yeniden dizinleyen bakım 173.994 (16,1 kat).

Sonraki Adım

Bu dersteki bütün dizinler var olan alanların üstüne kuruldu ve alanların ne taşıdığına hiç bakmadı. kopya.durum dizini onarimda yerine onarım yazılmış bir kopyayı da sessizce dizinler; birinci dersin ölçtüğü metin yazılmış yayın yılları da yayin_yili dizinine kendi tipleriyle girer. Esnek şema, alanın bulunup bulunmamasını ve tipini yazma anında bağlamaz — birinci ders bunun aralık sorgusunda 3.990 yerine 5.991 ya da 3.491 belge döndürdüğünü saymıştı ve kuralın nasıl konacağını bu derse bırakmıştı. Sonraki ders o kuralı yazar ve iki sayıyı ölçer: kuralın yakaladığı bozuk belge sınıfı ile kaçırdığı sınıf, ve kural derlem doluyken konduğunda ortaya çıkan ihlal sayısıyla geriye dönük düzeltmenin dokunduğu belge sayısı.