Which is the common data structure to implement a relational database?
Answer: Relational databases commonly uses B-tree indexes for data retrieval.
Time Complexity of B-Tree:
| Sr. No. | Algorithm | Time Complexity |
| 1 | Add | O(log n) |
| 1 | Delete | O(log n) |
| 2 | Search | O(log n) |
C++ Program to implement B-tree
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 |
// B Tree is the Common data structure to implement relational database #include<iostream> using namespace std; struct BTree//node declaration { int *d; BTree **derived_Pointer; bool l; int n; }*r = NULL, *New_Pointer = NULL, *x = NULL; BTree* init()//creation of node { int i; New_Pointer = new BTree; New_Pointer->d = new int[6];//order 6 New_Pointer->derived_Pointer = new BTree *[7]; New_Pointer->l = true; New_Pointer->n = 0; for (i = 0; i < 7; i++) { New_Pointer->derived_Pointer[i] = NULL; } return New_Pointer; } void traversal_of_B_Tree(BTree *p)//traversal_of_B_Tree { cout<<endl<<endl;; int i; for (i = 0; i < p->n; i++) { if (p->l == false) { traversal_of_B_Tree(p->derived_Pointer[i]); } cout << " " << p->d[i]; } if (p->l == false) { traversal_of_B_Tree(p->derived_Pointer[i]); } cout<<endl<<endl;; } void sort(int *p, int n)//sorting the B tree { int i, j, t; for (i = 0; i < n; i++) { for (j = i; j <= n; j++) { if (p[i] >p[j]) { t = p[i]; p[i] = p[j]; p[j] = t; } } } } int Child_Division(BTree *x, int i) { int j, mid; BTree *New_Pointer1, *New_Pointer3, *y; New_Pointer3 = init();//create new node New_Pointer3->l = true; if (i == -1) { mid = x->d[2];//find mid x->d[2] = 0; x->n--; New_Pointer1 = init(); New_Pointer1->l= false; x->l= true; for (j = 3; j < 6; j++) { New_Pointer3->d[j - 3] = x->d[j]; New_Pointer3->derived_Pointer[j - 3] = x->derived_Pointer[j]; New_Pointer3->n++; x->d[j] = 0; x->n--; } for (j = 0; j < 6; j++) { x->derived_Pointer[j] = NULL; } New_Pointer1->d[0] = mid; New_Pointer1->derived_Pointer[New_Pointer1->n] = x; New_Pointer1->derived_Pointer[New_Pointer1->n + 1] = New_Pointer3; New_Pointer1->n++; r = New_Pointer1; } else { y = x->derived_Pointer[i]; mid = y->d[2]; y->d[2] = 0; y->n--; for (j = 3; j <6 ; j++) { New_Pointer3->d[j - 3] = y->d[j]; New_Pointer3->n++; y->d[j] = 0; y->n--; } x->derived_Pointer[i + 1] = y; x->derived_Pointer[i + 1] = New_Pointer3; } return mid; } void insert(int a) { int i, t; x = r; if (x == NULL) { r = init(); x = r; } else { if (x->l== true && x->n == 6) { t = Child_Division(x, -1); x = r; for (i = 0; i < (x->n); i++) { if ((a >x->d[i]) && (a < x->d[i + 1])) { i++; break; } else if (a < x->d[0]) { break; } else { continue; } } x = x->derived_Pointer[i]; } else { while (x->l == false) { for (i = 0; i < (x->n); i++) { if ((a >x->d[i]) && (a < x->d[i + 1])) { i++; break; } else if (a < x->d[0]) { break; } else { continue; } } if ((x->derived_Pointer[i])->n == 6) { t = Child_Division(x, i); x->d[x->n] = t; x->n++; continue; } else { x = x->derived_Pointer[i]; } } } } x->d[x->n] = a; sort(x->d, x->n); x->n++; } int main() { int i, n, t; cout<<"Please tell that how much elements you want to insert?\n"; cin>>n; for(i = 0; i < n; i++) { cout<<"Please enter the element:n"; cin>>t; insert(t); } cout<<"The traversal of constructed B tree is:\n"; traversal_of_B_Tree(r); } |
Output
Please tell that how much elements you want to insert?2
Please enter the element: 3
Please enter the element: 4
The traversal of constructed B tree is:
3 4
