Hafta 14 — Dosya Organizasyonu II: Dizinler, B-Ağaçları, Genişleyebilir Hashleme ve Dosya Sıralama¶

/* Week 14 -- File Organisation II
 * Primary (sparse) index over a sorted file: one index entry per disk page.
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdbool.h>
#include <stdio.h>

#define MAX_PAGES 8
#define MAX_BLOCK 16

typedef struct {
    int first_key;
    int page;
} IndexEntry;

int find_page(IndexEntry index[], int idx_n, int key) {
    int page = -1;
    for (int i = 0; i < idx_n; i++) {
        if (index[i].first_key <= key)
            page = index[i].page; /* keep the last entry that still fits */
        else
            break; /* index is sorted: later entries start too high */
    }
    return page;
}

bool search_key(int data[][MAX_BLOCK], const int page_len[], IndexEntry index[], int idx_n,
                 int key, int *out_page) {
    int page = find_page(index, idx_n, key);
    if (page == -1)
        return false; /* smaller than every key: guaranteed absent */
    for (int i = 0; i < page_len[page]; i++)
        if (data[page][i] == key) {
            *out_page = page;
            return true;
        }
    *out_page = page;
    return false;
}

static void run_scenario(const char *label, const int keys[], int n, int block, const int queries[], int qn) {
    printf("-- %s --\n", label);
    int data[MAX_PAGES][MAX_BLOCK];
    int page_len[MAX_PAGES];
    IndexEntry index[MAX_PAGES];
    int pages = 0;

    for (int i = 0; i < n; i += block) {
        int len = 0;
        for (int j = i; j < i + block && j < n; j++)
            data[pages][len++] = keys[j];
        page_len[pages] = len;
        index[pages].first_key = data[pages][0];
        index[pages].page = pages;
        pages++;
    }

    printf("pages: %d\n", pages);
    for (int p = 0; p < pages; p++) {
        printf("  page %d:", p + 1);
        for (int i = 0; i < page_len[p]; i++)
            printf(" %d", data[p][i]);
        printf("\n");
    }
    for (int q = 0; q < qn; q++) {
        int out_page = -1;
        bool found = search_key(data, page_len, index, pages, queries[q], &out_page);
        if (out_page == -1)
            printf("search(%d) -> not found (below the first key, no page read)\n", queries[q]);
        else
            printf("search(%d) -> %s (page %d)\n", queries[q], found ? "found" : "not found", out_page + 1);
    }
    printf("\n");
}

int main(void) {
    const int normal_keys[] = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60};
    const int normal_q[] = {22, 50, 3};
    run_scenario("normal: 12 keys, block=4", normal_keys, 12, 4, normal_q, 3);

    const int hard_keys[] = {2, 8, 14, 19, 23, 29, 34, 41, 47, 53, 58, 64, 69, 75, 81, 88};
    const int hard_q[] = {29, 75, 90, 1, 88};
    run_scenario("hard: 16 keys, block=3, partial last page", hard_keys, 16, 3, hard_q, 5);

    const int single_keys[] = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30};
    const int single_q[] = {9, 25, 1};
    run_scenario("edge: single page, block=12", single_keys, 10, 12, single_q, 3);

    const int below_keys[] = {100, 105, 110, 115, 120, 125, 130, 135, 140, 145, 150, 155};
    const int below_q[] = {10, 50, 99};
    run_scenario("edge: every query below range, block=4", below_keys, 12, 4, below_q, 3);
    return 0;
}

/* Week 14 -- File Organisation II
 * Primary (sparse) index over a sorted file: one index entry per disk page.
 * CEN207 Data Structures (formerly CE205)
 */
public class PrimaryIndex {
    static final int MAX_PAGES = 8;
    static final int MAX_BLOCK = 16;

    static class IndexEntry {
        int firstKey;
        int page;
    }

    static int findPage(IndexEntry[] index, int idxN, int key) {
        int page = -1;
        for (int i = 0; i < idxN; i++) {
            if (index[i].firstKey <= key)
                page = index[i].page; // keep the last entry that still fits
            else
                break; // index is sorted: later entries start too high
        }
        return page;
    }

    static boolean searchKey(int[][] data, int[] pageLen, IndexEntry[] index, int idxN,
                              int key, int[] outPage) {
        int page = findPage(index, idxN, key);
        if (page == -1)
            return false; // smaller than every key: guaranteed absent
        for (int i = 0; i < pageLen[page]; i++)
            if (data[page][i] == key) {
                outPage[0] = page;
                return true;
            }
        outPage[0] = page;
        return false;
    }

