--- title: Dizinleme source: 'https://academia.sh/tr/kurslar/nosql/dizinleme' course: 'İlişkisel Olmayan Veri Modelleri' language: tr updated: '2026-08-17T18:08:58+00:00' license: 'CC BY-SA 4.0' --- # Dizinleme Dizinin belge yapısı üzerinde kurulması: bir dizi alanının tek belgeden kaç giriş ürettiği, iki dizi alanını tek bileşik dizinde birleştirmenin giriş sayısını 20.000'den 120.042'ye çıkarması, aynı ögede karşılanması gereken koşulun iki tek alan dizininde 6.033 belge okutup öge düzeyi dizinde 3.340 okutması ve kısmi dizinin aynı yanıtı derlemin %27,8'i yerine %6'sı yer kaplayarak vermesi. Ö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. ```js // 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. ```js // 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ı.