$data = json_decode( '[{"id":1,"children":[{"id":2,"children":[{"id":4},{"id":7},{"id":8}]},{"id":3}]},{"id":5},{"id":6}]' );

function insert( $rows = array() ) {
	$order = 0;
	foreach( $rows as $row ) {
		// Oppdater order-kolonnen i databasen med $order-variablen her
		$sql = "UPDATE menu SET order=$order WHERE id=$row->id"; // Eksempel

		if( isset( $row->children ) ) {
			insert( $row->children );
		}
		$order++;
	}
}

insert( $data );