度（たび）に is the adverbial form of the noun 度（たび）, meaning 'time' (as in 'at the time of'). たびに is frequently paired with either verbs, or nouns, in order to show that something happens 'whenever (A)', or 'each time (A)'.
After nouns, the case marking particle の will be required before たびに.

• タナカ君（くん）と飲（の）みに行（い）くたびに、二日（ふつか）酔（よ）いになる。
  Every time I go out to drink with Tanaka-kun, I get a hangover.
• 牛乳（ぎゅうにゅう）を飲（の）むたびにお腹（なか）が痛（いた）くなる。
  Every time I drink milk, I get a stomach ache.
• 私（わたし）は休（やす）みのたびにハワイへ行（い）きます。
  Whenever I have a holiday, I go to Hawaii.
• 彼（かれ）は洗（あら）い物（もの）のたびに指（ゆび）を切（き）る。
  Every time he does the dishes, he cuts his finger.