Nowadays, index structures reside in memory in order to avoid accessing the disk and make processes of databases faster. Since size of the memories are big enough nowadays, there is no problem to keep the indexes in memory but in case of bit flip occurrence, we would like to detect them to avoid accessing a part of memory which is not allocated or accessing wrong values. When bit flip happens, bits can change from 0 to 1 or vice versa. Bit flips can happen because of multiple reasons. Sometimes bit flips are transient, so they will go away after a reboot, but sometimes they will not change at all.
The index structure which is going to be explored is prefix tree. In this thesis, parity bits are used for the pointers in the tree in the first step. In the second step, memory allocation for the prefix tree is done in a way, so that locating the nodes is possible through some calculations and any bit flips can be detected by any mismatch between the calculation and the existing pointers. In the third step, prefix tree is implemented in a way to reduce the memory accesses but bit flip detection is done in the same way as in the second step.
Based on the results of these implementations, bit flips can be detected by using parity bits if the number of bit flips on a byte is odd. In the implementations on the second and third step, any number of bit flips could be detected. There were some memory allocation issues in both of the methods which resulted in high memory consumption when a lot of keys were inserted into the tree, but a reasonable solution for that is given at the end of the thesis.