Implemented a B+tree based indexing to speed up searching in a relational database resulting in the reduction of search time to log(n) with base d where d is the degree of the B+tree and n is the number of index pages
- Compile Client.java file present in the src folder.
- Run the Client file and pass an empty folder as an argument for the creation of data and indexes.
Add the complete path of the empty folder while running the client file.
- Here you go! The window launches with first page as the home page giving a brief summary about the project.
- Users can create data by switching to the data panel and then enter the number of rows to be created.
Data will be stored in the form of extents.
Extent -> Pages -> Rows
For demonstration purpose, the schema of the table is as : Roll number | Name | Username | Password .
- Users can create Non-Clustered indexing [?] on any attribute of the table from the index panel which has a drop-down list to select the attribute name for the creation of indexes.
- Now, it's time to enjoy the benefits of indexing. Switch to query panel.
Index seek is performed if query is made using the attribute on which indexes are created.
Table scan is performed otherwise. Time taken in table scan is considerably more than that in index seek.
Why Is Indexing Used in the Database?
Imagine you need to store a list of numbers in a file and search a given number on that list. The simplest solution is to store data in an array and append values when new values come. But if you need to check if a given value exists in the array, then you need to search through all of the array elements one by one and check whether the given value exists. If you are lucky enough, you can find the given value in the first element. In the worst case, the value can be the last element in the array. We can denote this worst-case as O(n) in asymptotic notation. This means if your array size is “n,” at most, you need to do “n” number of searches to find a given value in an array. Such type of search is called a Table scan.
B-Tree Indexes
This is the default index for most storage engines in MySql. The general idea of a B-Tree is that all the values are stored in order, and each leaf page is the same distance from the root.
A B-Tree index speeds up data access because the storage engine doesn’t have to scan the whole table to find the desired data. Instead, it starts at the root node. The slots in the root node hold pointers to child nodes, and the storage engine follows these pointers. It finds the right pointer by looking at the values in the node pages, which define the upper and lower bounds of the values in the child nodes. Eventually, the storage engine either determines that the desired value doesn’t exist or successfully reaches a leaf page. Leaf pages are special because they have pointers to the indexed data instead of pointers to other pages.
B+ - Tree Indexes
B+tree is another data structure used to store data, which is almost the same as the B-tree. The only difference of B+tree is that it stores data on the leaf nodes. This means that all non-leaf node values are duplicated in leaf nodes again. Below is a sample B+tree.
