Podcast
Questions and Answers
What happens to a B+ tree when a leaf node is split during an insert operation?
What happens to a B+ tree when a leaf node is split during an insert operation?
- The tree decreases in height.
- New nodes are created in all levels of the tree.
- An element is added to the root. (correct)
- The tree remains unchanged.
Which of the following actions can be taken if a delete operation causes a node to have low occupancy?
Which of the following actions can be taken if a delete operation causes a node to have low occupancy?
- Always merge the node with a parent node.
- Insert a new node to fill the vacancy.
- Borrow from the nearest sibling node. (correct)
- Remove the node's parent.
What is a potential outcome of deleting a key from a B+ tree?
What is a potential outcome of deleting a key from a B+ tree?
- The minimum number of keys in a node is always maintained.
- The tree structure always remains unchanged.
- The height of the tree increases dramatically.
- The tree may become smaller and more efficient. (correct)
After deleting elements from a B+ tree, what should be done if the tree needs to maintain its balance?
After deleting elements from a B+ tree, what should be done if the tree needs to maintain its balance?
What does it mean for a B+ tree to 'grow wider and deeper' after an insert operation?
What does it mean for a B+ tree to 'grow wider and deeper' after an insert operation?
Which type of file organization allows for efficient range searches?
Which type of file organization allows for efficient range searches?
What is the primary function of indexes in a database?
What is the primary function of indexes in a database?
When inserting a value into a B-tree index, what happens if there is not enough space at the leaf level?
When inserting a value into a B-tree index, what happens if there is not enough space at the leaf level?
What type of query would benefit most from the use of an index?
What type of query would benefit most from the use of an index?
Which statement best describes heap files in the context of databases?
Which statement best describes heap files in the context of databases?
What is the primary drawback of using heap files for data organization?
What is the primary drawback of using heap files for data organization?
What happens to a B-tree when a new key is inserted and the existing leaf node is full?
What happens to a B-tree when a new key is inserted and the existing leaf node is full?
Which aspect of database organization optimizes search speed and allows for fast updates?
Which aspect of database organization optimizes search speed and allows for fast updates?
Flashcards
Database Indexing
Database Indexing
Data structures that speed up data retrieval by providing a way to quickly locate specific data within a database.
Heap Files
Heap Files
Files that store data in no particular order; searching requires looking at every record.
Sorted Files
Sorted Files
Files where data is ordered based on a specific column, which allows for faster range searches.
Index Creation
Index Creation
Signup and view all the flashcards
Index Maintenance
Index Maintenance
Signup and view all the flashcards
Tree-based Indexes
Tree-based Indexes
Signup and view all the flashcards
Index Splitting
Index Splitting
Signup and view all the flashcards
Index Node Occupation
Index Node Occupation
Signup and view all the flashcards
B+ Tree Insert
B+ Tree Insert
Signup and view all the flashcards
B+ Tree Split
B+ Tree Split
Signup and view all the flashcards
B+ Tree Delete
B+ Tree Delete
Signup and view all the flashcards
B+ Tree Borrowing
B+ Tree Borrowing
Signup and view all the flashcards
B+ Tree Merging
B+ Tree Merging
Signup and view all the flashcards
Study Notes
INF2003: Database Systems - Indexing
- Course: INF2003 Database Systems, Indexing
- Semester: AY24/25 Trimester 1
- Instructor: Zhang Wei, SIT
- Date: Oct. 22, 2024
About the Instructor
- Email: [email protected]
- Website: https://www.singaporetech.edu.sg/directory/faculty/wei-zhang
- Google Homepage: https://sites.google.com/view/sit-zhang-wei/
- PhD in Computer Science from NTU
- Research: applied AI and energy efficiency
- Teaching databases since 2019
- Part of A*STAR database tasks (2017-2019)
- Customized content for different programs (e.g., CS/SE)
- Current course INF2003 harmonized for lower difficulty
- Interested in inter-program collaboration and activities
- Interested in applied learning projects
Course Outline (2nd Half Topics)
- Week 8: Indexing (mainly centralized)
- Week 9: Transactions and Concurrency
- Week 10: NoSQL
- Week 11: Blockchain
- Week 12: Data Warehouse
Files and File Organization
- Database: Consists of one or more tables.
- Table: Contains one or more tuples (rows).
- Data File: Contains data chunks.
- Data Pages: Individual chunks within the data file.
- Query Processing: Database Management Systems (DBMS) determine which data pages contain the requested data.
- File Organization:
- Heap files (random order): Used for scanning all records.
- Sorted files: Used for order-sensitive data retrieval and range queries.
- Indexes: Additional data structures that speed up specific retrievals.
- Index Advantages
- Speed up search
- Speed up updates
Discussion Points
- SQL Query Examples:
SELECT * FROM Students;Basic querySELECT * FROM Students WHERE sid = 2001234;Query by student IDSELECT * FROM Students WHERE year >= 2013 AND year <= 2015;Query by year range
- Indexing and Query Speed: Certain queries can be substantially faster when indexes are used.
- Index Creation: Creating appropriate indexes can significantly improve query performance.
Index Data Structure - Hash
- Index: Collection of buckets (possibly with overflow pages).
- Buckets: Contain data entries.
- Hash Function (h): Same for all records, maps record's key to a specific bucket. h(r) = bucket for record r.
- h(r) = Surname
- Suitable for equality search only.
- Potential Issues: Multiple records in the same bucket, one record in different buckets.
Index Data Structure - Tree
- Hash: Primarily equality search.
- Tree: Both equality and range searches are supported
- Structure: Hierarchical (non-flat)
- B+ tree: Most popular tree-based index structure.
B+ Tree: Basic Elements
- Root: Topmost node of the tree.
- Internal Nodes: Nodes that store keys and pointers to child nodes.
- Leaves: Nodes that store data entries.
- High Fanout: Typically a large number of pointers to child nodes (e.g., 100 or more) for fast navigation.
- Philosophy: All data located in leaf nodes and all leaves on same level.
- Balance: The tree is balanced ensuring all leaf nodes at the same depth.
B+ Tree: Search, Insert and Delete
- Search: A series of comparisons that operate in O(log n) time.
- Insert:
- Locate insertion place in leaf node
- If space available, insert value.
- Otherwise, split leaf node and propagate changes up the tree.
- May require splitting parent nodes also
- Delete:
- Locate item.
- If low occupancy in leaf, borrow from neighboring node.
- Merge if borrowing not possible.
- Propagation up tree to root if necessary
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
