diff --git a/libedataserverui/e-tree-model-generator.c b/libedataserverui/e-tree-model-generator.c
index 5537528..4380cc6 100644
--- a/libedataserverui/e-tree-model-generator.c
+++ b/libedataserverui/e-tree-model-generator.c
@@ -111,6 +111,7 @@ typedef struct {
 
 	gint    n_generated;
 	GArray *child_nodes;
+	gint    accum_offset;
 }
 Node;
 
@@ -293,22 +294,65 @@ row_changed (ETreeModelGenerator *tree_model_generator, GtkTreePath *path)
  * Node map translation *
  * -------------------- */
 
+static void
+recalc_accum_offsets (GArray *group, gint from_index)
+{
+	gint ii, accum_offset = 0;
+	Node *node;
+
+	g_return_if_fail (group != NULL);
+	g_return_if_fail (from_index >= 0);
+	g_return_if_fail (from_index < group->len);
+
+	if (from_index > 0) {
+		node = &g_array_index (group, Node, from_index - 1);
+		accum_offset = node->accum_offset + node->n_generated;
+	}
+
+	for (ii = from_index; ii < group->len; ii++) {
+		node = &g_array_index (group, Node, ii);
+
+		node->accum_offset = accum_offset;
+		accum_offset += node->n_generated;
+	}
+}
+
 static gint
 generated_offset_to_child_offset (GArray *group, gint offset, gint *internal_offset)
 {
-	gboolean success      = FALSE;
-	gint     accum_offset = 0;
-	gint     i;
+	gboolean success = FALSE;
+	gint aa, bb, mid;
+	Node *node;
+	gint accum_offset = 0;
 
-	for (i = 0; i < group->len; i++) {
-		Node *node = &g_array_index (group, Node, i);
+	if (!group->len)
+		return -1;
 
-		accum_offset += node->n_generated;
-		if (accum_offset > offset) {
-			accum_offset -= node->n_generated;
+	
+	aa = 0;
+	bb = group->len;
+	while (aa < bb) {
+		mid = aa + (bb - aa) / 2;
+
+		node = &g_array_index (group, Node, mid);
+		if (node->accum_offset <= offset && offset < node->accum_offset + node->n_generated) {
 			success = TRUE;
+			accum_offset = node->accum_offset;
 			break;
 		}
+
+		if (node->accum_offset <= offset)
+			aa = aa == mid ? mid + 1 : mid;
+		else
+			bb = bb == mid ? mid - 1 : mid;
+	}
+
+	if (!success && mid >= 0 && mid < group->len) {
+		node = &g_array_index (group, Node, mid);
+		if (node->accum_offset <= offset && offset < node->accum_offset + node->n_generated) {
+			success = TRUE;
+			accum_offset = node->accum_offset;
+		}
 	}
 
 	if (!success)
@@ -317,22 +361,19 @@ generated_offset_to_child_offset (GArray *group, gint offset, gint *internal_off
 	if (internal_offset)
 		*internal_offset = offset - accum_offset;
 
-	return i;
+	return mid;
 }
 
 static gint
 child_offset_to_generated_offset (GArray *group, gint offset)
 {
-	gint accum_offset = 0;
-	gint i;
-
-	for (i = 0; i < group->len && i < offset; i++) {
-		Node *node = &g_array_index (group, Node, i);
+	if (offset >= group->len)
+		offset = group->len - 1;
 
-		accum_offset += node->n_generated;
-	}
+	if (offset < 0)
+		return 0;
 
-	return accum_offset;
+	return g_array_index (group, Node, offset).accum_offset;
 }
 
 static gint
@@ -414,6 +455,9 @@ build_node_map (ETreeModelGenerator *tree_model_generator, GtkTreeIter *parent_i
 		node->child_nodes = build_node_map (tree_model_generator, &iter, group, i);
 	} while (gtk_tree_model_iter_next (tree_model_generator->priv->child_model, &iter));
 
+	if (group->len > 0)
+		recalc_accum_offsets (group, 0);
+
 	return group;
 }
 
@@ -436,7 +480,7 @@ get_first_visible_index_from (GArray *group, gint index)
 }
 
 static Node *
-get_node_by_child_path (ETreeModelGenerator *tree_model_generator, GtkTreePath *path, GArray **node_group)
+get_node_by_child_path (ETreeModelGenerator *tree_model_generator, GtkTreePath *path, GArray **node_group, gint *node_index)
 {
 	Node   *node = NULL;
 	GArray *group;
@@ -456,11 +500,17 @@ get_node_by_child_path (ETreeModelGenerator *tree_model_generator, GtkTreePath *
 		node = &g_array_index (group, Node, index);
 
 		if (depth + 1 < gtk_tree_path_get_depth (path))
-		    group = node->child_nodes;
+			group = node->child_nodes;
+
+		if (node_index)
+			*node_index = index;
 	}
 
-	if (!node)
+	if (!node) {
 		group = NULL;
+		if (node_index)
+			*node_index = -1;
+	}
 
 	if (node_group)
 		*node_group = group;
@@ -469,7 +519,7 @@ get_node_by_child_path (ETreeModelGenerator *tree_model_generator, GtkTreePath *
 }
 
 static Node *
-create_node_at_child_path (ETreeModelGenerator *tree_model_generator, GtkTreePath *path)
+create_node_at_child_path (ETreeModelGenerator *tree_model_generator, GtkTreePath *path, GArray **node_group, gint *node_index)
 {
 	GtkTreePath *parent_path;
 	gint         parent_index;
@@ -480,7 +530,7 @@ create_node_at_child_path (ETreeModelGenerator *tree_model_generator, GtkTreePat
 
 	parent_path = gtk_tree_path_copy (path);
 	gtk_tree_path_up (parent_path);
-	node = get_node_by_child_path (tree_model_generator, parent_path, &parent_group);
+	node = get_node_by_child_path (tree_model_generator, parent_path, &parent_group, NULL);
 
 	if (node) {
 		if (!node->child_nodes)
@@ -533,6 +583,10 @@ create_node_at_child_path (ETreeModelGenerator *tree_model_generator, GtkTreePat
 	node->parent_index = parent_index;
 	node->n_generated  = 0;
 	node->child_nodes  = NULL;
+	node->accum_offset = 0;
+
+	*node_group = group;
+	*node_index = index;
 
 	ETMG_DEBUG (g_print ("Created node at offset %d, parent_group = %p, parent_index = %d\n",
 			     index, node->parent_group, node->parent_index));
@@ -570,7 +624,7 @@ delete_node_at_child_path (ETreeModelGenerator *tree_model_generator, GtkTreePat
 
 	parent_path = gtk_tree_path_copy (path);
 	gtk_tree_path_up (parent_path);
-	node = get_node_by_child_path (tree_model_generator, parent_path, &parent_group);
+	node = get_node_by_child_path (tree_model_generator, parent_path, &parent_group, NULL);
 
 	if (node) {
 		group = node->child_nodes;
@@ -592,6 +646,9 @@ delete_node_at_child_path (ETreeModelGenerator *tree_model_generator, GtkTreePat
 		release_node_map (node->child_nodes);
 	g_array_remove_index (group, index);
 
+	if (index < group->len)
+		recalc_accum_offsets (group, index);
+
 	/* Update parent pointers */
 	for (i = index; i < group->len; i++) {
 		Node   *pnode = &g_array_index (group, Node, i);
@@ -613,6 +670,8 @@ static void
 child_row_changed (ETreeModelGenerator *tree_model_generator, GtkTreePath *path, GtkTreeIter *iter)
 {
 	GtkTreePath *generated_path;
+	GArray      *node_group = NULL;
+	gint         node_index = -1;
 	Node        *node;
 	gint         n_generated;
 	gint         i;
@@ -624,10 +683,17 @@ child_row_changed (ETreeModelGenerator *tree_model_generator, GtkTreePath *path,
 	else
 		n_generated = 1;
 
-	node = get_node_by_child_path (tree_model_generator, path, NULL);
+	node = get_node_by_child_path (tree_model_generator, path, &node_group, &node_index);
 	if (!node)
 		return;
 
+	if (node_index > 0) {
+		Node *prev_node;
+
+		prev_node = &g_array_index (node_group, Node, node_index - 1);
+		node->accum_offset = prev_node->accum_offset + prev_node->n_generated;
+	}
+
 	generated_path = e_tree_model_generator_convert_child_path_to_path (tree_model_generator, path);
 
 	/* FIXME: Converting the path to an iter every time is inefficient */
@@ -639,16 +705,20 @@ child_row_changed (ETreeModelGenerator *tree_model_generator, GtkTreePath *path,
 
 	for (; i < node->n_generated; ) {
 		node->n_generated--;
+		recalc_accum_offsets (node_group, node_index);
 		row_deleted (tree_model_generator, generated_path);
 	}
 
 	for (; i < n_generated; i++) {
 		node->n_generated++;
+		recalc_accum_offsets (node_group, node_index);
 		row_inserted (tree_model_generator, generated_path);
 		gtk_tree_path_next (generated_path);
 	}
 
 	gtk_tree_path_free (generated_path);
+
+	recalc_accum_offsets (node_group, node_index);
 }
 
 static void
@@ -657,6 +727,8 @@ child_row_inserted (ETreeModelGenerator *tree_model_generator, GtkTreePath *path
 	GtkTreePath *generated_path;
 	Node        *node;
 	gint         n_generated;
+	GArray      *node_group = NULL;
+	gint         node_index = -1;
 
 	if (tree_model_generator->priv->generate_func)
 		n_generated =
@@ -665,21 +737,31 @@ child_row_inserted (ETreeModelGenerator *tree_model_generator, GtkTreePath *path
 	else
 		n_generated = 1;
 
-	node = create_node_at_child_path (tree_model_generator, path);
+	node = create_node_at_child_path (tree_model_generator, path, &node_group, &node_index);
 	if (!node)
 		return;
 
+	if (node_index > 0) {
+		Node *prev_node;
+
+		prev_node = &g_array_index (node_group, Node, node_index - 1);
+		node->accum_offset = prev_node->accum_offset + prev_node->n_generated;
+	}
+
 	generated_path = e_tree_model_generator_convert_child_path_to_path (tree_model_generator, path);
 
 	/* FIXME: Converting the path to an iter every time is inefficient */
 
 	for (node->n_generated = 0; node->n_generated < n_generated; ) {
 		node->n_generated++;
+		recalc_accum_offsets (node_group, node_index);
 		row_inserted (tree_model_generator, generated_path);
 		gtk_tree_path_next (generated_path);
 	}
 
 	gtk_tree_path_free (generated_path);
+
+	recalc_accum_offsets (node_group, node_index);
 }
 
 static void
@@ -688,7 +770,7 @@ child_row_deleted (ETreeModelGenerator *tree_model_generator, GtkTreePath *path)
 	GtkTreePath *generated_path;
 	Node        *node;
 
-	node = get_node_by_child_path (tree_model_generator, path, NULL);
+	node = get_node_by_child_path (tree_model_generator, path, NULL, NULL);
 	if (!node)
 		return;
 
