- This is default index for CRTLF command and CREATE INDEX statement.
- It uses the Radix tree data structure.
- The radix tree data structure is a compressed version of the digital tree also called Trie (try) data structure.
There are the main terms in action here
1. Binary tree data structure
2. Trie data structure
3. Radix tree data structure
Binary tree data structure:(Google for more details)
1. It’s a tree data structure where each node can have maximum 2 child nodes.
a. Simple called left node and the right node
2. This structure is arranged in such a way that the value of left child node is less than the value parent node and value of right child node is greater than or equal to the value of parent node.
3. If use Binary search algorithm to look find a match.
Something like this
More details here.
Trie data structure
- It’s a tree-like data structure.
- Each node represents a step or a try towards the required match.
- Its root node is always empty.
- Each node can contain any number of child nodes.
- Right node always contains bigger value than its sibling left node.
For example, let say we have following string key values
In this case, Trie data structure uses individual characters from each string to make sure that a value can be retrieved from the data structure by reading a single branch starting from top node.
So, these values will be represented in this way
Here is how this data structure find a value
- Find “RED”
- Find “CORN”
There is one more term in play here that is “redundant nodes”. Any node with just a single child is called a redundant node. For example, from the branch for the key “APPLE” node A is a redundant node.
Why the redundant nodes matter?
We have only one key starting with letter A. And still, we created 5 nodes to represent a single value and data structure have to take 6 steps to find the match.
Here are other redundant nodes
Radix Tree Data structure(Not the Binary-Radix index).
As I said earlier “Radix tree data structure is a compressed version of Trie (try) data structure.”
So, it compresses these redundant nodes it can save a lot of space and steps to find the final match.
For example, if we compress the five nodes for key “APPLE” into a single node for string “APPLE” it will save a lot of space and step to find the match and that’s what Radix tree does.
So, for the same set of keys, Radix tree will look like this:
- All the redundant nodes are compressed to make a single node.
- Like Trie data structure, one node can have any number of child nodes.
Back to the Binary-Radix Index.
- It’s a mix of Binary Tree and Radix tree
- Each node can have maximum 2 child nodes. Simply called the left child and right child.
- It uses the Binary search algorithm to find a match.
Let say data in the table looks something like this
Now if you search for key = ”RUSH”
- This data structure will go through following nodes
- And will return the RRN = 6.
- Now RDBMS can quickly find a record in the table with RRN and return the all required columns.
- Nodes also contain some metadata.
- Access path maintenance all about rearranging this tree to reflect the changes in the base table.