A computer-implemented method comprising: determining, by a processor, distinction bit positions for index keys of a database index; representing the distinction bit positions as a first bitmap, the position of each distinction bit in the first bitmap corresponding to the distinction bit's position in the index keys; representing variant bit positions (120, 125, 130) of the index keys as a second bitmap, the variant bit positions (120, 125, 130) being bit positions (105, 110, 115, 120, 130) where all key values for a bit position (105, 110, 115, 120, 130) are not identical; assigning a reference key value for invariant bit positions (105, 110, 115) of the index keys, the invariant bit positions (105, 110, 115) being bit positions (105, 110, 115, 120, 130) where all key values for a bit position (105, 110, 115, 120, 130) are identical; maintaining a record of the first bitmap, the second bitmap, and the reference key values during a database operation for the database index; building an index tree (400, 540, 545, 550) from a database table using the first bitmap, the second bitmap, and the reference key values; updating incrementally the first bitmap, the second bitmap, and the reference key values as data in the database table changes, wherein an update operation is accomplished by a delete operation followed by an insert operation, and wherein for delete operations a given delete key value is deleted from the index tree (400, 540, 545, 550) and for insert operations a given insert key value is inserted into the index tree (400, 540, 545, 550); and rebuilding the index tree (400, 540, 545, 550) and a new first bitmap, second bitmap, and reference key values with the current first bitmap, second bitmap, and reference key values when it is lost or unavailable. determining, by a processor, distinction bit positions for index keys of a database index; representing the distinction bit positions as a first bitmap, the position of each distinction bit in the first bitmap corresponding to the distinction bit's position in the index keys; representing variant bit positions (120, 125, 130) of the index keys as a second bitmap, the variant bit positions (120, 125, 130) being bit positions (105, 110, 115, 120, 130) where all key values for a bit position (105, 110, 115, 120, 130) are not identical; assigning a reference key value for invariant bit positions (105, 110, 115) of the index keys, the invariant bit positions (105, 110, 115) being bit positions (105, 110, 115, 120, 130) where all key values for a bit position (105, 110, 115, 120, 130) are identical; maintaining a record of the first bitmap, the second bitmap, and the reference key values during a database operation for the database index; building an index tree (400, 540, 545, 550) from a database table using the first bitmap, the second bitmap, and the reference key values; updating incrementally the first bitmap, the second bitmap, and the reference key values as data in the database table changes, wherein an update operation is accomplished by a delete operation followed by an insert operation, and wherein for delete operations a given delete key value is deleted from the index tree (400, 540, 545, 550) and for insert operations a given insert key value is inserted into the index tree (400, 540, 545, 550); and rebuilding the index tree (400, 540, 545, 550) and a new first bitmap, second bitmap, and reference key values with the current first bitmap, second bitmap, and reference key values when it is lost or unavailable.