{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tutorial 5: Data Indexing - B+ Trees and Extendible Hashing\n",
    "\n",
    "## B+ Tree: Key Concepts\n",
    "\n",
    "- **Internal Nodes**: Non-leaf nodes that guide searches using separator keys\n",
    "- **Keys**: Values used for indexing and searching\n",
    "- **Children**: Nodes that an internal node points to\n",
    "- **Leaf Nodes**: Bottom-level nodes containing actual data or data pointers\n",
    "\n",
    "## Problem 1: B+ Tree Construction and Insertion\n",
    "\n",
    "**Task**: Construct a B+ tree by inserting (1, 3, 5, 7, 9, 2, 4, 6, 8, 10) sequentially, where each node can hold up to 4 pointers.\n",
    "\n",
    "### Step-by-Step Construction:\n",
    "\n",
    "1. Insert 1: Tree: [1]\n",
    "2. Insert 3: Tree: [1, 3]\n",
    "3. Insert 5: Tree: [1, 3, 5]\n",
    "4. Insert 7: Split needed\n",
    " ```\n",
    "Root: [3]\n",
    "Leaves: [1, 3] ---> [5, 7]\n",
    " ```\n",
    "5. Insert 9:\n",
    " ```\n",
    "Root: [3]\n",
    "Leaves: [1, 3] ---> [5, 7, 9]\n",
    " ```\n",
    "6. Insert 2:\n",
    " ```\n",
    "Root: [3]\n",
    "Leaves: [1, 2, 3] ---> [5, 7, 9]\n",
    " ```\n",
    "7. Insert 4, split needed:\n",
    " ```\n",
    "Root: [3, 5]\n",
    "Leaves: [1, 2, 3] ---> [4, 5] ---> [7, 9]\n",
    " ```\n",
    "8. Insert 6:\n",
    " ```\n",
    "Root: [3, 5]\n",
    "Leaves: [1, 2, 3] ---> [4, 5] ---> [6, 7, 9]\n",
    " ```\n",
    "9. Insert 8:\n",
    " ```\n",
    "Root: [3, 5, 7]\n",
    "Leaves: [1, 2, 3] ---> [4, 5] ---> [6, 7] ---> [8, 9]\n",
    " ```\n",
    "10. Insert 10:\n",
    " ```\n",
    " Root: [3, 5, 7]\n",
    " Leaves: [1, 2, 3] ---> [4, 5] ---> [6, 7] ---> [8, 9, 10]\n",
    " ```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 2: B+ Tree Deletion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Starting with our final tree from Problem 1, perform the following deletions:\n",
    "### a) Delete 9\n",
    " ```\n",
    "Root: [3, 5, 7]\n",
    "Leaves: [1, 2, 3] ---> [4, 5] ---> [6, 7] ---> [8, 10]\n",
    " ```\n",
    "### b) Delete 7\n",
    " ```\n",
    "Root: [3, 5, 8]\n",
    "Leaves: [1, 2, 3] ---> [4, 5] ---> [6] ---> [8, 10]\n",
    " ```\n",
    "### c) Delete 8\n",
    "Underflow in the last leaf node leads to redistribution or merging:\n",
    " ```\n",
    "Root: [3, 5]\n",
    "Leaves: [1, 2, 3] ---> [4, 5] ---> [6, 10]\n",
    " ```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 3: Extendible Hashing\n",
    "\n",
    "**Task**: Use extendible hashing with bucket size 3 to hash: 16, 4, 6, 22, 24, 10, 31, 7, 9, 20, 26.\n",
    "The hash function returns X LSBs (Least Significant Bits), where X is the global depth.\n",
    "\n",
    "### Binary Representation:\n",
    "- 16: 10000\n",
    "- 4: 00100\n",
    "- 6: 00110\n",
    "- 22: 10110\n",
    "- 24: 11000\n",
    "- 10: 01010\n",
    "- 31: 11111\n",
    "- 7: 00111\n",
    "- 9: 01001\n",
    "- 20: 10100\n",
    "- 26: 11010\n",
    "\n",
    "### Insertion Process:\n",
    "\n",
    "1. Insert 16, 4, 6:\n",
    " ```\n",
    "Directory: 0 -> [16, 4, 6], 1 -> []\n",
    " ```\n",
    "2. Insert 22 (overflow, split bucket):\n",
    " ```\n",
    "Directory: 00 -> [16, 4], 01 -> [], 10 -> [6, 22], 11 -> []\n",
    " ```\n",
    "3. Insert 24, 10:\n",
    " ```\n",
    "Directory: 00 -> [16, 4, 24], 01 -> [], 10 -> [6, 22, 10], 11 -> []\n",
    " ```\n",
    "4. Insert 31, 7, 9:\n",
    " ```\n",
    "Directory: 00 -> [16, 4, 24], 01 -> [9], 10 -> [6, 22, 10], 11 -> [31, 7]\n",
    " ```\n",
    "5. Insert 20 (overflow, split bucket):\n",
    " ```\n",
    "Directory: 000 -> [16, 24], 001 -> [], 010 -> [9], 011 -> [],\n",
    "100 -> [4, 20], 101 -> [], 110 -> [6, 22, 10], 111 -> [31, 7]\n",
    " ```\n",
    "6. Insert 26:\n",
    " ```\n",
    "Directory: 000 -> [16, 24], 001 -> [], 010 -> [9, 26], 011 -> [],\n",
    "100 -> [4, 20], 101 -> [], 110 -> [6, 22, 10], 111 -> [31, 7]\n",
    " ```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}