    static void runScenario(String label, int[] keys, int block, int[] queries) {
        System.out.println("-- " + label + " --");
        int[][] data = new int[MAX_PAGES][MAX_BLOCK];
        int[] pageLen = new int[MAX_PAGES];
        IndexEntry[] index = new IndexEntry[MAX_PAGES];
        int pages = 0;

        for (int i = 0; i < keys.length; i += block) {
            int len = 0;
            for (int j = i; j < i + block && j < keys.length; j++)
                data[pages][len++] = keys[j];
            pageLen[pages] = len;
            index[pages] = new IndexEntry();
            index[pages].firstKey = data[pages][0];
            index[pages].page = pages;
            pages++;
        }

        System.out.println("pages: " + pages);
        for (int p = 0; p < pages; p++) {
            StringBuilder sb = new StringBuilder("  page " + (p + 1) + ":");
            for (int i = 0; i < pageLen[p]; i++)
                sb.append(' ').append(data[p][i]);
            System.out.println(sb);
        }
        for (int q : queries) {
            int[] outPage = {-1};
            boolean found = searchKey(data, pageLen, index, pages, q, outPage);
            if (outPage[0] == -1)
                System.out.println("search(" + q + ") -> not found (below the first key, no page read)");
            else
                System.out.println("search(" + q + ") -> " + (found ? "found" : "not found") + " (page " + (outPage[0] + 1) + ")");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] normalKeys = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60};
        int[] normalQ = {22, 50, 3};
        runScenario("normal: 12 keys, block=4", normalKeys, 4, normalQ);

        int[] hardKeys = {2, 8, 14, 19, 23, 29, 34, 41, 47, 53, 58, 64, 69, 75, 81, 88};
        int[] hardQ = {29, 75, 90, 1, 88};
        runScenario("hard: 16 keys, block=3, partial last page", hardKeys, 3, hardQ);

        int[] singleKeys = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30};
        int[] singleQ = {9, 25, 1};
        runScenario("edge: single page, block=12", singleKeys, 12, singleQ);

        int[] belowKeys = {100, 105, 110, 115, 120, 125, 130, 135, 140, 145, 150, 155};
        int[] belowQ = {10, 50, 99};
        runScenario("edge: every query below range, block=4", belowKeys, 4, belowQ);
    }
}

/* Week 14 -- File Organisation II
 * Dense secondary index: one index entry per RECORD, sorted by a key that repeats.
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdio.h>
#include <stdlib.h>

#define MAX_RECORDS 16

typedef struct {
    int key;
    int slot;
} IndexEntry;

/* Search a dense, sorted index for every record whose key matches; matching entries cluster
 * together because the index is sorted, so a single pass collects them all. */
int search_dense(const IndexEntry index[], int n, int key, int matches[], int max_matches) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (index[i].key == key) {
            if (count < max_matches)
                matches[count] = index[i].slot; /* remember which record matched */
            count++;
        } else if (count > 0) {
            break; /* dense + sorted: matches always cluster together */
        }
    }
    return count;
}

static int cmp_entry(const void *a, const void *b) {
    const IndexEntry *ea = a, *eb = b;
    if (ea->key != eb->key)
        return ea->key - eb->key;
    return ea->slot - eb->slot;
}

static void run_scenario(const char *label, const int keys[], int n, int block, const int queries[], int qn) {
    printf("-- %s --\n", label);
    printf("records: %d, block=%d\n", n, block);

    IndexEntry index[MAX_RECORDS];
    for (int i = 0; i < n; i++) {
        index[i].key = keys[i];
        index[i].slot = i;
    }
    qsort(index, (size_t) n, sizeof(IndexEntry), cmp_entry);

    for (int q = 0; q < qn; q++) {
        int matches[MAX_RECORDS];
        int count = search_dense(index, n, queries[q], matches, MAX_RECORDS);
        printf("search(%d) -> %d match(es):", queries[q], count);
        for (int i = 0; i < count; i++) {
            int slot = matches[i];
            printf(" page%d.slot%d", slot / block + 1, slot % block);
        }
        printf("\n");
    }
    printf("\n");
}

