--- title: 'Bölüt Birleştirme' source: 'https://academia.sh/tr/kurslar/arama-motorlari/bolut-birlestirme' course: 'Arama Motorları ve Metin Erişimi' language: tr updated: '2026-08-17T18:09:01+00:00' license: 'CC BY-SA 4.0' --- # Bölüt Birleştirme Her toplu işten geriye kalan bölütlerin sorguya ödettiği bedel: bölüt sayısının sözlük araması, taranan gönderi girişi ve dizin boyutuna etkisi, silme işaretlerinin temizlenmesi, birleştirmenin kopyaladığı bayt ve katmanlı birleştirme politikasının iki çarpan ayarının karşılaştırılması. Toplu dizinleme yazma verimini artırdı: belgeler tek tek değil parti hâlinde dizine girdi. Bu kazancın sessiz bir yan ürünü vardır. Her toplu iş dizine yeni bir **bölüt** bırakır: kendi sözlüğü, kendi gönderi listeleri ve kendi belge sayısı olan, yazıldıktan sonra bir daha değiştirilmeyen bir birim. Bölüt değişmez olduğu için silinen bir belge yerinden kalkmaz, yalnız bir **silme işareti** alır ve orada durmayı sürdürür. Kırk altı parti sonunda dizin kırk altı ayrı bölüttür ve her sorgu hepsini ayrı ayrı aramak zorundadır. Bu dersin iki sorusu vardır. Bölüt sayısı sorguya tam olarak neyi ödetir, ve arka planda çalışan birleştirme bunun ne kadarını geri alır, karşılığında neyi kopyalar. ## Bölüt Yığınının Kurulumu Ölçüm için katalog derlemi, bölütlü ters dizin ve birleştirme kendi yazılır. Derlem 12.000 kitap kaydıdır, tohum 20260731; 300 belgelik kırk parti dizine girer, ardından altı düzeltme partisi daha önce dizinlenmiş kayıtları yeniden yazar ve eski kopyalarına silme işareti koyar. **AK10.** Her bölüt bağımsız arandığı için puanlama bölütün **kendi** belge sayısını ve belge sıklığını kullanır. Bu, gerçek bir bölütlü dizinin davranışıdır: küresel istatistik ancak bölütler birleştiğinde ortaya çıkar. **AK11.** Bölütün diskteki boyutu, sözlüğün ve gönderi listelerinin metin olarak serileştirilmiş hâlidir. Gerçek bir gerçekleştirim bunu sıkıştırır; oran değişir, ölçümün yönü değişmez. **AK12.** Bir birleştirmenin bedeli, okunan girdi baytı ile yazılan çıktı baytının toplamıdır. ```js // derlem.mjs — tohumlu katalog derlemi, bölütlü ters dizin ve katmanlı birleştirme export function uretec(tohum) { // belirlenimci sözde rastgele üreteç let a = tohum >>> 0; return () => { a = (a + 0x6d2b79f5) >>> 0; let t = a; t = Math.imul(t ^ (t >>> 15), t | 1); t ^= t + Math.imul(t ^ (t >>> 7), t | 61); return ((t ^ (t >>> 14)) >>> 0) / 4294967296; }; } const SIFAT = 'sessiz uzak kırık yitik beyaz kara ince derin sarı uzun geç son eski yeni yalnız'.split(' '); const AD = 'kapı deniz yol ev şehir bahçe ada defter ırmak kuyu saat orman köprü kule bahar'.split(' '); const KONU = ['çocuk edebiyatı', 'kısa öykü', 'roman', 'deneme', 'şiir', 'tarih', 'coğrafya', 'felsefe', 'psikoloji', 'ekonomi', 'mimarlık', 'müzik', 'sinema', 'gezi', 'biyografi', 'anı', 'bilim kurgu', 'polisiye', 'halk bilimi', 'dil bilim']; const KOK = ('kitap yazar anlatı öykü çocuk kent bellek yolculuk kuşak savaş göç aile deniz kış ' + 'sabah mektup fotoğraf tren sokak okul kütüphane rüzgâr sessizlik umut ada yağmur orman köy ' + 'dağ nehir sınır yüzyıl kadın asker öğretmen hekim ressam şarkı dize kapak baskı').split(' '); const KISI = 'Ahmet Zeynep Mehmet Elif Can Ayşe Murat Selin Kemal Deniz Nazlı Orhan'.split(' '); const SOY = 'Yılmaz Demir Kaya Çelik Şahin Aydın Öztürk Arslan Doğan Koç'.split(' '); function cekim(kok, i) { // ek yüzey biçimi: ünlü uyumu ve sertleşme const v = [...kok].reverse().find((c) => 'aeıioöuü'.includes(c)); const k = 'aıou'.includes(v), d = 'fhkpsştç'.includes(kok.at(-1)) ? 't' : 'd'; return kok + ['', k ? 'lar' : 'ler', d + (k ? 'a' : 'e'), d + (k ? 'an' : 'en'), k ? 'la' : 'le', k ? 'lara' : 'lere', k ? 'larda' : 'lerde', k ? 'lardan' : 'lerden'][i]; } export function derlemUret(sayi, tohum) { // kütüphane katalogundan kitap kaydı const r = uretec(tohum), liste = []; for (let i = 0; i < sayi; i++) { const ozet = []; for (let j = 0; j < 16; j++) // sık kökler daha sık geçer: eğik seçim ozet.push(cekim(KOK[Math.floor(r() ** 2 * KOK.length)], Math.floor(r() ** 2 * 8))); const konu = [KONU[Math.floor(r() * 20)]]; if (r() < 0.45) konu.push(KONU[Math.floor(r() * 20)]); liste.push({ id: 'k' + String(i).padStart(5, '0'), ozet: ozet.join(' '), konu, ad: `${SIFAT[Math.floor(r() * 15)]} ${AD[Math.floor(r() * 15)]}`, yazar: `${KISI[Math.floor(r() * 12)]} ${SOY[Math.floor(r() * 10)]}`, yil: 1990 + Math.floor(r() * 35), raf: 'pl' + (100 + Math.floor(r() * 900)) + '.' + (1 + Math.floor(r() * 40)), }); } return liste; } export const metin = (b) => `${b.ad} ${b.ozet} ${b.konu.join(' ')} ${b.yazar} ${b.yil} ${b.raf}`; export const belirtecle = (s) => // Türkçe küçük harf, harf dışı ayırıcı s.toLocaleLowerCase('tr').split(/[^\p{L}\p{N}]+/u).filter((t) => t.length > 1); export class Bolut { // bir toplu işten doğan, değişmez bölüt constructor(belgeler) { this.sozluk = new Map(); // terim -> [[belge kimliği, terim sıklığı], ...] this.belge = new Set(); this.silinen = new Set(); for (const b of belgeler) { this.belge.add(b.id); const sayac = new Map(); for (const t of belirtecle(metin(b))) sayac.set(t, (sayac.get(t) || 0) + 1); for (const [t, tf] of sayac) { if (!this.sozluk.has(t)) this.sozluk.set(t, []); this.sozluk.get(t).push([b.id, tf]); } } } serile() { // diske yazılan biçim: sözlük + gönderi listeleri let s = ''; for (const [t, g] of this.sozluk) s += t + '\t' + g.map(([i, f]) => i + ':' + f).join(' ') + '\n'; for (const id of this.silinen) s += '-\t' + id + '\n'; return s; } get bayt() { return Buffer.byteLength(this.serile()); } } // bölütler üzerinde sorgu: her bölütte ayrı arama, puan bölütün kendi istatistiğinden export function ara(bolutler, terimler, k = 10) { const puan = new Map(); let sozlukAramasi = 0, taranan = 0, atilan = 0; for (const bl of bolutler) { const N = bl.belge.size; // silinen belge bölütün istatistiğinde durur for (const t of terimler) { sozlukAramasi++; const g = bl.sozluk.get(t); if (!g) continue; const idf = Math.log(1 + N / g.length); for (const [id, tf] of g) { taranan++; if (bl.silinen.has(id)) { atilan++; continue; } puan.set(id, (puan.get(id) || 0) + tf * idf); } } } const sira = [...puan].sort((a, b) => b[1] - a[1] || (a[0] < b[0] ? -1 : 1)); return { ilkK: sira.slice(0, k).map(([id]) => id), eslesen: sira.length, sozlukAramasi, taranan, atilan }; } export function birlestir(bolutler) { // silme işaretlilerini atarak tek bölüte indirir const yeni = new Bolut([]); for (const bl of bolutler) { for (const id of bl.belge) if (!bl.silinen.has(id)) yeni.belge.add(id); for (const [t, g] of bl.sozluk) { const kalan = g.filter(([id]) => !bl.silinen.has(id)); if (kalan.length === 0) continue; if (!yeni.sozluk.has(t)) yeni.sozluk.set(t, []); for (const p of kalan) yeni.sozluk.get(t).push(p); } } return yeni; } // katmanlı politika: aynı katmanda çarpan kadar bölüt birikince hepsi üst katmana birleşir export function yiginKur(carpan, sayi = 12000, tohum = 20260731) { const derlem = derlemUret(sayi, tohum); const katman = [], nerede = new Map(); let kopyalanan = 0, birlestirme = 0, toplamBolut = 0, parti = 0; const sayim = () => katman.reduce((n, k) => n + k.length, 0); const yerlestir = (b, k) => { while (katman.length <= k) katman.push([]); katman[k].push(b); if (katman[k].length < carpan) return; const grup = katman[k].splice(0, carpan), yeni = birlestir(grup); for (const g of grup) kopyalanan += g.bayt; // okunan kopyalanan += yeni.bayt; // yazılan birlestirme++; for (const id of yeni.belge) nerede.set(id, yeni); yerlestir(yeni, k + 1); }; const ekle = (belgeler) => { const b = new Bolut(belgeler); for (const id of b.belge) nerede.set(id, b); yerlestir(b, 0); toplamBolut += sayim(); parti++; }; for (let i = 0; i < sayi; i += 300) ekle(derlem.slice(i, i + 300)); const r = uretec(907); for (let p = 0; p < 6; p++) { // düzeltme partisi: kayıt yeniden dizinlenir const duzeltme = []; while (duzeltme.length < 300) { const b = derlem[Math.floor(r() * sayi)], eski = nerede.get(b.id); if (!eski || eski.silinen.has(b.id)) continue; eski.silinen.add(b.id); // eski kopya silme işareti alır duzeltme.push(b); } ekle(duzeltme); } return { derlem, bolutler: katman.flat(), kopyalanan, birlestirme, ortalama: toplamBolut / parti }; } ``` ## Bölüt Sayısı Sorguya Ne Ödetir Aynı yığın üç dizilimle aranır: hiç birleştirilmemiş kırk altı bölüt, beş bölüte indirilmiş hâli ve tek bölüt. Beş katalog sorusu koşar; her dizilimde sözlük araması, taranan gönderi girişi, silme işareti yüzünden atılan giriş ve eşleşen belge sayısı sayılır. Sonra ilk on sonuç tek bölütlü dizilimle karşılaştırılır. ```js // bolut.mjs — bölüt sayısının sorgu maliyetine, kümeye ve sıraya etkisi import { ara, birlestir, yiginKur } from './derlem.mjs'; const SORGULAR = [ ['çocuk', 'edebiyatı', 'kısa', 'öykü'], ['yitik', 'kapı'], ['kütüphane', 'bellek', 'yolculuk'], ['deniz', 'ada', 'yağmur'], ['polisiye', 'kent'], ]; const { bolutler } = yiginKur(Infinity); // Infinity: hiç birleştirme yapılmaz const grupla = (bl, n) => { // ardışık bölütleri n gruba indirger const adim = Math.ceil(bl.length / n), c = []; for (let i = 0; i < bl.length; i += adim) c.push(birlestir(bl.slice(i, i + adim))); return c; }; const dizilim = [['birleştirme yok', bolutler], ['beş bölüt', grupla(bolutler, 5)], ['tek bölüt', grupla(bolutler, 1)]]; console.log('derlem: 12000 belge, tohum 20260731 | 300 belgelik 40 parti + 6 düzeltme partisi'); console.log('dizilim bölüt sözlük girişi dizin bayt sözlük araması taranan atılan eşleşen'); const ilkOn = new Map(); for (const [ad, bl] of dizilim) { let sozluk = 0, bayt = 0, sa = 0, tar = 0, at = 0, es = 0; for (const b of bl) { sozluk += b.sozluk.size; bayt += b.bayt; } const ilk = []; for (const s of SORGULAR) { const c = ara(bl, s); sa += c.sozlukAramasi; tar += c.taranan; at += c.atilan; es += c.eslesen; ilk.push(c.ilkK); } ilkOn.set(ad, ilk); console.log(ad.padEnd(15), String(bl.length).padStart(5), String(sozluk).padStart(14), String(bayt).padStart(11), String(sa).padStart(15), String(tar).padStart(8), String(at).padStart(7), String(es).padStart(8)); } console.log('\nilk on sonuç, tek bölütlü dizilime göre (5 sorgu, 50 basamak)'); console.log('dizilim ilk ondan çıkan basamağı oynayan ilk sırası değişen sorgu'); const temel = ilkOn.get('tek bölüt'); for (const [ad, ilk] of ilkOn) { let cikan = 0, oynayan = 0, bas = 0; for (let q = 0; q < SORGULAR.length; q++) { const t = temel[q], y = ilk[q]; for (const id of t) if (!y.includes(id)) cikan++; for (let i = 0; i < t.length; i++) if (y[i] !== t[i]) oynayan++; if (y[0] !== t[0]) bas++; } console.log(ad.padEnd(15), String(cikan).padStart(15), String(oynayan).padStart(17), String(bas).padStart(25)); } ``` ``` derlem: 12000 belge, tohum 20260731 | 300 belgelik 40 parti + 6 düzeltme partisi dizilim bölüt sözlük girişi dizin bayt sözlük araması taranan atılan eşleşen birleştirme yok 46 33098 3193775 644 26336 3434 18775 beş bölüt 5 6458 2587395 70 22902 0 18775 tek bölüt 1 1364 2552007 14 22902 0 18775 ilk on sonuç, tek bölütlü dizilime göre (5 sorgu, 50 basamak) dizilim ilk ondan çıkan basamağı oynayan ilk sırası değişen sorgu birleştirme yok 12 42 1 beş bölüt 14 37 2 tek bölüt 0 0 0 ``` Birinci sütun ikisinin de kaynağıdır. Derlemde 1.364 ayrı terim vardır; kırk altı bölüte dağılmış hâlde sözlük **33.098 giriş** tutar. Aynı terim her bölütte yeniden yazılıdır, çünkü her bölüt kendi başına aranabilir olmak zorundadır. Bu, dizin boyutunun 2.552.007 bayttan 3.193.775 bayta çıkmasının başlıca nedenidir: yüzde 25 fazla yer, aynı veri için. Sorgu tarafında iki ayrı maliyet vardır. **Sözlük araması** bölüt sayısıyla doğrusal artar: on dört terimlik sorgu kümesi tek bölütte 14 arama yaparken kırk altı bölütte 644 arama yapar. Bu, arama başına ödenen sabit maliyettir ve gönderi listeleri boş çıksa bile ödenir. **Taranan giriş** ise 22.902'den 26.336'ya çıkar; aradaki 3.434 giriş, silme işareti almış eski kopyaların gönderi listelerinde durmayı sürdüren kayıtlarıdır. Bunlar taranır, puanlanmadan atılır ve tarama işini yine de yaptırır. Son sütun kararın en önemli tarafını gösterir: **eşleşen belge sayısı üç dizilimde de 18.775**. Bölüt sayısı kümeyi değiştirmez; silinen kopyalar süzüldüğü için yanıt aynı yanıttır. Değişen sıradır. Kırk altı bölütlü dizilimde ilk on sonucun elli basamağının **42'si** tek bölütlü dizilimden farklı bir belge taşır ve on iki belge ilk ondan bütünüyle düşer. Nedeni AK10'dur: her bölüt ters belge sıklığını yalnızca kendi 300 belgesine bakarak hesaplar, dolayısıyla aynı terim bir bölütte nadir, ötekinde sıradan görünür. Beş bölütlü ara dizilim bu bozulmayı tam olarak düzeltmez — bu satırda ilk ondan çıkan belge sayısı 46 bölütlü dizilimden bir tık yüksektir. Küresel istatistik ancak bütün bölütler tek bölüte indiğinde ortaya çıkar; birleştirme sırayı yavaşça düzeltmez, eşiği geçtiğinde düzeltir. ## Birleştirme Politikasının İki Ayarı Birleştirme kararı elle verilmez; bir politika sürekli çalışır. Katmanlı politika bölütleri boyutuna göre katmanlara koyar: aynı katmanda **çarpan** kadar bölüt birikince hepsi tek bölüte indirilir ve sonuç bir üst katmana yerleşir. Çarpan tek ayardır. Aynı kırk altı parti iki çarpanla oynatılır. ```js // politika.mjs — katmanlı birleştirme politikasının iki ayarı: çarpan 3 ve çarpan 10 import { ara, yiginKur } from './derlem.mjs'; const SORGULAR = [ ['çocuk', 'edebiyatı', 'kısa', 'öykü'], ['yitik', 'kapı'], ['kütüphane', 'bellek', 'yolculuk'], ['deniz', 'ada', 'yağmur'], ['polisiye', 'kent'], ]; console.log('aynı 46 parti, aynı tohum: 12000 belge, tohum 20260731'); console.log('çarpan birleştirme kopyalanan bayt ortalama bölüt son bölüt dizin bayt sözlük araması taranan'); for (const carpan of [3, 10]) { const y = yiginKur(carpan); let bayt = 0, sa = 0, tar = 0; for (const b of y.bolutler) bayt += b.bayt; for (const s of SORGULAR) { const c = ara(y.bolutler, s); sa += c.sozlukAramasi; tar += c.taranan; } console.log(String(carpan).padStart(6), String(y.birlestirme).padStart(12), String(y.kopyalanan).padStart(16), y.ortalama.toFixed(1).padStart(15), String(y.bolutler.length).padStart(10), String(bayt).padStart(11), String(sa).padStart(15), String(tar).padStart(8)); } ``` ``` aynı 46 parti, aynı tohum: 12000 belge, tohum 20260731 çarpan birleştirme kopyalanan bayt ortalama bölüt son bölüt dizin bayt sözlük araması taranan 3 21 15355451 3.3 4 2922192 56 25934 10 4 5342633 6.3 10 3009648 140 26336 ``` İki ayar arasındaki fark sorgu tarafında ölçülüdür ama küçüktür: sözlük araması 140'tan 56'ya iner, taranan giriş 26.336'dan 25.934'e. Dizin boyutu 3.009.648 bayttan 2.922.192 bayta düşer. Arka planda ödenen fark ise büyüktür: çarpan 3 yirmi bir birleştirme yapıp **15.355.451 bayt** kopyalar, çarpan 10 dört birleştirmeyle 5.342.633 bayt. Ölçüyü bir orana çevirmek ayrımı keskinleştirir. Çarpan 3, sonunda 2,9 MB tutan bir dizin için 15,4 MB okuyup yazar: **yazma büyütmesi 5,25 kat**. Çarpan 10 için aynı oran 1,78 kattır. Bu, birleştirmenin gerçek ödünleşimidir. Toplu dizinlemenin kazandırdığı yazma verimi, arka planda çalışan birleştirme tarafından geri alınabilir; parti başına yazılan bayt azken kopyalanan bayt üç katına çıkabilir. Aynı diski ve aynı kanalı hem gelen partiler hem birleştirme kullanır. Çarpanı düşürmek sorguyu biraz hızlandırır, dizini biraz küçültür ve arka plan yükünü üçe katlar; sorgu maliyetinin asıl düşüşü, birinci ölçümdeki 644'ten 140'a inişte, yani birleştirmenin **hiç yapılmaması ile yapılması** arasında gerçekleşmiştir. ## Özet - Her toplu iş bir bölüt bırakır; bölüt değişmez olduğu için silinen belge yerinde kalır ve yalnız bir silme işareti alır. - Kırk altı bölütte sözlük 33.098 giriş tutar, tek bölütte 1.364; aynı veri için dizin 3.193.775 bayttan 2.552.007 bayta iner. - Bölüt sayısı kümeyi değiştirmez (üç dizilimde de 18.775 eşleşen belge), sırayı değiştirir: ilk on sonucun elli basamağının 42'si tek bölütlü dizilimden farklıdır, çünkü her bölüt ters belge sıklığını kendi 300 belgesiyle hesaplar. - Birleştirme 3.434 silme işaretli girişi tarama işinden çıkarır ve sözlük aramasını 644'ten 14'e indirir. - Katmanlı politikada çarpan 3, çarpan 10'a göre sözlük aramasını 140'tan 56'ya indirir ama kopyalanan baytı 5,3 MB'tan 15,4 MB'a çıkarır: yazma büyütmesi 1,78 kattan 5,25 kata çıkar. ## Sonraki Adım Birleştirme bölüt sayısını denetler, ama dizinin **büyümesini** denetlemez. Ölçümdeki 12.000 kayıt sabit bir katalogdur; sürekli yeni kayıt akan bir dizinde birleştirme her seferinde daha büyük bir bölütü yeniden kopyalar ve eski veriyi silmenin bedeli de aynı kopyalamaya bağlanır. Sonraki ders dizini tek bir sonsuz büyüyen nesne olmaktan çıkarır: belirli bir eşikte yeni bir dizine devretmek, sorgunun kaç dizine gitmesi gerektiğini ve eski veriyi silmenin kaç bayta mal olduğunu değiştirir. Ölçülecek olan, zamana göre devretmenin sorgu kapsamına etkisi, tek büyük dizinde belge silmek ile dizin düşürmek arasındaki maliyet farkı ve sıcak–ılık–soğuk katman yerleşiminin bellekte tuttuğu kaynaktır.