In this paper, the indexing in constraint databases is considered. Meta-blocktree is improved and a data structure S^* tree is presented. It stores the stabbing sets forconstants that appears in the intervals. If the maximurn length of each stabbing set is limited, the space used in S^* tree is optimal- Compared with M tree, a significant improvement of S^* is that it can support delete operation.