int main(void) {
    const int normal_keys[] = {3, 1, 4, 1, 2, 3, 1, 4, 2, 3, 1, 4};
    const int normal_q[] = {1, 5, 4};
    run_scenario("normal: 12 records, block=4", normal_keys, 12, 4, normal_q, 3);

    const int hard_keys[] = {2, 5, 1, 3, 5, 4, 1, 5, 2, 3, 5, 1, 4, 2};
    const int hard_q[] = {5, 9, 4};
    run_scenario("hard: 14 records, block=3", hard_keys, 14, 3, hard_q, 3);

    const int same_keys[] = {7, 7, 7, 7, 7, 7, 7, 7, 7, 7};
    const int same_q[] = {7, 3};
    run_scenario("edge: all 10 records share one key", same_keys, 10, 4, same_q, 2);

    const int unique_keys[] = {40, 10, 30, 20, 50, 15, 25, 35, 45, 5};
    const int unique_q[] = {30, 99, 5};
    run_scenario("edge: no duplicate keys", unique_keys, 10, 5, unique_q, 3);
    return 0;
}

/* Week 14 -- File Organisation II
 * Dense secondary index: one index entry per RECORD, sorted by a key that repeats.
 * CEN207 Data Structures (formerly CE205)
 */
import java.util.Arrays;
import java.util.Comparator;

public class SecondaryIndex {
    static final int MAX_RECORDS = 16;

    static class IndexEntry {
        int key;
        int slot;
        IndexEntry(int key, int slot) { this.key = key; this.slot = slot; }
    }

    // Search a dense, sorted index for every record whose key matches; matching entries cluster
    // together because the index is sorted, so a single pass collects them all.
    static int searchDense(IndexEntry[] index, int n, int key, int[] matches, int maxMatches) {
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (index[i].key == key) {
                if (count < maxMatches)
                    matches[count] = index[i].slot; // remember which record matched
                count++;
            } else if (count > 0) {
                break; // dense + sorted: matches always cluster together
            }
        }
        return count;
    }

    static void runScenario(String label, int[] keys, int block, int[] queries) {
        System.out.println("-- " + label + " --");
        System.out.println("records: " + keys.length + ", block=" + block);

        IndexEntry[] index = new IndexEntry[keys.length];
        for (int i = 0; i < keys.length; i++)
            index[i] = new IndexEntry(keys[i], i);
        Arrays.sort(index, Comparator.<IndexEntry>comparingInt(e -> e.key).thenComparingInt(e -> e.slot));

        for (int q : queries) {
            int[] matches = new int[MAX_RECORDS];
            int count = searchDense(index, keys.length, q, matches, MAX_RECORDS);
            StringBuilder sb = new StringBuilder("search(" + q + ") -> " + count + " match(es):");
            for (int i = 0; i < count; i++) {
                int slot = matches[i];
                sb.append(" page").append(slot / block + 1).append(".slot").append(slot % block);
            }
            System.out.println(sb);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] normalKeys = {3, 1, 4, 1, 2, 3, 1, 4, 2, 3, 1, 4};
        int[] normalQ = {1, 5, 4};
        runScenario("normal: 12 records, block=4", normalKeys, 4, normalQ);

        int[] hardKeys = {2, 5, 1, 3, 5, 4, 1, 5, 2, 3, 5, 1, 4, 2};
        int[] hardQ = {5, 9, 4};
        runScenario("hard: 14 records, block=3", hardKeys, 3, hardQ);

        int[] sameKeys = {7, 7, 7, 7, 7, 7, 7, 7, 7, 7};
        int[] sameQ = {7, 3};
        runScenario("edge: all 10 records share one key", sameKeys, 4, sameQ);

        int[] uniqueKeys = {40, 10, 30, 20, 50, 15, 25, 35, 45, 5};
        int[] uniqueQ = {30, 99, 5};
        runScenario("edge: no duplicate keys", uniqueKeys, 5, uniqueQ);
    }
}

/* Week 14 -- File Organisation II
 * ISAM: a two-level index over a sorted primary data area, plus an overflow area
 * (a linked chain) for keys that no longer fit their home page.
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdio.h>
#include <stdlib.h>

#define MAX_PAGES 8
#define MAX_BLOCK 8
#define MAX_GROUPS 8

typedef struct OverflowNode {
    int key;
    struct OverflowNode *next;
} OverflowNode;

typedef struct {
    int keys[MAX_BLOCK]; /* holds up to BLOCK keys: the page's capacity */
    int len;              /* how many of those slots are currently used */
    OverflowNode *overflow_head;
    OverflowNode *overflow_tail;
} Page;

int find_group(const int l1_key[], int l1_n, int key) {
    int g = 0;
    for (int i = 0; i < l1_n; i++) {
        if (l1_key[i] <= key)
            g = i;
        else
            break;
    }
    return g;
}

int find_page(const int l2_key[], int lo, int hi, int key) {
    int page = lo;
    for (int i = lo; i <= hi; i++) {
        if (l2_key[i] <= key)
            page = i;
        else
            break;
    }
    return page;
}

