Mining frequent traversal patterns is to discover the consecutive reference paths traversed by a sufficient number of users from web logs. The previous approaches for mining frequent traversal patterns need to repeatedly scan the traversal paths and take a large amount of computation time to find frequent traversal patterns. However, the discovered frequent traversal patterns may become invalid or inappropriate when the databases are updated. In this paper, we propose an incremental updating technique to maintain the discovered frequent traversal patterns when the user sequences are inserted into or the database. Our approach partitions the database into some segments and scans the database segment by segment. For each segment scan, the candidate traversal sequences that cannot be frequent traversal sequences can be pruned and the frequent traversal sequences can be found out earlier. Besides, the number of database scans can be significantly reduced because some information can be computed by our approach. The experimental results show that our algorithms are more efficient than other algorithms for the maintenance of mining frequent traversal patterns.