diff --git a/fs/ssdfs/btree_hierarchy.c b/fs/ssdfs/btree_hierarchy.c
index cba502e6f3a6..6e9f91ed4541 100644
--- a/fs/ssdfs/btree_hierarchy.c
+++ b/fs/ssdfs/btree_hierarchy.c
@@ -2906,3 +2906,2750 @@ int ssdfs_btree_prepare_index_area_resize(struct ssdfs_btree_level *level,
 
 	return 0;
 }
+
+/*
+ * ssdfs_btree_check_nothing_root_pair() - check pair of nothing and root nodes
+ * @tree: btree object
+ * @search: search object
+ * @parent: parent level object
+ * @child: child level object
+ *
+ * This method tries to check the nothing and root nodes pair.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-ERANGE     - internal error.
+ */
+static
+int ssdfs_btree_check_nothing_root_pair(struct ssdfs_btree *tree,
+					struct ssdfs_btree_search *search,
+					struct ssdfs_btree_level *parent,
+					struct ssdfs_btree_level *child)
+{
+	int child_type;
+	struct ssdfs_btree_node *child_node;
+	u64 start_hash, end_hash;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !search);
+	BUG_ON(!parent || !child);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	child_node = child->nodes.old_node.ptr;
+
+	if (!child_node) {
+		SSDFS_ERR("child is NULL\n");
+		return -ERANGE;
+	}
+
+	child_type = atomic_read(&child_node->type);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("tree %p, search %p, "
+		  "parent %p, child %p, "
+		  "child id %u, child_type %#x\n",
+		  tree, search, parent, child,
+		  child_node->node_id, child_type);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (child_type != SSDFS_BTREE_ROOT_NODE) {
+		SSDFS_WARN("invalid child node's type %#x\n",
+			   child_type);
+		return -ERANGE;
+	}
+
+	if (!(child->flags & SSDFS_BTREE_LEVEL_ADD_NODE))
+		return 0;
+
+	down_read(&child_node->header_lock);
+	start_hash = child_node->index_area.start_hash;
+	end_hash = U64_MAX;
+	up_read(&child_node->header_lock);
+
+	err = ssdfs_btree_prepare_add_index(parent,
+					    start_hash,
+					    end_hash,
+					    child_node);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to prepare level: "
+			  "node_id %u, height %u\n",
+			  child_node->node_id,
+			  atomic_read(&child_node->height));
+		return err;
+	}
+
+	err = ssdfs_btree_define_moving_indexes(parent, child);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to define moving indexes: "
+			  "err %d\n", err);
+		return err;
+	}
+
+	return 0;
+}
+
+/*
+ * ssdfs_btree_check_root_nothing_pair() - check pair of root and nothing nodes
+ * @tree: btree object
+ * @search: search object
+ * @parent: parent level object
+ * @child: child level object
+ *
+ * This method tries to check the root and nothing nodes pair.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ */
+static
+int ssdfs_btree_check_root_nothing_pair(struct ssdfs_btree *tree,
+					struct ssdfs_btree_search *search,
+					struct ssdfs_btree_level *parent,
+					struct ssdfs_btree_level *child)
+{
+	int tree_height;
+	int parent_type;
+	struct ssdfs_btree_node *parent_node;
+	u64 start_hash, end_hash;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !search);
+	BUG_ON(!parent || !child);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	parent_node = parent->nodes.old_node.ptr;
+
+	if (!parent_node) {
+		SSDFS_ERR("parent is NULL\n");
+		return -ERANGE;
+	}
+
+	parent_type = atomic_read(&parent_node->type);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("tree %p, search %p, "
+		  "parent %p, child %p, "
+		  "parent id %u, type %#x\n",
+		  tree, search, parent, child,
+		  parent_node->node_id,
+		  parent_type);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (parent_type != SSDFS_BTREE_ROOT_NODE) {
+		SSDFS_WARN("invalid parent node's type %#x\n",
+			   parent_type);
+		return -ERANGE;
+	}
+
+	tree_height = atomic_read(&tree->height);
+	if (tree_height <= 0 || tree_height > 1) {
+		SSDFS_WARN("unexpected tree_height %u\n",
+			  tree_height);
+		return -EINVAL;
+	}
+
+	if (!can_add_new_index(parent_node)) {
+		SSDFS_ERR("unable add index into the root\n");
+		return -ERANGE;
+	}
+
+	start_hash = search->request.start.hash;
+	end_hash = search->request.end.hash;
+
+	ssdfs_btree_prepare_add_node(tree, SSDFS_BTREE_LEAF_NODE,
+				     start_hash, end_hash,
+				     child, NULL);
+
+	err = ssdfs_btree_prepare_add_index(parent, start_hash,
+					    end_hash, parent_node);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to prepare level: "
+			  "node_id %u, height %u\n",
+			  parent_node->node_id,
+			  atomic_read(&parent_node->height));
+		return err;
+	}
+
+	return 0;
+}
+
+/*
+ * ssdfs_btree_check_root_index_pair() - check pair of root and index nodes
+ * @tree: btree object
+ * @search: search object
+ * @parent: parent level object
+ * @child: child level object
+ *
+ * This method tries to check the root and index nodes pair.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENOSPC     - needs to increase the tree's height.
+ */
+static
+int ssdfs_btree_check_root_index_pair(struct ssdfs_btree *tree,
+					struct ssdfs_btree_search *search,
+					struct ssdfs_btree_level *parent,
+					struct ssdfs_btree_level *child)
+{
+	int parent_type, child_type;
+	int parent_height, child_height;
+	struct ssdfs_btree_node *parent_node, *child_node;
+	u64 start_hash, end_hash;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !search);
+	BUG_ON(!parent || !child);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	parent_node = parent->nodes.old_node.ptr;
+
+	if (!parent_node) {
+		SSDFS_ERR("parent is NULL\n");
+		return -ERANGE;
+	}
+
+	child_node = child->nodes.old_node.ptr;
+
+	if (!child_node) {
+		SSDFS_ERR("child is NULL\n");
+		return -ERANGE;
+	}
+
+	parent_type = atomic_read(&parent_node->type);
+	child_type = atomic_read(&child_node->type);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("tree %p, search %p, "
+		  "parent %p, child %p, "
+		  "parent id %u, parent_type %#x, "
+		  "child id %u, child_type %#x\n",
+		  tree, search, parent, child,
+		  parent_node->node_id, parent_type,
+		  child_node->node_id, child_type);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (parent_type != SSDFS_BTREE_ROOT_NODE) {
+		SSDFS_WARN("invalid parent node's type %#x\n",
+			   parent_type);
+		return -ERANGE;
+	}
+
+	if (child_type != SSDFS_BTREE_INDEX_NODE) {
+		SSDFS_WARN("invalid child node's type %#x\n",
+			   child_type);
+		return -ERANGE;
+	}
+
+	parent_height = atomic_read(&parent_node->height);
+	child_height = atomic_read(&child_node->height);
+
+	if ((child_height + 1) != parent_height) {
+		SSDFS_ERR("invalid pair: "
+			  "parent_height %u, child_height %u\n",
+			  parent_height, child_height);
+		return -ERANGE;
+	}
+
+	start_hash = search->request.start.hash;
+	end_hash = search->request.end.hash;
+
+	if (child->flags & SSDFS_BTREE_LEVEL_ADD_NODE) {
+		if (can_add_new_index(parent_node)) {
+			err = ssdfs_btree_prepare_add_index(parent,
+							    start_hash,
+							    end_hash,
+							    parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare level: "
+					  "node_id %u\n",
+					  parent_node->node_id);
+				return err;
+			}
+		} else {
+			ssdfs_btree_prepare_add_node(tree,
+						     SSDFS_BTREE_INDEX_NODE,
+						     start_hash, end_hash,
+						     parent, parent_node);
+
+			err = ssdfs_btree_prepare_add_index(parent,
+							    start_hash,
+							    end_hash,
+							    parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare level: "
+					  "node_id %u, height %u\n",
+					  parent_node->node_id,
+					  atomic_read(&parent_node->height));
+				return err;
+			}
+
+			/*
+			 * it needs to prepare increasing
+			 * the tree's height
+			 */
+			return -ENOSPC;
+		}
+	} else if (need_update_parent_index_area(start_hash, child_node)) {
+		err = ssdfs_btree_prepare_update_index(parent,
+							start_hash,
+							end_hash,
+							parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare update index: "
+				  "err %d\n", err);
+			return err;
+		}
+	}
+
+	if (!parent->flags) {
+		err = ssdfs_btree_prepare_do_nothing(parent,
+						     parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare root node: "
+				  "err %d\n", err);
+			return err;
+		}
+	}
+
+	return 0;
+}
+
+/*
+ * ssdfs_btree_check_root_hybrid_pair() - check pair of root and hybrid nodes
+ * @tree: btree object
+ * @search: search object
+ * @parent: parent level object
+ * @child: child level object
+ *
+ * This method tries to check the root and hybrid nodes pair.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENOSPC     - needs to increase the tree's height.
+ */
+static
+int ssdfs_btree_check_root_hybrid_pair(struct ssdfs_btree *tree,
+					struct ssdfs_btree_search *search,
+					struct ssdfs_btree_level *parent,
+					struct ssdfs_btree_level *child)
+{
+	int tree_height;
+	int parent_type, child_type;
+	struct ssdfs_btree_node *parent_node, *child_node;
+	u64 start_hash, end_hash;
+	u16 items_count;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !search);
+	BUG_ON(!parent || !child);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	parent_node = parent->nodes.old_node.ptr;
+
+	if (!parent_node) {
+		SSDFS_ERR("parent is NULL\n");
+		return -ERANGE;
+	}
+
+	child_node = child->nodes.old_node.ptr;
+
+	if (!child_node) {
+		SSDFS_ERR("child is NULL\n");
+		return -ERANGE;
+	}
+
+	parent_type = atomic_read(&parent_node->type);
+	child_type = atomic_read(&child_node->type);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("tree %p, search %p, "
+		  "parent %p, child %p, "
+		  "parent id %u, parent_type %#x, "
+		  "child id %u, child_type %#x\n",
+		  tree, search, parent, child,
+		  parent_node->node_id, parent_type,
+		  child_node->node_id, child_type);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (parent_type != SSDFS_BTREE_ROOT_NODE) {
+		SSDFS_WARN("invalid parent node's type %#x\n",
+			   parent_type);
+		return -ERANGE;
+	}
+
+	if (child_type != SSDFS_BTREE_HYBRID_NODE) {
+		SSDFS_WARN("invalid child node's type %#x\n",
+			   child_type);
+		return -ERANGE;
+	}
+
+	tree_height = atomic_read(&tree->height);
+	start_hash = search->request.start.hash;
+	end_hash = search->request.end.hash;
+
+	if (tree_height < 2) {
+		SSDFS_ERR("invalid tree height %d\n",
+			  tree_height);
+		return -ERANGE;
+	}
+
+	down_read(&child_node->header_lock);
+	items_count = child_node->items_area.items_count;
+	up_read(&child_node->header_lock);
+
+	if (tree_height >= 3 && items_count == 0) {
+		err = ssdfs_btree_prepare_insert_item(child, search,
+						      child_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare the insert: "
+				  "node_id %u, height %u\n",
+				  child_node->node_id,
+				  atomic_read(&child_node->height));
+			return err;
+		}
+
+		if (need_update_parent_index_area(start_hash, child_node)) {
+			err = ssdfs_btree_prepare_update_index(parent,
+								start_hash,
+								end_hash,
+								parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare update index: "
+					  "err %d\n", err);
+				return err;
+			}
+		}
+	} else if (tree_height == 2) {
+		err = ssdfs_btree_prepare_insert_item(child, search, child_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare the insert: "
+				  "node_id %u, height %u\n",
+				  child_node->node_id,
+				  atomic_read(&child_node->height));
+			return err;
+		}
+
+		ssdfs_btree_prepare_add_node(tree, SSDFS_BTREE_LEAF_NODE,
+					     start_hash, end_hash,
+					     child, child_node);
+
+		err = ssdfs_btree_prepare_add_index(child,
+						    start_hash,
+						    end_hash,
+						    child_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare level: "
+				  "node_id %u, height %u\n",
+				  child_node->node_id,
+				  atomic_read(&child_node->height));
+			return err;
+		}
+
+		err = ssdfs_btree_define_moving_items(tree, search,
+							child, child);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to define moving items: "
+				  "err %d\n", err);
+			return err;
+		}
+
+		/*
+		 * it needs to prepare increasing
+		 * the tree's height
+		 */
+		return -ENOSPC;
+	} else if (child->flags & SSDFS_BTREE_LEVEL_ADD_NODE) {
+		if (can_add_new_index(parent_node)) {
+			err = ssdfs_btree_prepare_add_index(parent,
+							start_hash,
+							end_hash,
+							parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare level: "
+					  "node_id %u\n",
+					  parent_node->node_id);
+				return err;
+			}
+		} else {
+			ssdfs_btree_prepare_add_node(tree,
+						SSDFS_BTREE_INDEX_NODE,
+						start_hash, end_hash,
+						parent, parent_node);
+
+			err = ssdfs_btree_prepare_add_index(parent,
+							start_hash,
+							end_hash,
+							parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare level: "
+					  "node_id %u\n",
+					  parent_node->node_id);
+				return err;
+			}
+
+			/*
+			 * it needs to prepare increasing
+			 * the tree's height
+			 */
+			return -ENOSPC;
+		}
+	} else if (need_update_parent_index_area(start_hash,
+						 child_node)) {
+		err = ssdfs_btree_prepare_update_index(parent,
+							start_hash,
+							end_hash,
+							parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare update index: "
+				  "err %d\n", err);
+			return err;
+		}
+	}
+
+	if (!parent->flags) {
+		err = ssdfs_btree_prepare_do_nothing(parent,
+						     parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare root node: "
+				  "err %d\n", err);
+			return err;
+		}
+	}
+
+	return 0;
+}
+
+/*
+ * ssdfs_btree_check_root_leaf_pair() - check pair of root and leaf nodes
+ * @tree: btree object
+ * @search: search object
+ * @parent: parent level object
+ * @child: child level object
+ *
+ * This method tries to check the root and leaf nodes pair.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENOSPC     - needs to increase the tree's height.
+ */
+static
+int ssdfs_btree_check_root_leaf_pair(struct ssdfs_btree *tree,
+				     struct ssdfs_btree_search *search,
+				     struct ssdfs_btree_level *parent,
+				     struct ssdfs_btree_level *child)
+{
+	int tree_height;
+	int parent_type, child_type;
+	struct ssdfs_btree_node *parent_node, *child_node;
+	u64 start_hash, end_hash;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !search);
+	BUG_ON(!parent || !child);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	parent_node = parent->nodes.old_node.ptr;
+
+	if (!parent_node) {
+		SSDFS_ERR("parent is NULL\n");
+		return -ERANGE;
+	}
+
+	child_node = child->nodes.old_node.ptr;
+
+	if (!child_node) {
+		SSDFS_ERR("child is NULL\n");
+		return -ERANGE;
+	}
+
+	parent_type = atomic_read(&parent_node->type);
+	child_type = atomic_read(&child_node->type);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("tree %p, search %p, "
+		  "parent %p, child %p, "
+		  "parent id %u, parent_type %#x, "
+		  "child id %u, child_type %#x\n",
+		  tree, search, parent, child,
+		  parent_node->node_id, parent_type,
+		  child_node->node_id, child_type);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (parent_type != SSDFS_BTREE_ROOT_NODE) {
+		SSDFS_WARN("invalid parent node's type %#x\n",
+			   parent_type);
+		return -ERANGE;
+	}
+
+	if (child_type != SSDFS_BTREE_LEAF_NODE) {
+		SSDFS_WARN("invalid child node's type %#x\n",
+			   child_type);
+		return -ERANGE;
+	}
+
+	tree_height = atomic_read(&tree->height);
+	if (tree_height > 2) {
+		SSDFS_WARN("unexpected tree_height %u\n",
+			  tree_height);
+		return -EINVAL;
+	}
+
+	start_hash = search->request.start.hash;
+	end_hash = search->request.end.hash;
+
+	if (can_add_new_index(parent_node)) {
+		/* tree has only one leaf node */
+		err = ssdfs_btree_prepare_insert_item(child,
+						      search,
+						      child_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare the insert: "
+				  "node_id %u, height %u\n",
+				  child_node->node_id,
+				  atomic_read(&child_node->height));
+			return err;
+		}
+
+		if (ssdfs_need_move_items_to_sibling(child)) {
+			err = ssdfs_check_capability_move_to_sibling(child);
+			if (err == -ENOSPC) {
+				/*
+				 * It needs to add a node.
+				 */
+			} else if (unlikely(err)) {
+				SSDFS_ERR("fail to check moving to sibling: "
+					  "err %d\n", err);
+				return err;
+			}
+		} else
+			err = -ENOSPC;
+
+		if (err == -ENOSPC) {
+			ssdfs_btree_prepare_add_node(tree,
+						     SSDFS_BTREE_LEAF_NODE,
+						     start_hash, end_hash,
+						     child, child_node);
+
+			err = ssdfs_btree_prepare_add_index(parent,
+							    start_hash,
+							    end_hash,
+							    parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare level: "
+					  "node_id %u, height %u\n",
+					  parent_node->node_id,
+					  atomic_read(&parent_node->height));
+				return err;
+			}
+		} else {
+			err = ssdfs_btree_prepare_update_index(parent,
+								start_hash,
+								end_hash,
+								parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare update index: "
+					  "err %d\n", err);
+				return err;
+			}
+		}
+	} else {
+		err = ssdfs_btree_prepare_insert_item(child,
+						      search,
+						      child_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare the insert: "
+				  "node_id %u, height %u\n",
+				  child_node->node_id,
+				  atomic_read(&child_node->height));
+			return err;
+		}
+
+		if (ssdfs_need_move_items_to_sibling(child)) {
+			err = ssdfs_check_capability_move_to_sibling(child);
+			if (err == -ENOSPC) {
+				/*
+				 * It needs to add a node.
+				 */
+				ssdfs_btree_cancel_insert_item(child);
+			} else if (unlikely(err)) {
+				SSDFS_ERR("fail to check moving to sibling: "
+					  "err %d\n", err);
+				return err;
+			} else {
+				err = ssdfs_btree_prepare_update_index(parent,
+								start_hash,
+								end_hash,
+								parent_node);
+				if (unlikely(err)) {
+					SSDFS_ERR("fail to prepare update: "
+						  "err %d\n", err);
+					return err;
+				}
+
+				return 0;
+			}
+		} else
+			ssdfs_btree_cancel_insert_item(child);
+
+		ssdfs_btree_prepare_add_node(tree,
+					     SSDFS_BTREE_HYBRID_NODE,
+					     start_hash, end_hash,
+					     parent, parent_node);
+
+		err = ssdfs_btree_prepare_insert_item(parent,
+						      search,
+						      parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare the insert: "
+				  "node_id %u, height %u\n",
+				  parent_node->node_id,
+				  atomic_read(&parent_node->height));
+			return err;
+		}
+
+		if (ssdfs_need_move_items_to_parent(child)) {
+			err = ssdfs_prepare_move_items_to_parent(search,
+								 parent,
+								 child);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to check moving to sibling: "
+					  "err %d\n", err);
+				return err;
+			}
+		}
+
+		/* it needs to prepare increasing the tree's height */
+		return -ENOSPC;
+	}
+
+	return 0;
+}
+
+/*
+ * ssdfs_btree_check_index_index_pair() - check pair of index and index nodes
+ * @tree: btree object
+ * @search: search object
+ * @parent: parent level object
+ * @child: child level object
+ *
+ * This method tries to check the index and index nodes pair.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ */
+static
+int ssdfs_btree_check_index_index_pair(struct ssdfs_btree *tree,
+					struct ssdfs_btree_search *search,
+					struct ssdfs_btree_level *parent,
+					struct ssdfs_btree_level *child)
+{
+	int parent_type, child_type;
+	int parent_height, child_height;
+	struct ssdfs_btree_node *parent_node, *child_node;
+	u64 start_hash, end_hash;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !search);
+	BUG_ON(!parent || !child);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	parent_node = parent->nodes.old_node.ptr;
+
+	if (!parent_node) {
+		SSDFS_ERR("parent is NULL\n");
+		return -ERANGE;
+	}
+
+	child_node = child->nodes.old_node.ptr;
+
+	if (!child_node) {
+		SSDFS_ERR("child is NULL\n");
+		return -ERANGE;
+	}
+
+	parent_type = atomic_read(&parent_node->type);
+	child_type = atomic_read(&child_node->type);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("tree %p, search %p, "
+		  "parent %p, child %p, "
+		  "parent id %u, parent_type %#x, "
+		  "child id %u, child_type %#x\n",
+		  tree, search, parent, child,
+		  parent_node->node_id, parent_type,
+		  child_node->node_id, child_type);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (parent_type != SSDFS_BTREE_INDEX_NODE) {
+		SSDFS_WARN("invalid parent node's type %#x\n",
+			   parent_type);
+		return -ERANGE;
+	}
+
+	if (child_type != SSDFS_BTREE_INDEX_NODE) {
+		SSDFS_WARN("invalid child node's type %#x\n",
+			   child_type);
+		return -ERANGE;
+	}
+
+	parent_height = atomic_read(&parent_node->height);
+	child_height = atomic_read(&child_node->height);
+
+	if ((child_height + 1) != parent_height) {
+		SSDFS_ERR("invalid pair: "
+			  "parent_height %u, child_height %u\n",
+			  parent_height, child_height);
+		return -ERANGE;
+	}
+
+	start_hash = search->request.start.hash;
+	end_hash = search->request.end.hash;
+
+	if (child->flags & SSDFS_BTREE_LEVEL_ADD_NODE) {
+		if (can_add_new_index(parent_node)) {
+			err = ssdfs_btree_prepare_add_index(parent,
+							    start_hash,
+							    end_hash,
+							    parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare level: "
+					  "node_id %u, height %u\n",
+					  parent_node->node_id,
+					  atomic_read(&parent_node->height));
+				return err;
+			}
+		} else {
+			ssdfs_btree_prepare_add_node(tree,
+						     SSDFS_BTREE_INDEX_NODE,
+						     start_hash, end_hash,
+						     parent, parent_node);
+
+			err = ssdfs_btree_prepare_add_index(parent,
+							    start_hash,
+							    end_hash,
+							    parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare level: "
+					  "node_id %u, height %u\n",
+					  parent_node->node_id,
+					  atomic_read(&parent_node->height));
+				return err;
+			}
+		}
+	} else if (need_update_parent_index_area(start_hash, child_node)) {
+		err = ssdfs_btree_prepare_update_index(parent,
+							start_hash,
+							end_hash,
+							parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare update index: "
+				  "err %d\n", err);
+			return err;
+		}
+	}
+
+	if (!parent->flags) {
+		err = ssdfs_btree_prepare_do_nothing(parent,
+						     parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare index node: "
+				  "err %d\n", err);
+			return err;
+		}
+	}
+
+	return 0;
+}
+
+/*
+ * ssdfs_btree_check_index_hybrid_pair() - check pair of index and hybrid nodes
+ * @tree: btree object
+ * @search: search object
+ * @parent: parent level object
+ * @child: child level object
+ *
+ * This method tries to check the index and hybrid nodes pair.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ */
+static
+int ssdfs_btree_check_index_hybrid_pair(struct ssdfs_btree *tree,
+					struct ssdfs_btree_search *search,
+					struct ssdfs_btree_level *parent,
+					struct ssdfs_btree_level *child)
+{
+	int parent_type, child_type;
+	int parent_height, child_height;
+	struct ssdfs_btree_node *parent_node, *child_node;
+	u64 start_hash, end_hash;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !search);
+	BUG_ON(!parent || !child);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	parent_node = parent->nodes.old_node.ptr;
+
+	if (!parent_node) {
+		SSDFS_ERR("parent is NULL\n");
+		return -ERANGE;
+	}
+
+	child_node = child->nodes.old_node.ptr;
+
+	if (!child_node) {
+		SSDFS_ERR("child is NULL\n");
+		return -ERANGE;
+	}
+
+	parent_type = atomic_read(&parent_node->type);
+	child_type = atomic_read(&child_node->type);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("tree %p, search %p, "
+		  "parent %p, child %p, "
+		  "parent id %u, parent_type %#x, "
+		  "child id %u, child_type %#x\n",
+		  tree, search, parent, child,
+		  parent_node->node_id, parent_type,
+		  child_node->node_id, child_type);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (parent_type != SSDFS_BTREE_INDEX_NODE) {
+		SSDFS_WARN("invalid parent node's type %#x\n",
+			   parent_type);
+		return -ERANGE;
+	}
+
+	if (child_type != SSDFS_BTREE_HYBRID_NODE) {
+		SSDFS_WARN("invalid child node's type %#x\n",
+			   child_type);
+		return -ERANGE;
+	}
+
+	parent_height = atomic_read(&parent_node->height);
+	child_height = atomic_read(&child_node->height);
+
+	if ((child_height + 1) != parent_height) {
+		SSDFS_ERR("invalid pair: "
+			  "parent_height %u, child_height %u\n",
+			  parent_height, child_height);
+		return -ERANGE;
+	}
+
+	start_hash = search->request.start.hash;
+	end_hash = search->request.end.hash;
+
+	if (child->flags & SSDFS_BTREE_TRY_RESIZE_INDEX_AREA) {
+		err = ssdfs_btree_define_moving_indexes(parent, child);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to define moving indexes: "
+				  "err %d\n", err);
+			return err;
+		}
+
+		if (need_update_parent_index_area(start_hash, child_node)) {
+			err = ssdfs_btree_prepare_update_index(parent,
+								start_hash,
+								end_hash,
+								parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare update index: "
+					  "err %d\n", err);
+				return err;
+			}
+		}
+	} else if (child->flags & SSDFS_BTREE_LEVEL_ADD_NODE) {
+		if (can_add_new_index(parent_node)) {
+			err = ssdfs_btree_prepare_add_index(parent,
+							    start_hash,
+							    end_hash,
+							    parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare level: "
+					  "node_id %u, height %u\n",
+					  parent_node->node_id,
+					  atomic_read(&parent_node->height));
+				return err;
+			}
+		} else {
+			ssdfs_btree_prepare_add_node(tree,
+						     SSDFS_BTREE_INDEX_NODE,
+						     start_hash, end_hash,
+						     parent, parent_node);
+
+			err = ssdfs_btree_prepare_add_index(parent,
+							    start_hash,
+							    end_hash,
+							    parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare level: "
+					  "node_id %u, height %u\n",
+					  parent_node->node_id,
+					  atomic_read(&parent_node->height));
+				return err;
+			}
+		}
+	} else if (need_update_parent_index_area(start_hash, child_node)) {
+		err = ssdfs_btree_prepare_update_index(parent,
+							start_hash,
+							end_hash,
+							parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare update index: "
+				  "err %d\n", err);
+			return err;
+		}
+	}
+
+	if (!parent->flags) {
+		err = ssdfs_btree_prepare_do_nothing(parent,
+						     parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare index node: "
+				  "err %d\n", err);
+			return err;
+		}
+	}
+
+	return 0;
+}
+
+/*
+ * ssdfs_btree_check_index_leaf_pair() - check pair of index and leaf nodes
+ * @tree: btree object
+ * @search: search object
+ * @parent: parent level object
+ * @child: child level object
+ *
+ * This method tries to check the index and leaf nodes pair.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ */
+static
+int ssdfs_btree_check_index_leaf_pair(struct ssdfs_btree *tree,
+					struct ssdfs_btree_search *search,
+					struct ssdfs_btree_level *parent,
+					struct ssdfs_btree_level *child)
+{
+	int parent_type, child_type;
+	int parent_height, child_height;
+	struct ssdfs_btree_node *parent_node, *child_node;
+	u64 start_hash, end_hash;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !search);
+	BUG_ON(!parent || !child);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	parent_node = parent->nodes.old_node.ptr;
+
+	if (!parent_node) {
+		SSDFS_ERR("parent is NULL\n");
+		return -ERANGE;
+	}
+
+	child_node = child->nodes.old_node.ptr;
+
+	if (!child_node) {
+		SSDFS_ERR("child is NULL\n");
+		return -ERANGE;
+	}
+
+	parent_type = atomic_read(&parent_node->type);
+	child_type = atomic_read(&child_node->type);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("tree %p, search %p, "
+		  "parent %p, child %p, "
+		  "parent id %u, parent_type %#x, "
+		  "child id %u, child_type %#x\n",
+		  tree, search, parent, child,
+		  parent_node->node_id, parent_type,
+		  child_node->node_id, child_type);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (parent_type != SSDFS_BTREE_INDEX_NODE) {
+		SSDFS_WARN("invalid parent node's type %#x\n",
+			   parent_type);
+		return -ERANGE;
+	}
+
+	if (child_type != SSDFS_BTREE_LEAF_NODE) {
+		SSDFS_WARN("invalid child node's type %#x\n",
+			   child_type);
+		return -ERANGE;
+	}
+
+	parent_height = atomic_read(&parent_node->height);
+	child_height = atomic_read(&child_node->height);
+
+	if ((child_height + 1) != parent_height) {
+		SSDFS_ERR("invalid pair: "
+			  "parent_height %u, child_height %u\n",
+			  parent_height, child_height);
+		return -ERANGE;
+	}
+
+	start_hash = search->request.start.hash;
+	end_hash = search->request.end.hash;
+
+	if (can_add_new_index(parent_node)) {
+		err = ssdfs_btree_prepare_insert_item(child,
+						      search,
+						      child_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare the insert: "
+				  "node_id %u, height %u\n",
+				  child_node->node_id,
+				  atomic_read(&child_node->height));
+			return err;
+		}
+
+		if (ssdfs_need_move_items_to_sibling(child)) {
+			err = ssdfs_check_capability_move_to_sibling(child);
+			if (err == -ENOSPC) {
+				/*
+				 * It needs to add a node.
+				 */
+			} else if (unlikely(err)) {
+				SSDFS_ERR("fail to check moving to sibling: "
+					  "err %d\n", err);
+				return err;
+			}
+		} else
+			err = -ENOSPC;
+
+		if (err == -ENOSPC) {
+			ssdfs_btree_prepare_add_node(tree,
+						     SSDFS_BTREE_LEAF_NODE,
+						     start_hash, end_hash,
+						     child, child_node);
+
+			err = ssdfs_btree_prepare_add_index(parent,
+							    start_hash,
+							    end_hash,
+							    parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare level: "
+					  "node_id %u, height %u\n",
+					  parent_node->node_id,
+					  atomic_read(&parent_node->height));
+				return err;
+			}
+		} else {
+			err = ssdfs_btree_prepare_update_index(parent,
+								start_hash,
+								end_hash,
+								parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare update index: "
+					  "err %d\n", err);
+				return err;
+			}
+		}
+	} else {
+		err = ssdfs_check_capability_move_indexes_to_sibling(parent);
+		if (err == -ENOENT) {
+			ssdfs_btree_prepare_add_node(tree,
+						     SSDFS_BTREE_INDEX_NODE,
+						     U64_MAX, U64_MAX,
+						     parent, parent_node);
+
+			err = ssdfs_prepare_move_indexes_right(parent,
+								parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare to move indexes: "
+					  "node_id %u, height %u\n",
+					  parent_node->node_id,
+					  atomic_read(&parent_node->height));
+				return err;
+			}
+		} else if (err == -ENOSPC) {
+			ssdfs_btree_prepare_add_node(tree,
+						     SSDFS_BTREE_INDEX_NODE,
+						     U64_MAX, U64_MAX,
+						     parent, parent_node);
+
+			err = ssdfs_prepare_move_indexes_right(parent,
+								parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare to move indexes: "
+					  "node_id %u, height %u\n",
+					  parent_node->node_id,
+					  atomic_read(&parent_node->height));
+				return err;
+			}
+		} else if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare to move indexes: "
+				  "node_id %u, height %u\n",
+				  parent_node->node_id,
+				  atomic_read(&parent_node->height));
+			return err;
+		} else {
+			/*
+			 * Do nothing.
+			 * The index moving has been prepared already.
+			 */
+		}
+
+		/* make first phase of transformation */
+		return -EAGAIN;
+	}
+
+	return 0;
+}
+
+/*
+ * ssdfs_btree_check_hybrid_nothing_pair() - check pair of hybrid and nothing
+ * @tree: btree object
+ * @search: search object
+ * @parent: parent level object
+ * @child: child level object
+ *
+ * This method tries to check the hybrid and nothing nodes pair.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ */
+static
+int ssdfs_btree_check_hybrid_nothing_pair(struct ssdfs_btree *tree,
+					struct ssdfs_btree_search *search,
+					struct ssdfs_btree_level *parent,
+					struct ssdfs_btree_level *child)
+{
+	int parent_type;
+	struct ssdfs_btree_node *parent_node;
+	u64 start_hash, end_hash;
+	u16 items_count;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !search);
+	BUG_ON(!parent || !child);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	parent_node = parent->nodes.old_node.ptr;
+
+	if (!parent_node) {
+		SSDFS_ERR("parent is NULL\n");
+		return -ERANGE;
+	}
+
+	parent_type = atomic_read(&parent_node->type);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("tree %p, search %p, "
+		  "parent %p, child %p, "
+		  "parent id %u, type %#x\n",
+		  tree, search, parent, child,
+		  parent_node->node_id,
+		  parent_type);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (parent_type != SSDFS_BTREE_HYBRID_NODE) {
+		SSDFS_WARN("invalid parent node's type %#x\n",
+			   parent_type);
+		return -ERANGE;
+	}
+
+	down_read(&parent_node->header_lock);
+	items_count = parent_node->items_area.items_count;
+	start_hash = parent_node->items_area.start_hash;
+	end_hash = parent_node->items_area.end_hash;
+	up_read(&parent_node->header_lock);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("items_count %u, start_hash %llx, end_hash %llx\n",
+		  items_count, start_hash, end_hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (items_count == 0) {
+		/*
+		 * Do nothing.
+		*/
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("parent id %u, type %#x, items_count == 0\n",
+			  parent_node->node_id,
+			  parent_type);
+#endif /* CONFIG_SSDFS_DEBUG */
+	} else if (can_add_new_index(parent_node)) {
+		ssdfs_btree_prepare_add_node(tree, SSDFS_BTREE_LEAF_NODE,
+					     start_hash, end_hash,
+					     child, NULL);
+
+		err = ssdfs_btree_prepare_add_index(parent,
+						    start_hash,
+						    start_hash,
+						    parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare update index: "
+				  "err %d\n", err);
+			return err;
+		}
+
+		err = ssdfs_btree_define_moving_items(tree, search,
+							parent, child);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to define moving items: "
+				  "err %d\n", err);
+			return err;
+		}
+	} else if (is_index_area_resizable(parent_node)) {
+		err = ssdfs_btree_prepare_index_area_resize(parent,
+							parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare resize of index area: "
+				  "err %d\n", err);
+			return err;
+		}
+
+		ssdfs_btree_prepare_add_node(tree, SSDFS_BTREE_LEAF_NODE,
+					     start_hash, end_hash,
+					     child, NULL);
+
+		err = ssdfs_btree_prepare_add_index(parent,
+						    start_hash,
+						    start_hash,
+						    parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare update index: "
+				  "err %d\n", err);
+			return err;
+		}
+
+		err = ssdfs_btree_define_moving_items(tree, search,
+							parent, child);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to define moving items: "
+				  "err %d\n", err);
+			return err;
+		}
+	} else {
+		start_hash = search->request.start.hash;
+		end_hash = search->request.end.hash;
+
+		ssdfs_btree_prepare_add_node(tree, SSDFS_BTREE_HYBRID_NODE,
+					     start_hash, end_hash,
+					     parent, parent_node);
+	}
+
+	if (!parent->flags) {
+		err = ssdfs_btree_prepare_do_nothing(parent,
+						     parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare root node: "
+				  "err %d\n", err);
+			return err;
+		}
+	}
+
+	return 0;
+}
+
+/*
+ * ssdfs_btree_check_hybrid_index_pair() - check pair of hybrid and index nodes
+ * @tree: btree object
+ * @search: search object
+ * @parent: parent level object
+ * @child: child level object
+ *
+ * This method tries to check the hybrid and index nodes pair.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ */
+static
+int ssdfs_btree_check_hybrid_index_pair(struct ssdfs_btree *tree,
+					struct ssdfs_btree_search *search,
+					struct ssdfs_btree_level *parent,
+					struct ssdfs_btree_level *child)
+{
+	int parent_type, child_type;
+	int parent_height, child_height;
+	struct ssdfs_btree_node *parent_node, *child_node;
+	u64 start_hash, end_hash;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !search);
+	BUG_ON(!parent || !child);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	parent_node = parent->nodes.old_node.ptr;
+
+	if (!parent_node) {
+		SSDFS_ERR("parent is NULL\n");
+		return -ERANGE;
+	}
+
+	child_node = child->nodes.old_node.ptr;
+
+	if (!child_node) {
+		SSDFS_ERR("child is NULL\n");
+		return -ERANGE;
+	}
+
+	parent_type = atomic_read(&parent_node->type);
+	child_type = atomic_read(&child_node->type);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("tree %p, search %p, "
+		  "parent %p, child %p, "
+		  "parent id %u, parent_type %#x, "
+		  "child id %u, child_type %#x\n",
+		  tree, search, parent, child,
+		  parent_node->node_id, parent_type,
+		  child_node->node_id, child_type);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (parent_type != SSDFS_BTREE_HYBRID_NODE) {
+		SSDFS_WARN("invalid parent node's type %#x\n",
+			   parent_type);
+		return -ERANGE;
+	}
+
+	if (child_type != SSDFS_BTREE_INDEX_NODE) {
+		SSDFS_WARN("invalid child node's type %#x\n",
+			   child_type);
+		return -ERANGE;
+	}
+
+	parent_height = atomic_read(&parent_node->height);
+	child_height = atomic_read(&child_node->height);
+
+	if ((child_height + 1) != parent_height) {
+		SSDFS_ERR("invalid pair: "
+			  "parent_height %u, child_height %u\n",
+			  parent_height, child_height);
+		return -ERANGE;
+	}
+
+	start_hash = search->request.start.hash;
+	end_hash = search->request.end.hash;
+
+	if (child->flags & SSDFS_BTREE_LEVEL_ADD_NODE) {
+		if (can_add_new_index(parent_node)) {
+			err = ssdfs_btree_prepare_add_index(parent,
+							    start_hash,
+							    end_hash,
+							    parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare level: "
+					  "node_id %u, height %u\n",
+					  parent_node->node_id,
+					  atomic_read(&parent_node->height));
+				return err;
+			}
+		} else if (is_index_area_resizable(parent_node)) {
+			err = ssdfs_btree_prepare_index_area_resize(parent,
+								parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare resize of index area: "
+					  "err %d\n", err);
+				return err;
+			}
+
+			err = ssdfs_btree_prepare_add_index(parent,
+							    start_hash,
+							    end_hash,
+							    parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare level: "
+					  "node_id %u, height %u\n",
+					  parent_node->node_id,
+					  atomic_read(&parent_node->height));
+				return err;
+			}
+		} else {
+			ssdfs_btree_prepare_add_node(tree,
+						     SSDFS_BTREE_HYBRID_NODE,
+						     start_hash, end_hash,
+						     parent, parent_node);
+
+			err = ssdfs_btree_prepare_add_index(parent,
+							    start_hash,
+							    end_hash,
+							    parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare level: "
+					  "node_id %u, height %u\n",
+					  parent_node->node_id,
+					  atomic_read(&parent_node->height));
+				return err;
+			}
+		}
+	} else if (need_update_parent_index_area(start_hash, child_node)) {
+		err = ssdfs_btree_prepare_update_index(parent,
+							start_hash,
+							end_hash,
+							parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare update index: "
+				  "err %d\n", err);
+			return err;
+		}
+	}
+
+	if (!parent->flags) {
+		err = ssdfs_btree_prepare_do_nothing(parent,
+						     parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare hybrid node: "
+				  "err %d\n", err);
+			return err;
+		}
+	}
+
+	return 0;
+}
+
+/*
+ * ssdfs_btree_check_hybrid_hybrid_pair() - check pair of hybrid + hybrid nodes
+ * @tree: btree object
+ * @search: search object
+ * @parent: parent level object
+ * @child: child level object
+ *
+ * This method tries to check the hybrid and hybrid nodes pair.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ */
+static
+int ssdfs_btree_check_hybrid_hybrid_pair(struct ssdfs_btree *tree,
+					 struct ssdfs_btree_search *search,
+					 struct ssdfs_btree_level *parent,
+					 struct ssdfs_btree_level *child)
+{
+	int parent_type, child_type;
+	int parent_height, child_height;
+	struct ssdfs_btree_node *parent_node, *child_node;
+	u64 start_hash, end_hash;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !search);
+	BUG_ON(!parent || !child);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	parent_node = parent->nodes.old_node.ptr;
+
+	if (!parent_node) {
+		SSDFS_ERR("parent is NULL\n");
+		return -ERANGE;
+	}
+
+	child_node = child->nodes.old_node.ptr;
+
+	if (!child_node) {
+		SSDFS_ERR("child is NULL\n");
+		return -ERANGE;
+	}
+
+	parent_type = atomic_read(&parent_node->type);
+	child_type = atomic_read(&child_node->type);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("tree %p, search %p, "
+		  "parent %p, child %p, "
+		  "parent id %u, parent_type %#x, "
+		  "child id %u, child_type %#x\n",
+		  tree, search, parent, child,
+		  parent_node->node_id, parent_type,
+		  child_node->node_id, child_type);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (parent_type != SSDFS_BTREE_HYBRID_NODE) {
+		SSDFS_WARN("invalid parent node's type %#x\n",
+			   parent_type);
+		return -ERANGE;
+	}
+
+	if (child_type != SSDFS_BTREE_HYBRID_NODE) {
+		SSDFS_WARN("invalid child node's type %#x\n",
+			   child_type);
+		return -ERANGE;
+	}
+
+	parent_height = atomic_read(&parent_node->height);
+	child_height = atomic_read(&child_node->height);
+
+	if ((child_height + 1) != parent_height) {
+		SSDFS_ERR("invalid pair: "
+			  "parent_height %u, child_height %u\n",
+			  parent_height, child_height);
+		return -ERANGE;
+	}
+
+	start_hash = search->request.start.hash;
+	end_hash = search->request.end.hash;
+
+	err = ssdfs_btree_define_moving_items(tree, search,
+						parent, child);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to define moving items: "
+			  "err %d\n", err);
+		return err;
+	}
+
+	if (child->flags & SSDFS_BTREE_TRY_RESIZE_INDEX_AREA) {
+		err = ssdfs_btree_define_moving_indexes(parent, child);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to define moving indexes: "
+				  "err %d\n", err);
+			return err;
+		}
+
+		err = ssdfs_btree_prepare_update_index(parent,
+							start_hash,
+							end_hash,
+							parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare update index: "
+				  "err %d\n", err);
+			return err;
+		}
+	} else if (child->flags & SSDFS_BTREE_LEVEL_ADD_NODE) {
+		if (can_add_new_index(parent_node)) {
+			err = ssdfs_btree_prepare_add_index(parent,
+							    start_hash,
+							    end_hash,
+							    parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare level: "
+					  "node_id %u, height %u\n",
+					  parent_node->node_id,
+					  atomic_read(&parent_node->height));
+				return err;
+			}
+		} else if (is_index_area_resizable(parent_node)) {
+			err = ssdfs_btree_prepare_index_area_resize(parent,
+								parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare resize of index area: "
+					  "err %d\n", err);
+				return err;
+			}
+
+			err = ssdfs_btree_prepare_add_index(parent,
+							    start_hash,
+							    end_hash,
+							    parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare level: "
+					  "node_id %u, height %u\n",
+					  parent_node->node_id,
+					  atomic_read(&parent_node->height));
+				return err;
+			}
+		} else {
+			ssdfs_btree_prepare_add_node(tree,
+						     SSDFS_BTREE_HYBRID_NODE,
+						     start_hash, end_hash,
+						     parent, parent_node);
+
+			err = ssdfs_btree_prepare_add_index(parent,
+							    start_hash,
+							    end_hash,
+							    parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare level: "
+					  "node_id %u, height %u\n",
+					  parent_node->node_id,
+					  atomic_read(&parent_node->height));
+				return err;
+			}
+		}
+	} else if (need_update_parent_index_area(start_hash, child_node)) {
+		err = ssdfs_btree_prepare_update_index(parent,
+							start_hash,
+							end_hash,
+							parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare update index: "
+				  "err %d\n", err);
+			return err;
+		}
+	}
+
+	if (!parent->flags) {
+		err = ssdfs_btree_prepare_do_nothing(parent,
+						     parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare index node: "
+				  "err %d\n", err);
+			return err;
+		}
+	}
+
+	return 0;
+}
+
+/*
+ * ssdfs_btree_check_hybrid_leaf_pair() - check pair of hybrid and leaf nodes
+ * @tree: btree object
+ * @search: search object
+ * @parent: parent level object
+ * @child: child level object
+ *
+ * This method tries to check the hybrid and leaf nodes pair.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ */
+static
+int ssdfs_btree_check_hybrid_leaf_pair(struct ssdfs_btree *tree,
+					struct ssdfs_btree_search *search,
+					struct ssdfs_btree_level *parent,
+					struct ssdfs_btree_level *child)
+{
+	int parent_type, child_type;
+	int parent_height, child_height;
+	struct ssdfs_btree_node *parent_node, *child_node;
+	u64 start_hash, end_hash;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !search);
+	BUG_ON(!parent || !child);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	parent_node = parent->nodes.old_node.ptr;
+
+	if (!parent_node) {
+		SSDFS_ERR("parent is NULL\n");
+		return -ERANGE;
+	}
+
+	child_node = child->nodes.old_node.ptr;
+
+	if (!child_node) {
+		SSDFS_ERR("child is NULL\n");
+		return -ERANGE;
+	}
+
+	parent_type = atomic_read(&parent_node->type);
+	child_type = atomic_read(&child_node->type);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("tree %p, search %p, "
+		  "parent %p, child %p, "
+		  "parent id %u, parent_type %#x, "
+		  "child id %u, child_type %#x\n",
+		  tree, search, parent, child,
+		  parent_node->node_id, parent_type,
+		  child_node->node_id, child_type);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (parent_type != SSDFS_BTREE_HYBRID_NODE) {
+		SSDFS_WARN("invalid parent node's type %#x\n",
+			   parent_type);
+		return -ERANGE;
+	}
+
+	if (child_type != SSDFS_BTREE_LEAF_NODE) {
+		SSDFS_WARN("invalid child node's type %#x\n",
+			   child_type);
+		return -ERANGE;
+	}
+
+	parent_height = atomic_read(&parent_node->height);
+	child_height = atomic_read(&child_node->height);
+
+	if ((child_height + 1) != parent_height) {
+		SSDFS_ERR("invalid pair: "
+			  "parent_height %u, child_height %u\n",
+			  parent_height, child_height);
+		return -ERANGE;
+	}
+
+	start_hash = search->request.start.hash;
+	end_hash = search->request.end.hash;
+
+	err = ssdfs_btree_prepare_insert_item(child, search, child_node);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to prepare the insert: "
+			  "node_id %u, height %u\n",
+			  child_node->node_id,
+			  atomic_read(&child_node->height));
+		return err;
+	}
+
+	if (ssdfs_need_move_items_to_sibling(child)) {
+		err = ssdfs_check_capability_move_to_sibling(child);
+		if (err == -ENOSPC) {
+			/*
+			 * It needs to add a node.
+			 */
+			goto try_add_node;
+		} else if (unlikely(err)) {
+			SSDFS_ERR("fail to check moving to sibling: "
+				  "err %d\n", err);
+			return err;
+		}
+
+		err = ssdfs_btree_prepare_update_index(parent,
+						start_hash,
+						end_hash,
+						parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare update: "
+				  "err %d\n", err);
+			return err;
+		}
+
+		return 0;
+	}
+
+try_add_node:
+	ssdfs_btree_prepare_add_node(tree,
+				     SSDFS_BTREE_LEAF_NODE,
+				     start_hash, end_hash,
+				     child, child_node);
+
+	if (can_add_new_index(parent_node)) {
+		err = ssdfs_btree_prepare_add_index(parent,
+						    start_hash,
+						    end_hash,
+						    parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare level: "
+				  "node_id %u, height %u\n",
+				  parent_node->node_id,
+				  atomic_read(&parent_node->height));
+			return err;
+		}
+	} else if (is_index_area_resizable(parent_node)) {
+		err = ssdfs_btree_prepare_index_area_resize(parent,
+							parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare resize: "
+				  "err %d\n", err);
+			return err;
+		}
+
+		err = ssdfs_btree_prepare_add_index(parent,
+						    start_hash,
+						    end_hash,
+						    parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare level: "
+				  "node_id %u, height %u\n",
+				  parent_node->node_id,
+				  atomic_read(&parent_node->height));
+			return err;
+		}
+
+		err = ssdfs_btree_define_moving_items(tree, search,
+							parent, child);
+		if (err == -EAGAIN) {
+			ssdfs_btree_cancel_insert_item(child);
+			ssdfs_btree_cancel_move_items_to_sibling(child);
+			ssdfs_btree_cancel_add_index(parent);
+
+			down_read(&parent_node->header_lock);
+			start_hash = parent_node->items_area.start_hash;
+			up_read(&parent_node->header_lock);
+
+			end_hash = start_hash;
+
+			ssdfs_btree_prepare_add_node(tree,
+						     SSDFS_BTREE_LEAF_NODE,
+						     start_hash, end_hash,
+						     child, child_node);
+
+			err = ssdfs_btree_prepare_add_index(parent,
+							    start_hash,
+							    end_hash,
+							    parent_node);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare level: "
+					  "node_id %u, height %u\n",
+					  parent_node->node_id,
+					  atomic_read(&parent_node->height));
+				return err;
+			}
+
+			err = ssdfs_define_hybrid_node_moving_items(tree,
+								start_hash,
+								end_hash,
+								parent_node,
+								NULL,
+								parent,
+								child);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to prepare level: "
+					  "node_id %u, height %u\n",
+					  parent_node->node_id,
+					  atomic_read(&parent_node->height));
+				return err;
+			}
+
+			/* make first phase of transformation */
+			return -EAGAIN;
+		} else if (unlikely(err)) {
+			SSDFS_ERR("fail to define moving items: "
+				  "err %d\n", err);
+			return err;
+		}
+	} else {
+		ssdfs_btree_prepare_add_node(tree,
+					     SSDFS_BTREE_HYBRID_NODE,
+					     start_hash, end_hash,
+					     parent, parent_node);
+
+		if (ssdfs_need_move_items_to_parent(child)) {
+			err = ssdfs_prepare_move_items_to_parent(search,
+								 parent,
+								 child);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to check moving to parent: "
+					  "err %d\n", err);
+				return err;
+			}
+		}
+
+		err = ssdfs_btree_prepare_add_index(parent,
+						    start_hash,
+						    end_hash,
+						    parent_node);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to prepare level: "
+				  "node_id %u, height %u\n",
+				  parent_node->node_id,
+				  atomic_read(&parent_node->height));
+			return err;
+		}
+	}
+
+	return 0;
+}
+
+/*
+ * ssdfs_btree_check_level_for_add() - check btree's level for adding a node
+ * @tree: btree object
+ * @search: search object
+ * @parent: parent level object
+ * @child: child level object
+ *
+ * This method tries to check the level of btree for adding a node.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENOSPC     - needs to increase the tree's height.
+ */
+int ssdfs_btree_check_level_for_add(struct ssdfs_btree_state_descriptor *desc,
+				    struct ssdfs_btree *tree,
+				    struct ssdfs_btree_search *search,
+				    struct ssdfs_btree_level *parent,
+				    struct ssdfs_btree_level *child)
+{
+	struct ssdfs_btree_node *node = NULL;
+	int parent_type, child_type;
+	int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!desc || !tree || !search);
+	BUG_ON(!parent || !child);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+
+	SSDFS_DBG("tree %p, search %p, parent %p, child %p\n",
+		  tree, search, parent, child);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	parent_type = parent->nodes.old_node.type;
+	if (parent_type != SSDFS_BTREE_NODE_UNKNOWN_TYPE) {
+		BUG_ON(!parent->nodes.old_node.ptr);
+		parent_type = atomic_read(&parent->nodes.old_node.ptr->type);
+	}
+
+	child_type = child->nodes.old_node.type;
+	if (child_type != SSDFS_BTREE_NODE_UNKNOWN_TYPE) {
+		BUG_ON(!child->nodes.old_node.ptr);
+		child_type = atomic_read(&child->nodes.old_node.ptr->type);
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("parent_type %#x, child_type %#x\n",
+		  parent_type, child_type);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	switch (parent_type) {
+	case SSDFS_BTREE_NODE_UNKNOWN_TYPE:
+		switch (child_type) {
+		case SSDFS_BTREE_ROOT_NODE:
+			err = ssdfs_btree_check_nothing_root_pair(tree,
+								  search,
+								  parent,
+								  child);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to check nothing-root pair: "
+					  "err %d\n", err);
+			}
+			break;
+
+		default:
+			err = -ERANGE;
+			SSDFS_ERR("invalid child node's type %#x\n",
+				  child_type);
+		};
+		break;
+
+	case SSDFS_BTREE_ROOT_NODE:
+		switch (child_type) {
+		case SSDFS_BTREE_NODE_UNKNOWN_TYPE:
+			err = ssdfs_btree_check_root_nothing_pair(tree,
+								  search,
+								  parent,
+								  child);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to check root-nothing pair: "
+					  "err %d\n", err);
+			}
+
+			node = parent->nodes.old_node.ptr;
+			if (is_ssdfs_btree_node_index_area_empty(node)) {
+				/* root node should be moved on upper level */
+				desc->increment_height = true;
+				SSDFS_DBG("need to grow the tree height\n");
+			}
+			break;
+
+		case SSDFS_BTREE_INDEX_NODE:
+			err = ssdfs_btree_check_root_index_pair(tree,
+								search,
+								parent,
+								child);
+			if (err == -ENOSPC) {
+				/* root node should be moved on upper level */
+				desc->increment_height = true;
+				SSDFS_DBG("need to grow the tree height\n");
+			} else if (unlikely(err)) {
+				SSDFS_ERR("fail to check root-index pair: "
+					  "err %d\n", err);
+			}
+			break;
+
+		case SSDFS_BTREE_HYBRID_NODE:
+			err = ssdfs_btree_check_root_hybrid_pair(tree,
+								 search,
+								 parent,
+								 child);
+			if (err == -ENOSPC) {
+				/* root node should be moved on upper level */
+				desc->increment_height = true;
+				SSDFS_DBG("need to grow the tree height\n");
+			} else if (unlikely(err)) {
+				SSDFS_ERR("fail to check root-hybrid pair: "
+					  "err %d\n", err);
+			}
+			break;
+
+		case SSDFS_BTREE_LEAF_NODE:
+			err = ssdfs_btree_check_root_leaf_pair(tree,
+								search,
+								parent,
+								child);
+			if (err == -ENOSPC) {
+				/* root node should be moved on upper level */
+				desc->increment_height = true;
+				SSDFS_DBG("need to grow the tree height\n");
+			} else if (unlikely(err)) {
+				SSDFS_ERR("fail to check root-leaf pair: "
+					  "err %d\n", err);
+			}
+			break;
+
+		default:
+			err = -ERANGE;
+			SSDFS_ERR("invalid child node's type %#x\n",
+				  child_type);
+		};
+		break;
+
+	case SSDFS_BTREE_INDEX_NODE:
+		switch (child_type) {
+		case SSDFS_BTREE_INDEX_NODE:
+			err = ssdfs_btree_check_index_index_pair(tree,
+								 search,
+								 parent,
+								 child);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to check index-index pair: "
+					  "err %d\n", err);
+			}
+			break;
+
+		case SSDFS_BTREE_HYBRID_NODE:
+			err = ssdfs_btree_check_index_hybrid_pair(tree,
+								  search,
+								  parent,
+								  child);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to check index-hybrid pair: "
+					  "err %d\n", err);
+			}
+			break;
+
+		case SSDFS_BTREE_LEAF_NODE:
+			err = ssdfs_btree_check_index_leaf_pair(tree,
+								search,
+								parent,
+								child);
+			if (err == -EAGAIN) {
+#ifdef CONFIG_SSDFS_DEBUG
+				SSDFS_DBG("need to prepare hierarchy: "
+					  "err %d\n", err);
+#endif /* CONFIG_SSDFS_DEBUG */
+			} else if (unlikely(err)) {
+				SSDFS_ERR("fail to check index-leaf pair: "
+					  "err %d\n", err);
+			}
+			break;
+
+		default:
+			err = -ERANGE;
+			SSDFS_ERR("invalid child node's type %#x\n",
+				  child_type);
+		};
+		break;
+
+	case SSDFS_BTREE_HYBRID_NODE:
+		switch (child_type) {
+		case SSDFS_BTREE_NODE_UNKNOWN_TYPE:
+			err = ssdfs_btree_check_hybrid_nothing_pair(tree,
+								  search,
+								  parent,
+								  child);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to check hybrid-nothing pair: "
+					  "err %d\n", err);
+			}
+			break;
+
+		case SSDFS_BTREE_INDEX_NODE:
+			err = ssdfs_btree_check_hybrid_index_pair(tree,
+								  search,
+								  parent,
+								  child);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to check hybrid-index pair: "
+					  "err %d\n", err);
+			}
+			break;
+
+		case SSDFS_BTREE_HYBRID_NODE:
+			err = ssdfs_btree_check_hybrid_hybrid_pair(tree,
+								   search,
+								   parent,
+								   child);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to check hybrid-hybrid pair: "
+					  "err %d\n", err);
+			}
+			break;
+
+		case SSDFS_BTREE_LEAF_NODE:
+			err = ssdfs_btree_check_hybrid_leaf_pair(tree,
+								 search,
+								 parent,
+								 child);
+			if (err == -EAGAIN) {
+#ifdef CONFIG_SSDFS_DEBUG
+				SSDFS_DBG("need to prepare hierarchy: "
+					  "err %d\n", err);
+#endif /* CONFIG_SSDFS_DEBUG */
+			} else if (unlikely(err)) {
+				SSDFS_ERR("fail to check hybrid-leaf pair: "
+					  "err %d\n", err);
+			}
+			break;
+
+		default:
+			err = -ERANGE;
+			SSDFS_ERR("invalid child node's type %#x\n",
+				  child_type);
+		};
+		break;
+
+	default:
+		err = -ERANGE;
+		SSDFS_ERR("invalid parent node's type %#x\n",
+			  parent_type);
+	}
+
+	return err;
+}
+
+/*
+ * ssdfs_btree_descend_to_leaf_node() - descend to a leaf node
+ * @tree: btree object
+ * @search: search object
+ *
+ * This method tries to descend from the current level till a leaf node.
+ *
+ * RETURN:
+ * [success] - pointer on a leaf node.
+ * [failure] - error code:
+ *
+ * %-ERANGE     - internal error.
+ */
+static
+struct ssdfs_btree_node *
+ssdfs_btree_descend_to_leaf_node(struct ssdfs_btree *tree,
+				 struct ssdfs_btree_search *search)
+{
+	struct ssdfs_btree_node *node = NULL;
+	int type;
+	u64 upper_hash;
+	u64 start_item_hash;
+	u16 items_count;
+	u32 prev_node_id;
+	int counter = 0;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !search);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+
+	SSDFS_DBG("tree %p, search %p\n",
+		  tree, search);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (search->node.height == SSDFS_BTREE_LEAF_NODE_HEIGHT) {
+		SSDFS_DBG("search object contains leaf node\n");
+		return 0;
+	}
+
+	if (!search->node.child) {
+		err = -ERANGE;
+		SSDFS_ERR("child node object is NULL\n");
+		return ERR_PTR(err);
+	}
+
+	type = atomic_read(&search->node.child->type);
+	if (type != SSDFS_BTREE_HYBRID_NODE) {
+		err = -ERANGE;
+		SSDFS_ERR("invalid search object: "
+			  "height %u, node_type %#x\n",
+			  atomic_read(&search->node.child->height),
+			  type);
+		return ERR_PTR(err);
+	}
+
+	if (!is_ssdfs_btree_node_index_area_exist(search->node.child)) {
+		err = -ERANGE;
+		SSDFS_ERR("index area is absent: "
+			  "node_id %u\n",
+			  search->node.child->node_id);
+		return ERR_PTR(err);
+	}
+
+	down_read(&search->node.child->header_lock);
+	items_count = search->node.child->items_area.items_count;
+	start_item_hash = search->node.child->items_area.start_hash;
+	upper_hash = search->node.child->index_area.end_hash;
+	up_read(&search->node.child->header_lock);
+
+	if (upper_hash >= U64_MAX) {
+		err = -ERANGE;
+		SSDFS_ERR("invalid upper hash\n");
+		return ERR_PTR(err);
+	}
+
+	node = search->node.child;
+	prev_node_id = node->node_id;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("node_id %u, items_count %u, "
+		  "start_item_hash %llx, end_index_hash %llx\n",
+		  node->node_id, items_count,
+		  start_item_hash, upper_hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (type == SSDFS_BTREE_HYBRID_NODE) {
+		if (items_count == 0)
+			return node;
+		else if (start_item_hash >= U64_MAX) {
+			err = -ERANGE;
+			SSDFS_ERR("invalid start_item_hash %llx\n",
+				  start_item_hash);
+			return ERR_PTR(err);
+		}
+
+		if (start_item_hash == upper_hash)
+			return node;
+	}
+
+	do {
+		node = ssdfs_btree_get_child_node_for_hash(tree, node,
+							   upper_hash);
+		if (IS_ERR_OR_NULL(node)) {
+			err = !node ? -ERANGE : PTR_ERR(node);
+			SSDFS_ERR("fail to get the child node: err %d\n",
+				  err);
+			return node;
+		}
+
+		if (prev_node_id == node->node_id) {
+			counter++;
+
+			if (counter > 3) {
+				SSDFS_ERR("infinite cycle suspected: "
+					  "node_id %u, counter %d\n",
+					  node->node_id,
+					  counter);
+				return ERR_PTR(-ERANGE);
+			}
+		} else
+			prev_node_id = node->node_id;
+
+		type = atomic_read(&node->type);
+
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("node_id %u, type %#x, "
+			  "end_index_hash %llx\n",
+			  node->node_id, atomic_read(&node->type),
+			  upper_hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+		switch (type) {
+		case SSDFS_BTREE_LEAF_NODE:
+			/* do nothing */
+			break;
+
+		case SSDFS_BTREE_HYBRID_NODE:
+		case SSDFS_BTREE_INDEX_NODE:
+			if (!is_ssdfs_btree_node_index_area_exist(node)) {
+				err = -ERANGE;
+				SSDFS_ERR("index area is absent: "
+					  "node_id %u\n",
+					  node->node_id);
+				return ERR_PTR(err);
+			}
+
+			down_read(&node->header_lock);
+			upper_hash = node->index_area.end_hash;
+			up_read(&node->header_lock);
+
+			if (upper_hash == U64_MAX) {
+				err = -ERANGE;
+				SSDFS_ERR("invalid upper hash\n");
+				return ERR_PTR(err);
+			}
+			break;
+
+		default:
+			err = -ERANGE;
+			SSDFS_ERR("invalid node type: "
+				  "node_id %u, height %u, type %#x\n",
+				  node->node_id,
+				  atomic_read(&node->height),
+				  type);
+			return ERR_PTR(err);
+		}
+	} while (type != SSDFS_BTREE_LEAF_NODE);
+
+	switch (atomic_read(&node->state)) {
+	case SSDFS_BTREE_NODE_INITIALIZED:
+	case SSDFS_BTREE_NODE_DIRTY:
+		/* expected state */
+		break;
+
+	default:
+		err = -ERANGE;
+		SSDFS_ERR("invalid node state %#x\n",
+			  atomic_read(&node->state));
+		return ERR_PTR(err);
+	}
+
+	switch (atomic_read(&node->items_area.state)) {
+	case SSDFS_BTREE_NODE_ITEMS_AREA_EXIST:
+		/* expected state */
+		break;
+
+	default:
+		err = -ERANGE;
+		SSDFS_WARN("invalid items area state: node_id %u\n",
+			   search->node.id);
+		return ERR_PTR(err);
+	}
+
+	return node;
+}
+
+static
+void ssdfs_btree_hierarchy_init_hash_range(struct ssdfs_btree_level *level,
+					   struct ssdfs_btree_node *node)
+{
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!level);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (!node)
+		return;
+
+	down_read(&node->header_lock);
+	switch (atomic_read(&node->type)) {
+	case SSDFS_BTREE_ROOT_NODE:
+	case SSDFS_BTREE_INDEX_NODE:
+		level->nodes.old_node.index_hash.start =
+					node->index_area.start_hash;
+		level->nodes.old_node.index_hash.end =
+					node->index_area.end_hash;
+		break;
+
+	case SSDFS_BTREE_HYBRID_NODE:
+		level->nodes.old_node.index_hash.start =
+					node->index_area.start_hash;
+		level->nodes.old_node.index_hash.end =
+					node->index_area.end_hash;
+		level->nodes.old_node.items_hash.start =
+					node->items_area.start_hash;
+		level->nodes.old_node.items_hash.end =
+					node->items_area.end_hash;
+		break;
+
+	case SSDFS_BTREE_LEAF_NODE:
+		level->nodes.old_node.items_hash.start =
+					node->items_area.start_hash;
+		level->nodes.old_node.items_hash.end =
+					node->items_area.end_hash;
+		break;
+
+	default:
+		SSDFS_WARN("unexpected node type %#x\n",
+			   atomic_read(&node->type));
+		break;
+	}
+	up_read(&node->header_lock);
+}
+
+/*
+ * ssdfs_btree_check_hierarchy_for_add() - check the btree for add node
+ * @tree: btree object
+ * @search: search object
+ * @hierarchy: btree's hierarchy object
+ *
+ * This method tries to check the btree's hierarchy for operation of
+ * node addition.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-ERANGE     - internal error.
+ */
+int ssdfs_btree_check_hierarchy_for_add(struct ssdfs_btree *tree,
+					struct ssdfs_btree_search *search,
+					struct ssdfs_btree_hierarchy *hierarchy)
+{
+	struct ssdfs_btree_level *level;
+	struct ssdfs_btree_node *parent_node, *child_node;
+	int child_node_height, cur_height, tree_height;
+	int parent_node_type, child_node_type;
+	spinlock_t *lock = NULL;
+	int err;
+	int res = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!tree || !search || !hierarchy);
+	BUG_ON(!rwsem_is_locked(&tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+	SSDFS_ERR("tree %p, search %p, hierarchy %p\n",
+		  tree, search, hierarchy);
+#else
+	SSDFS_DBG("tree %p, search %p, hierarchy %p\n",
+		  tree, search, hierarchy);
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+	tree_height = atomic_read(&tree->height);
+	if (tree_height <= 0) {
+		SSDFS_ERR("invalid tree_height %d\n",
+			  tree_height);
+		return -ERANGE;
+	}
+
+	if (search->node.id == SSDFS_BTREE_ROOT_NODE_ID) {
+		if (tree_height <= 0 || tree_height > 1) {
+			SSDFS_ERR("invalid search object state: "
+				  "tree_height %u, node_id %u\n",
+				  tree_height,
+				  search->node.id);
+			return -ERANGE;
+		}
+
+		child_node = search->node.child;
+		parent_node = search->node.parent;
+
+		if (child_node || !parent_node) {
+			SSDFS_ERR("invalid search object state: "
+				  "child_node %p, parent_node %p\n",
+				  child_node, parent_node);
+			return -ERANGE;
+		}
+
+		parent_node_type = atomic_read(&parent_node->type);
+		child_node_type = SSDFS_BTREE_NODE_UNKNOWN_TYPE;
+
+		if (parent_node_type != SSDFS_BTREE_ROOT_NODE) {
+			SSDFS_ERR("invalid parent node's type %#x\n",
+				  parent_node_type);
+			return -ERANGE;
+		}
+
+		child_node_height = search->node.height;
+	} else {
+		child_node = search->node.child;
+		parent_node = search->node.parent;
+
+		if (!child_node || !parent_node) {
+			SSDFS_ERR("invalid search object state: "
+				  "child_node %p, parent_node %p\n",
+				  child_node, parent_node);
+			return -ERANGE;
+		}
+
+		switch (atomic_read(&child_node->type)) {
+		case SSDFS_BTREE_LEAF_NODE:
+			/* do nothing */
+			break;
+
+		case SSDFS_BTREE_HYBRID_NODE:
+			child_node = ssdfs_btree_descend_to_leaf_node(tree,
+								      search);
+			if (unlikely(IS_ERR_OR_NULL(child_node))) {
+				err = !child_node ?
+					-ERANGE : PTR_ERR(child_node);
+				SSDFS_ERR("fail to descend to leaf node: "
+					  "err %d\n", err);
+				return err;
+			}
+
+			lock = &child_node->descriptor_lock;
+			spin_lock(lock);
+			parent_node = child_node->parent_node;
+			spin_unlock(lock);
+			lock = NULL;
+
+			if (!child_node || !parent_node) {
+				SSDFS_ERR("invalid search object state: "
+					  "child_node %p, parent_node %p\n",
+					  child_node, parent_node);
+				return -ERANGE;
+			}
+			break;
+
+		default:
+			SSDFS_ERR("invalid child node's type %#x\n",
+				  atomic_read(&child_node->type));
+			return -ERANGE;
+		}
+
+		parent_node_type = atomic_read(&parent_node->type);
+		child_node_type = atomic_read(&child_node->type);
+
+		switch (child_node_type) {
+		case SSDFS_BTREE_LEAF_NODE:
+		case SSDFS_BTREE_HYBRID_NODE:
+			/* expected state */
+			break;
+
+		default:
+			SSDFS_ERR("invalid child node's type %#x\n",
+				  child_node_type);
+			return -ERANGE;
+		}
+
+		child_node_height = atomic_read(&child_node->height);
+	}
+
+	cur_height = child_node_height;
+	if (cur_height > tree_height) {
+		SSDFS_ERR("cur_height %u > tree_height %u\n",
+			  cur_height, tree_height);
+		return -ERANGE;
+	}
+
+	if ((cur_height + 1) >= hierarchy->desc.height) {
+		SSDFS_ERR("invalid hierarchy: "
+			  "tree_height %u, cur_height %u, "
+			  "hierarchy->desc.height %u\n",
+			  tree_height, cur_height,
+			  hierarchy->desc.height);
+		return -ERANGE;
+	}
+
+	level = hierarchy->array_ptr[cur_height];
+	level->nodes.old_node.type = child_node_type;
+	level->nodes.old_node.ptr = child_node;
+	ssdfs_btree_hierarchy_init_hash_range(level, child_node);
+
+	cur_height++;
+	level = hierarchy->array_ptr[cur_height];
+	level->nodes.old_node.type = parent_node_type;
+	level->nodes.old_node.ptr = parent_node;
+	ssdfs_btree_hierarchy_init_hash_range(level, parent_node);
+
+	cur_height++;
+	lock = &parent_node->descriptor_lock;
+	spin_lock(lock);
+	parent_node = parent_node->parent_node;
+	spin_unlock(lock);
+	lock = NULL;
+	for (; cur_height < tree_height; cur_height++) {
+		if (!parent_node) {
+			SSDFS_ERR("parent node is NULL\n");
+			return -ERANGE;
+		}
+
+		parent_node_type = atomic_read(&parent_node->type);
+		level = hierarchy->array_ptr[cur_height];
+		level->nodes.old_node.type = parent_node_type;
+		level->nodes.old_node.ptr = parent_node;
+		ssdfs_btree_hierarchy_init_hash_range(level, parent_node);
+
+		lock = &parent_node->descriptor_lock;
+		spin_lock(lock);
+		parent_node = parent_node->parent_node;
+		spin_unlock(lock);
+		lock = NULL;
+	}
+
+	cur_height = child_node_height;
+
+	if (child_node_type == SSDFS_BTREE_HYBRID_NODE) {
+#ifdef CONFIG_SSDFS_DEBUG
+		BUG_ON(cur_height < 1);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+		cur_height--;
+	}
+
+	for (; cur_height <= tree_height; cur_height++) {
+		struct ssdfs_btree_level *parent;
+		struct ssdfs_btree_level *child;
+
+		parent = hierarchy->array_ptr[cur_height + 1];
+		child = hierarchy->array_ptr[cur_height];
+
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("cur_height %d, tree_height %d\n",
+			  cur_height, tree_height);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+		err = ssdfs_btree_check_level_for_add(&hierarchy->desc,
+						      tree, search,
+						      parent, child);
+		if (err == -EAGAIN) {
+			res = -EAGAIN;
+			err = 0;
+			ssdfs_debug_btree_hierarchy_object(hierarchy);
+			SSDFS_DBG("need to prepare btree hierarchy for add\n");
+			/* continue logic for upper layers */
+			continue;
+		} else if (err == -ENOSPC) {
+			if ((cur_height + 1) != (tree_height - 1)) {
+				ssdfs_debug_btree_hierarchy_object(hierarchy);
+				SSDFS_ERR("invalid current height: "
+					  "cur_height %u, tree_height %u\n",
+					  cur_height, tree_height);
+				return -ERANGE;
+			} else {
+				err = 0;
+				continue;
+			}
+		} else if (unlikely(err)) {
+			ssdfs_debug_btree_hierarchy_object(hierarchy);
+			SSDFS_ERR("fail to check btree's level: "
+				  "cur_height %u, tree_height %u, "
+				  "err %d\n",
+				  cur_height, tree_height, err);
+			return err;
+		} else if ((cur_height + 1) >= tree_height)
+			break;
+	}
+
+#ifdef CONFIG_SSDFS_TRACK_API_CALL
+	SSDFS_ERR("finished\n");
+#endif /* CONFIG_SSDFS_TRACK_API_CALL */
+
+	ssdfs_debug_btree_hierarchy_object(hierarchy);
+
+	return res;
+}
