Where is the order of a menu saved in the database

You will get the nav_menu_items from wp_term_relationship in correct order. if you want to confirm there order by knowing there order number… u will get the object id of each item from the previous table and search for that id in wp_posts. then there will be column for that particular row named menu_order. so that u can get the actual order number.