/* block = a page's CAPACITY (how many keys it can hold before it overflows). */
static void isam_insert(Page pages[], int num_pages, int block, const int l1_key[], int l1_n,
                         int group, int key) {
    int g = find_group(l1_key, l1_n, key);
    int lo = g * group, hi = lo + group - 1;
    if (hi > num_pages - 1)
        hi = num_pages - 1;
    int l2_key[MAX_PAGES];
    for (int i = 0; i < num_pages; i++)
        l2_key[i] = pages[i].keys[0];
    int page = find_page(l2_key, lo, hi, key);

    if (pages[page].len < block) {
        int i = pages[page].len - 1;
        while (i >= 0 && pages[page].keys[i] > key) {
            pages[page].keys[i + 1] = pages[page].keys[i];
            i--;
        }
        pages[page].keys[i + 1] = key;
        pages[page].len++;
        printf("insert(%d) -> page %d (%d/%d)\n", key, page + 1, pages[page].len, block);
    } else {
        OverflowNode *node = malloc(sizeof *node);
        node->key = key;
        node->next = NULL;
        if (pages[page].overflow_tail == NULL)
            pages[page].overflow_head = node;
        else
            pages[page].overflow_tail->next = node;
        pages[page].overflow_tail = node;
        printf("insert(%d) -> page %d is full: OVERFLOW\n", key, page + 1);
    }
}

static void print_pages(const Page pages[], int num_pages) {
    for (int p = 0; p < num_pages; p++) {
        printf("  page %d:", p + 1);
        for (int i = 0; i < pages[p].len; i++)
            printf(" %d", pages[p].keys[i]);
        if (pages[p].overflow_head != NULL) {
            printf("  overflow:");
            for (OverflowNode *n = pages[p].overflow_head; n != NULL; n = n->next)
                printf(" %d", n->key);
        }
        printf("\n");
    }
}

static void free_overflow(Page pages[], int num_pages) {
    for (int p = 0; p < num_pages; p++) {
        OverflowNode *n = pages[p].overflow_head;
        while (n != NULL) {
            OverflowNode *next = n->next;
            free(n);
            n = next;
        }
    }
}

/* fill = keys per page when the file is first built (fill <= block, leaving block-fill free slots). */
static void run_scenario(const char *label, const int keys[], int n, int block, int fill, int group,
                          const int inserts[], int in_n) {
    printf("-- %s --\n", label);
    Page pages[MAX_PAGES];
    int num_pages = 0;
    for (int i = 0; i < n; i += fill) {
        int len = 0;
        for (int j = i; j < i + fill && j < n; j++)
            pages[num_pages].keys[len++] = keys[j];
        pages[num_pages].len = len;
        pages[num_pages].overflow_head = NULL;
        pages[num_pages].overflow_tail = NULL;
        num_pages++;
    }
    int l1_key[MAX_GROUPS];
    int l1_n = 0;
    for (int g = 0; g * group < num_pages; g++)
        l1_key[l1_n++] = pages[g * group].keys[0];

    printf("pages: %d (fill=%d, capacity=%d), level-1 groups: %d\n", num_pages, fill, block, l1_n);
    for (int i = 0; i < in_n; i++)
        isam_insert(pages, num_pages, block, l1_key, l1_n, group, inserts[i]);
    print_pages(pages, num_pages);
    free_overflow(pages, num_pages);
    printf("\n");
}

int main(void) {
    const int normal_keys[] = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60};
    const int normal_ins[] = {22, 38, 39};
    run_scenario("normal: 12 keys, block=4, fill=3 (1 overflow)", normal_keys, 12, 4, 3, 2, normal_ins, 3);

    const int hard_keys[] = {2, 8, 14, 19, 23, 29, 34, 41, 47, 53, 58, 64, 69, 75, 81, 88};
    const int hard_ins[] = {24, 25, 26};
    run_scenario("hard: 16 keys, block=4, fill=2, chained overflow", hard_keys, 16, 4, 2, 3, hard_ins, 3);

    const int no_of_keys[] = {4, 9, 14, 19, 24, 29, 34, 39, 44, 49, 54, 59};
    const int no_of_ins[] = {11, 46, 12, 47};
    run_scenario("edge: plenty of free room, no overflow", no_of_keys, 12, 8, 3, 2, no_of_ins, 4);

    const int all_of_keys[] = {10, 12, 20, 22, 30, 32, 40, 42, 50, 52};
    const int all_of_ins[] = {11, 21, 31, 41};
    run_scenario("edge: fill=block=2, every insert overflows", all_of_keys, 10, 2, 2, 3, all_of_ins, 4);
    return 0;
}