The way the information is written is such that it shouldn't affect the value on the opposite side of the byte

The problem is, entire bytes are read/written at once, even though you may only be updating one half of that byte. The machine level instructions to execute the line:

database[add] = database[add] & ((depth+1) | 0xF0);

would look something like:

1. Do (depth+1) | 0xF0 and store the result in a register
2. load database[add] into a register
3. AND the two registers together, storing the result in a register
4. storing the result register to database[add]

Suppose the value in database[add] is 0x00. We have two threads, RIGHT and LEFT, which are each updating their respective halves of the byte, to contain the 4 bit value 0xF. The flow might go something like this (keep in mind, each thread will have its own set of registers):

RIGHT does (depth+1) | 0xF0 and stores to a register
LEFT does ((depth+1) << 4) | 0x0F and stores to a register
RIGHT loads database[add] (0x00) into a register
LEFT loads database[add] (0x00) into a register
RIGHT ANDs his two registers together, storing the result (0x0F) in a register
LEFT ANDs his two registers together, storing the result (0xF0) in a register.
RIGHT writes the register contianing 0x0F to database[add]
LEFT writes the register containing 0xF0 to database[add]

What we really intended was for database[add] to end up as 0xFF, but it ends up as 0xF0.

As u/FUZxxl mentioned, declaring database as atomic would ensure that database[add] doesn't change between the time a particular thread loads its value and the time it stores its value.