diff --git a/fs/ssdfs/btree_node.c b/fs/ssdfs/btree_node.c
index a826b1c9699d..f4402cb8df64 100644
--- a/fs/ssdfs/btree_node.c
+++ b/fs/ssdfs/btree_node.c
@@ -5222,3 +5222,2988 @@ bool is_ssdfs_node_shared(struct ssdfs_btree_node *node)
 
 	return atomic_read(&node->refs_count) > 1;
 }
+
+/*
+ * ssdfs_btree_root_node_find_index() - find index record in root node
+ * @node: node object
+ * search_hash: hash for search in the index area
+ * @found_index: identification number of found index [out]
+ *
+ * This method tries to find the index record for the requested hash.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-ENODATA    - unable to find the node's index.
+ * %-EEXIST     - search hash has been found.
+ */
+static
+int ssdfs_btree_root_node_find_index(struct ssdfs_btree_node *node,
+				     u64 search_hash,
+				     u16 *found_index)
+{
+	int i;
+	int err = -ENODATA;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node || !found_index);
+	BUG_ON(!rwsem_is_locked(&node->header_lock));
+
+	SSDFS_DBG("node_id %u, node_type %#x, search_hash %llx\n",
+		  node->node_id, atomic_read(&node->type),
+		  search_hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	*found_index = U16_MAX;
+
+	for (i = 0; i < SSDFS_BTREE_ROOT_NODE_INDEX_COUNT; i++) {
+		struct ssdfs_btree_index *ptr = &node->raw.root_node.indexes[i];
+		u64 hash = le64_to_cpu(ptr->hash);
+
+		if (hash == U64_MAX)
+			break;
+
+		if (search_hash < hash)
+			break;
+
+		err = 0;
+		*found_index = i;
+
+		if (search_hash == hash) {
+			err = -EEXIST;
+			break;
+		}
+	}
+
+	return err;
+}
+
+#define CUR_INDEX(kaddr, page_off, index) \
+	((struct ssdfs_btree_index_key *)((u8 *)kaddr + \
+	 page_off + (index * sizeof(struct ssdfs_btree_index_key))))
+
+/*
+ * ssdfs_get_index_key_hash() - get hash from a range
+ * @node: node object
+ * @kaddr: pointer on starting address in the page
+ * @page_off: offset from page's beginning in bytes
+ * @index: requested starting index in the range
+ * @upper_index: last index in the available range
+ * @hash_index: available (not locked) index in the range [out]
+ * @hash: hash value of found index [out]
+ *
+ * This method tries to find any unlocked index in suggested
+ * range.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-ENODATA    - unable to find the node's index.
+ */
+static
+int ssdfs_get_index_key_hash(struct ssdfs_btree_node *node,
+			     void *kaddr, u32 page_off,
+			     u32 index, u32 upper_index,
+			     u32 *hash_index, u64 *hash)
+{
+	struct ssdfs_btree_index_key *ptr;
+	int err = -ENODATA;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node || !kaddr || !hash_index || !hash);
+	BUG_ON(!rwsem_is_locked(&node->full_lock));
+
+	SSDFS_DBG("kaddr %p, page_off %u, "
+		  "index %u, upper_index %u\n",
+		  kaddr, page_off, index, upper_index);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	*hash = U64_MAX;
+
+	for (*hash_index = index; *hash_index <= upper_index; ++(*hash_index)) {
+		err = ssdfs_lock_index_range(node, *hash_index, 1);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to lock index %u, err %d\n",
+				  *hash_index, err);
+			break;
+		}
+
+		err = -EEXIST;
+		ptr = CUR_INDEX(kaddr, page_off, *hash_index);
+		*hash = le64_to_cpu(ptr->index.hash);
+
+		ssdfs_unlock_index_range(node, *hash_index, 1);
+
+		if (err == -EEXIST) {
+			err = 0;
+			break;
+		} else if (err == -ENODATA)
+			continue;
+		else if (unlikely(err))
+			break;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("hash_index %u, hash %llx\n",
+		  *hash_index, *hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	return err;
+}
+
+/*
+ * ssdfs_check_last_index() - check last index in the search
+ * @node: node object
+ * @kaddr: pointer on starting address in the page
+ * @page_off: offset from page's beginning in bytes
+ * @index: requested index for the check
+ * @search_hash: hash for search
+ * @range_start: first index in the index area
+ * @range_end: last index in the index area
+ * @prev_found: processed index on previous iteration
+ * @found_index: value of found index [out]
+ *
+ * This method tries to check the index for the case when
+ * range has only one index.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-ERANGE     - internal error.
+ * %-ENOENT     - requested hash is located in previous range.
+ * %-ENODATA    - unable to find the node's index.
+ */
+static
+int ssdfs_check_last_index(struct ssdfs_btree_node *node,
+			   void *kaddr, u32 page_off,
+			   u32 index, u64 search_hash,
+			   u32 range_start, u32 range_end,
+			   u32 prev_found, u16 *found_index)
+{
+	u32 hash_index;
+	u64 hash;
+	int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node || !kaddr || !found_index);
+	BUG_ON(!rwsem_is_locked(&node->full_lock));
+
+	SSDFS_DBG("kaddr %p, page_off %u, "
+		  "index %u, search_hash %llx, "
+		  "range_start %u, range_end %u, "
+		  "prev_found %u\n",
+		  kaddr, page_off, index, search_hash,
+		  range_start, range_end, prev_found);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	err = ssdfs_get_index_key_hash(node, kaddr, page_off,
+					index, index,
+					&hash_index, &hash);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to get hash: "
+			  "index %u, err %d\n",
+			  index, err);
+		return err;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("hash_index %u, hash %llx\n",
+		  hash_index, hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (hash_index != index) {
+		SSDFS_ERR("hash_index %u != index %u\n",
+			  hash_index, index);
+		return -ERANGE;
+	}
+
+	if (search_hash < hash) {
+		err = -ENOENT;
+
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("unable to find index: "
+			  "index %u, search_hash %llx, "
+			  "hash %llx\n",
+			  hash_index, search_hash,
+			  hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+		if (prev_found < U16_MAX)
+			*found_index = prev_found;
+		else
+			*found_index = hash_index;
+	} else if (search_hash == hash) {
+		err = 0;
+		*found_index = hash_index;
+	} else {
+		err = -ENODATA;
+		*found_index = hash_index;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("prev_found %u, found_index %u\n",
+		  prev_found, *found_index);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	return err;
+}
+
+/*
+ * ssdfs_check_last_index_pair() - check last pair of indexes in the search
+ * @node: node object
+ * @kaddr: pointer on starting address in the page
+ * @page_off: offset from page's beginning in bytes
+ * @lower_index: starting index in the search
+ * @upper_index: ending index in the search
+ * @search_hash: hash for search
+ * @range_start: first index in the index area
+ * @range_end: last index in the index area
+ * @prev_found: processed index on previous iteration
+ * @found_index: value of found index [out]
+ *
+ * This method tries to find an index for the case when
+ * range has only two indexes.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-ERANGE     - internal error.
+ * %-ENOENT     - requested hash is located in previous range.
+ * %-ENODATA    - unable to find the node's index.
+ */
+static
+int ssdfs_check_last_index_pair(struct ssdfs_btree_node *node,
+				void *kaddr, u32 page_off,
+				u32 lower_index, u32 upper_index,
+				u64 search_hash,
+				u32 range_start, u32 range_end,
+				u32 prev_found, u16 *found_index)
+{
+	u32 hash_index;
+	u64 hash;
+	int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node || !kaddr || !found_index);
+	BUG_ON(!rwsem_is_locked(&node->full_lock));
+
+	SSDFS_DBG("kaddr %p, page_off %u, "
+		  "lower_index %u, upper_index %u, "
+		  "search_hash %llx, range_start %u, prev_found %u\n",
+		  kaddr, page_off, lower_index, upper_index,
+		  search_hash, range_start, prev_found);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	err = ssdfs_get_index_key_hash(node, kaddr, page_off,
+					lower_index, upper_index,
+					&hash_index, &hash);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to get hash: "
+			  "lower_index %u, upper_index %u, err %d\n",
+			  lower_index, upper_index, err);
+		return err;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("hash_index %u, hash %llx\n",
+		  hash_index, hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (hash_index == lower_index) {
+		if (search_hash < hash) {
+			err = -ENOENT;
+
+#ifdef CONFIG_SSDFS_DEBUG
+			SSDFS_DBG("unable to find index: "
+				  "index %u, search_hash %llx, "
+				  "hash %llx\n",
+				  hash_index, search_hash,
+				  hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+			if (prev_found < U16_MAX)
+				*found_index = prev_found;
+			else
+				*found_index = hash_index;
+		} else if (search_hash == hash) {
+			err = 0;
+			*found_index = hash_index;
+		} else {
+			prev_found = hash_index;
+			err = ssdfs_check_last_index(node, kaddr, page_off,
+						     upper_index, search_hash,
+						     range_start, range_end,
+						     prev_found, found_index);
+			if (err == -ENOENT) {
+				err = 0;
+				*found_index = prev_found;
+			}
+		}
+	} else if (hash_index == upper_index) {
+		if (search_hash > hash) {
+			err = -ENODATA;
+			*found_index = upper_index;
+		} else if (search_hash == hash) {
+			err = 0;
+			*found_index = upper_index;
+		} else {
+			prev_found = hash_index;
+			err = ssdfs_check_last_index(node, kaddr, page_off,
+						     lower_index, search_hash,
+						     range_start, range_end,
+						     prev_found, found_index);
+			if (err == -ENOENT) {
+				err = 0;
+				*found_index = prev_found;
+			}
+		}
+	} else {
+		SSDFS_ERR("invalid index: hash_index %u, "
+			  "lower_index %u, upper_index %u\n",
+			  hash_index, lower_index, upper_index);
+		return -ERANGE;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("prev_found %u, found_index %u, err %d\n",
+		  prev_found, *found_index, err);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	return err;
+}
+
+/*
+ * ssdfs_find_index_in_memory_page() - find index record in memory page
+ * @node: node object
+ * @area: description of index area
+ * @start_offset: offset in the index area of the node
+ * search_hash: hash for search in the index area
+ * @found_index: identification number of found index [out]
+ * @processed_bytes: amount of processed bytes into index area [out]
+ *
+ * This method tries to find the index record for the requested hash.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-ERANGE     - internal error.
+ * %-ENODATA    - unable to find the node's index.
+ * %-ENOENT     - index record is outside of this memory page.
+ */
+static
+int ssdfs_find_index_in_memory_page(struct ssdfs_btree_node *node,
+				    struct ssdfs_btree_node_index_area *area,
+				    u32 start_offset,
+				    u64 search_hash,
+				    u16 *found_index,
+				    u32 *processed_bytes)
+{
+	struct page *page;
+	void *kaddr;
+	u32 page_index;
+	u32 page_off;
+	u32 search_bytes;
+	u32 index_count;
+	u32 cur_index, upper_index, lower_index;
+	u32 range_start, range_end;
+	u32 prev_found;
+	u64 hash;
+	u32 processed_indexes = 0;
+	int err = -ENODATA;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node || !area || !processed_bytes || !found_index);
+	BUG_ON(!rwsem_is_locked(&node->full_lock));
+
+	SSDFS_DBG("node_id %u, node_type %#x, "
+		  "start_offset %u, search_hash %llx\n",
+		  node->node_id, atomic_read(&node->type),
+		  start_offset, search_hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	*found_index = U16_MAX;
+	*processed_bytes = 0;
+
+	if (start_offset >= (area->offset + area->area_size)) {
+		SSDFS_ERR("invalid start_offset: "
+			  "offset %u, area_start %u, area_size %u\n",
+			  start_offset, area->offset, area->area_size);
+		return -ERANGE;
+	}
+
+	if (area->index_size != sizeof(struct ssdfs_btree_index_key)) {
+		SSDFS_ERR("invalid index size %u\n",
+			  area->index_size);
+		return -ERANGE;
+	}
+
+	page_index = start_offset >> PAGE_SHIFT;
+	page_off = start_offset % PAGE_SIZE;
+
+	if ((page_off + area->index_size) > PAGE_SIZE) {
+		SSDFS_ERR("invalid offset into the page: "
+			  "offset %u, index_size %u\n",
+			  page_off, area->index_size);
+		return -ERANGE;
+	}
+
+	if (page_index == 0 && page_off < area->offset) {
+		SSDFS_ERR("page_off %u < area->offset %u\n",
+			  page_off, area->offset);
+		return -ERANGE;
+	}
+
+	if (page_off % area->index_size) {
+		SSDFS_ERR("offset is not aligned: "
+			  "page_off %u, index_size %u\n",
+			  page_off, area->index_size);
+		return -ERANGE;
+	}
+
+	if (page_index >= pagevec_count(&node->content.pvec)) {
+		SSDFS_ERR("invalid page index: "
+			  "page_index %u, pagevec_count %u\n",
+			  page_index,
+			  pagevec_count(&node->content.pvec));
+		return -ERANGE;
+	}
+
+	search_bytes = PAGE_SIZE - page_off;
+	search_bytes = min_t(u32, search_bytes,
+			(area->offset + area->area_size) - start_offset);
+
+	index_count = search_bytes / area->index_size;
+	if (index_count == 0) {
+		SSDFS_ERR("invalid index_count %u\n",
+			  index_count);
+		return -ERANGE;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("search_bytes %u, offset %u, area_size %u\n",
+		  search_bytes, area->offset, area->area_size);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	processed_indexes = (start_offset - area->offset);
+	processed_indexes /= area->index_size;
+
+	if (processed_indexes >= area->index_capacity) {
+		SSDFS_ERR("processed_indexes %u >= area->index_capacity %u\n",
+			  processed_indexes,
+			  area->index_capacity);
+		return -ERANGE;
+	} else if (processed_indexes >= area->index_count) {
+		err = -ENOENT;
+		*processed_bytes = search_bytes;
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("unable to find an index: "
+			  "processed_indexes %u, area->index_count %u\n",
+			  processed_indexes,
+			  area->index_count);
+#endif /* CONFIG_SSDFS_DEBUG */
+		return -ENOENT;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("area->index_count %u, area->index_capacity %u\n",
+		  area->index_count, area->index_capacity);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	index_count = min_t(u32, index_count,
+				area->index_count - processed_indexes);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("area->index_count %u, processed_indexes %u, "
+		  "index_count %u\n",
+		  area->index_count, processed_indexes, index_count);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	cur_index = 0;
+	range_start = lower_index = 0;
+	range_end = upper_index = index_count - 1;
+
+	page = node->content.pvec.pages[page_index];
+	kaddr = kmap_local_page(page);
+
+	prev_found = *found_index;
+	while (lower_index <= upper_index) {
+		int diff = upper_index - lower_index;
+		u32 hash_index;
+
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("lower_index %u, upper_index %u, diff %d\n",
+			  lower_index, upper_index, diff);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+		if (diff < 0) {
+			err = -ERANGE;
+			SSDFS_ERR("invalid diff: "
+				  "diff %d, lower_index %u, "
+				  "upper_index %u\n",
+				  diff, lower_index, upper_index);
+			goto finish_search;
+		}
+
+		if (diff == 0) {
+			err = ssdfs_check_last_index(node, kaddr, page_off,
+						     lower_index, search_hash,
+						     range_start, range_end,
+						     prev_found, found_index);
+			if (err == -ENOENT) {
+				if (prev_found < U16_MAX)
+					*found_index = prev_found;
+			} else if (err == -ENODATA) {
+				/*
+				 * Nothing was found
+				 */
+			} else if (unlikely(err)) {
+				SSDFS_ERR("fail to check the last index: "
+					  "index %u, err %d\n",
+					  lower_index, err);
+			}
+
+			*processed_bytes = search_bytes;
+			goto finish_search;
+		} else if (diff == 1) {
+			err = ssdfs_check_last_index_pair(node, kaddr,
+							  page_off,
+							  lower_index,
+							  upper_index,
+							  search_hash,
+							  range_start,
+							  range_end,
+							  prev_found,
+							  found_index);
+			if (err == -ENOENT) {
+				if (prev_found < U16_MAX)
+					*found_index = prev_found;
+			} else if (err == -ENODATA) {
+				/*
+				 * Nothing was found
+				 */
+			} else if (unlikely(err)) {
+				SSDFS_ERR("fail to check the last index pair: "
+					  "lower_index %u, upper_index %u, "
+					  "err %d\n",
+					  lower_index, upper_index, err);
+			}
+
+			*processed_bytes = search_bytes;
+			goto finish_search;
+		} else
+			cur_index = lower_index + (diff / 2);
+
+
+		err = ssdfs_get_index_key_hash(node, kaddr, page_off,
+						cur_index, upper_index,
+						&hash_index, &hash);
+		if (unlikely(err)) {
+			SSDFS_WARN("fail to get hash: "
+				  "cur_index %u, upper_index %u, err %d\n",
+				  cur_index, upper_index, err);
+			goto finish_search;
+		}
+
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("search_hash %llx, hash %llx, "
+			  "hash_index %u, range_start %u, range_end %u\n",
+			  search_hash, hash, hash_index,
+			  range_start, range_end);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+		if (search_hash < hash) {
+			if (hash_index == range_start) {
+				err = -ENOENT;
+				*found_index = hash_index;
+#ifdef CONFIG_SSDFS_DEBUG
+				SSDFS_DBG("unable to find index: "
+					  "index %u, search_hash %llx, "
+					  "hash %llx\n",
+					  hash_index, search_hash,
+					  hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+				goto finish_search;
+			} else {
+				prev_found = lower_index;
+				upper_index = cur_index;
+			}
+		} else if (search_hash == hash) {
+			err = -EEXIST;
+			*found_index = cur_index;
+			*processed_bytes = search_bytes;
+			goto finish_search;
+		} else {
+			if (hash_index == range_end) {
+				err = -ENODATA;
+				*found_index = hash_index;
+#ifdef CONFIG_SSDFS_DEBUG
+				SSDFS_DBG("unable to find index: "
+					  "index %u, search_hash %llx, "
+					  "hash %llx\n",
+					  hash_index, search_hash,
+					  hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+				goto finish_search;
+			} else {
+				prev_found = lower_index;
+				lower_index = cur_index;
+			}
+		}
+	};
+
+finish_search:
+	kunmap_local(kaddr);
+
+	if (!err || err == -EEXIST) {
+		*found_index += processed_indexes;
+		if (*found_index >= area->index_capacity) {
+			SSDFS_ERR("found_index %u >= capacity %u\n",
+				  *found_index,
+				  area->index_capacity);
+			return -ERANGE;
+		}
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("prev_found %u, found_index %u\n",
+		  prev_found, *found_index);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	return err;
+}
+
+/*
+ * ssdfs_btree_common_node_find_index() - find index record
+ * @node: node object
+ * @area: description of index area
+ * search_hash: hash for search in the index area
+ * @found_index: identification number of found index [out]
+ *
+ * This method tries to find the index record for the requested hash.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-ERANGE     - internal error.
+ * %-ENODATA    - unable to find the node's index.
+ * %-EEXIST     - search hash has been found.
+ */
+static
+int ssdfs_btree_common_node_find_index(struct ssdfs_btree_node *node,
+				    struct ssdfs_btree_node_index_area *area,
+				    u64 search_hash,
+				    u16 *found_index)
+{
+	u32 start_offset, end_offset;
+	u32 processed_bytes = 0;
+	u16 prev_found = U16_MAX;
+	int err = -ENODATA;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node || !area || !found_index);
+	BUG_ON(!rwsem_is_locked(&node->full_lock));
+
+	SSDFS_DBG("node_id %u, node_type %#x, search_hash %llx\n",
+		  node->node_id, atomic_read(&node->type),
+		  search_hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	*found_index = U16_MAX;
+
+	if (atomic_read(&area->state) != SSDFS_BTREE_NODE_INDEX_AREA_EXIST) {
+		SSDFS_ERR("invalid area state %#x\n",
+			  atomic_read(&area->state));
+		return -ERANGE;
+	}
+
+	if (area->index_count == 0) {
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("node %u hasn't any index\n",
+			  node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+		return -ENODATA;
+	}
+
+	if (area->index_count > area->index_capacity) {
+		SSDFS_ERR("invalid area: "
+			  "index_count %u, index_capacity %u\n",
+			  area->index_count,
+			  area->index_capacity);
+		return -ERANGE;
+	}
+
+	if ((area->offset + area->area_size) > node->node_size) {
+		SSDFS_ERR("invalid area: "
+			  "offset %u, area_size %u, node_size %u\n",
+			  area->offset,
+			  area->area_size,
+			  node->node_size);
+		return -ERANGE;
+	}
+
+	if (area->index_size != sizeof(struct ssdfs_btree_index_key)) {
+		SSDFS_ERR("invalid index size %u\n",
+			  area->index_size);
+		return -ERANGE;
+	}
+
+	start_offset = area->offset;
+	end_offset = area->offset + area->area_size;
+
+	while (start_offset < end_offset) {
+		prev_found = *found_index;
+		err = ssdfs_find_index_in_memory_page(node, area,
+						      start_offset,
+						      search_hash,
+						      found_index,
+						      &processed_bytes);
+		if (err == -ENODATA) {
+			err = 0;
+
+			if (*found_index >= U16_MAX) {
+				/*
+				 * continue to search
+				 */
+			} else if ((*found_index + 1) >= area->index_count) {
+				/*
+				 * index has been found
+				 */
+				break;
+			}
+		} else if (err == -ENOENT) {
+			err = 0;
+
+			if (prev_found != U16_MAX) {
+				err = 0;
+				*found_index = prev_found;
+#ifdef CONFIG_SSDFS_DEBUG
+				SSDFS_DBG("node_id %u, search_hash %llx, "
+					  "found_index %u\n",
+					  node->node_id, search_hash,
+					  *found_index);
+#endif /* CONFIG_SSDFS_DEBUG */
+			}
+			break;
+		} else if (err == -EEXIST) {
+			/*
+			 * index has been found
+			 */
+			break;
+		} else if (unlikely(err)) {
+			SSDFS_ERR("fail to find index: err %d\n",
+				  err);
+			break;
+		} else
+			break;
+
+		start_offset += processed_bytes;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("prev_found %u, found_index %u, err %d\n",
+		  prev_found, *found_index, err);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	return err;
+}
+
+/*
+ * __ssdfs_btree_root_node_extract_index() - extract index from root node
+ * @node: node object
+ * @found_index: identification number of found index
+ * @search: btree search object [out]
+ *
+ * This method tries to extract index record from the index area.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-ERANGE     - internal error.
+ */
+int __ssdfs_btree_root_node_extract_index(struct ssdfs_btree_node *node,
+					  u16 found_index,
+					  struct ssdfs_btree_index_key *ptr)
+{
+	size_t index_size = sizeof(struct ssdfs_btree_index);
+	__le32 node_id;
+	int node_height;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node || !ptr);
+	BUG_ON(!rwsem_is_locked(&node->full_lock));
+	BUG_ON(!rwsem_is_locked(&node->tree->lock));
+
+	SSDFS_DBG("node_id %u, node_type %#x, found_index %u\n",
+		  node->node_id, atomic_read(&node->type),
+		  found_index);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (found_index >= SSDFS_BTREE_ROOT_NODE_INDEX_COUNT) {
+		SSDFS_ERR("invalid found_index %u\n",
+			  found_index);
+		return -ERANGE;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("index 0: node_id %u; index 1: node_id %u\n",
+		  cpu_to_le32(node->raw.root_node.header.node_ids[0]),
+		  cpu_to_le32(node->raw.root_node.header.node_ids[1]));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	down_read(&node->header_lock);
+	node_id = node->raw.root_node.header.node_ids[found_index];
+	ptr->node_id = cpu_to_le32(node_id);
+	ssdfs_memcpy(&ptr->index, 0, index_size,
+		     &node->raw.root_node.indexes[found_index], 0, index_size,
+		     index_size);
+	up_read(&node->header_lock);
+
+	node_height = atomic_read(&node->height);
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(node_height < 0);
+#endif /* CONFIG_SSDFS_DEBUG */
+	ptr->height = node_height - 1;
+
+	switch (node_height) {
+	case SSDFS_BTREE_LEAF_NODE_HEIGHT:
+	case SSDFS_BTREE_PARENT2LEAF_HEIGHT:
+		ptr->node_type = SSDFS_BTREE_LEAF_NODE;
+		break;
+
+	case SSDFS_BTREE_PARENT2HYBRID_HEIGHT:
+		ptr->node_type = SSDFS_BTREE_HYBRID_NODE;
+		break;
+
+	default:
+		ptr->node_type = SSDFS_BTREE_INDEX_NODE;
+		break;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("node_height %u, node_type %#x\n",
+		  node_height, ptr->node_type);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	ptr->flags = cpu_to_le16(SSDFS_BTREE_INDEX_HAS_VALID_EXTENT);
+
+	return 0;
+}
+
+/*
+ * ssdfs_btree_root_node_extract_index() - extract index from root node
+ * @node: node object
+ * @found_index: identification number of found index
+ * @search: btree search object [out]
+ *
+ * This method tries to extract index record from the index area.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-ERANGE     - internal error.
+ */
+static inline
+int ssdfs_btree_root_node_extract_index(struct ssdfs_btree_node *node,
+					u16 found_index,
+					struct ssdfs_btree_search *search)
+{
+	struct ssdfs_btree_index_key *ptr;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node || !search);
+	BUG_ON(!rwsem_is_locked(&node->full_lock));
+	BUG_ON(!rwsem_is_locked(&node->tree->lock));
+
+	SSDFS_DBG("node_id %u, node_type %#x, found_index %u\n",
+		  node->node_id, atomic_read(&node->type),
+		  found_index);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	ptr = &search->node.found_index;
+	return __ssdfs_btree_root_node_extract_index(node, found_index, ptr);
+}
+
+/*
+ * ssdfs_btree_node_get_index() - extract index from node
+ * @pvec: pagevec object
+ * @area_offset: area offset from the node's beginning
+ * @area_size: size of the area
+ * @node_size: node size in bytes
+ * @position: position of index record in the node
+ * @ptr: pointer on index buffer [out]
+ *
+ * This method tries to extract index record from the index area.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-ERANGE     - internal error.
+ */
+int ssdfs_btree_node_get_index(struct pagevec *pvec,
+				u32 area_offset, u32 area_size,
+				u32 node_size, u16 position,
+				struct ssdfs_btree_index_key *ptr)
+{
+	size_t index_size = sizeof(struct ssdfs_btree_index_key);
+	struct page *page;
+	u32 page_index;
+	u32 page_off;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!pvec || !ptr);
+
+	SSDFS_DBG("area_offset %u, area_size %u, "
+		  "node_size %u, position %u\n",
+		  area_offset, area_size,
+		  node_size, position);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	err = __ssdfs_define_memory_page(area_offset, area_size,
+					 node_size, index_size, position,
+					 &page_index, &page_off);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to define memory page: "
+			  "position %u, err %d\n",
+			  position, err);
+		return err;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(page_index >= U32_MAX);
+	BUG_ON(page_off >= U32_MAX);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (page_index >= pagevec_count(pvec)) {
+		SSDFS_ERR("page_index %u > pvec_size %u\n",
+			  page_index,
+			  pagevec_count(pvec));
+		return -ERANGE;
+	}
+
+	page = pvec->pages[page_index];
+	err = ssdfs_memcpy_from_page(ptr, 0, index_size,
+				     page, page_off, PAGE_SIZE,
+				     index_size);
+	if (unlikely(err)) {
+		SSDFS_ERR("invalid page_off %u, err %d\n",
+			  page_off, err);
+		return err;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("node_id %u, node_type %#x, hash %llx, "
+		  "seg_id %llu, logical_blk %u, len %u\n",
+		  le32_to_cpu(ptr->node_id),
+		  ptr->node_type,
+		  le64_to_cpu(ptr->index.hash),
+		  le64_to_cpu(ptr->index.extent.seg_id),
+		  le32_to_cpu(ptr->index.extent.logical_blk),
+		  le32_to_cpu(ptr->index.extent.len));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	return 0;
+}
+
+/*
+ * __ssdfs_btree_common_node_extract_index() - extract index from node
+ * @node: node object
+ * @area: description of index area
+ * @found_index: identification number of found index
+ * @search: btree search object [out]
+ *
+ * This method tries to extract index record from the index area.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-ERANGE     - internal error.
+ */
+int __ssdfs_btree_common_node_extract_index(struct ssdfs_btree_node *node,
+				    struct ssdfs_btree_node_index_area *area,
+				    u16 found_index,
+				    struct ssdfs_btree_index_key *ptr)
+{
+	struct page *page;
+	size_t index_key_len = sizeof(struct ssdfs_btree_index_key);
+	u32 page_index;
+	u32 page_off;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node || !area || !ptr);
+	BUG_ON(!rwsem_is_locked(&node->full_lock));
+	BUG_ON(!rwsem_is_locked(&node->tree->lock));
+
+	SSDFS_DBG("node_id %u, node_type %#x, found_index %u\n",
+		  node->node_id, atomic_read(&node->type),
+		  found_index);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (found_index == area->index_count) {
+		SSDFS_ERR("found_index %u == index_count %u\n",
+			  found_index, area->index_count);
+		return -ERANGE;
+	}
+
+	err = ssdfs_define_memory_page(node, area, found_index,
+					&page_index, &page_off);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to define memory page: "
+			  "node_id %u, found_index %u, err %d\n",
+			  node->node_id, found_index, err);
+		return err;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(page_index >= U32_MAX);
+	BUG_ON(page_off >= U32_MAX);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (page_index >= pagevec_count(&node->content.pvec)) {
+		SSDFS_ERR("page_index %u > pvec_size %u\n",
+			  page_index,
+			  pagevec_count(&node->content.pvec));
+		return -ERANGE;
+	}
+
+	page = node->content.pvec.pages[page_index];
+	err = ssdfs_memcpy_from_page(ptr, 0, index_key_len,
+				     page, page_off, PAGE_SIZE,
+				     index_key_len);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to copy: err %d\n", err);
+		return err;
+	}
+
+	if (ptr->node_type <= SSDFS_BTREE_NODE_UNKNOWN_TYPE ||
+	    ptr->node_type >= SSDFS_BTREE_NODE_TYPE_MAX) {
+		SSDFS_WARN("node_id %u, node_type %#x, found_index %u\n",
+			  node->node_id, atomic_read(&node->type),
+			  found_index);
+		SSDFS_ERR("page_index %u, page_off %u\n",
+			  page_index, page_off);
+		SSDFS_ERR("FOUND_INDEX: node_id %u, node_type %#x, "
+			  "height %u, flags %#x, hash %llx, "
+			  "seg_id %llu, logical_blk %u, len %u\n",
+			  le32_to_cpu(ptr->node_id),
+			  ptr->node_type, ptr->height, ptr->flags,
+			  le64_to_cpu(ptr->index.hash),
+			  le64_to_cpu(ptr->index.extent.seg_id),
+			  le32_to_cpu(ptr->index.extent.logical_blk),
+			  le32_to_cpu(ptr->index.extent.len));
+		return -ERANGE;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("FOUND_INDEX: node_id %u, node_type %#x, "
+		  "height %u, flags %#x, hash %llx, "
+		  "seg_id %llu, logical_blk %u, len %u\n",
+		  le32_to_cpu(ptr->node_id),
+		  ptr->node_type, ptr->height, ptr->flags,
+		  le64_to_cpu(ptr->index.hash),
+		  le64_to_cpu(ptr->index.extent.seg_id),
+		  le32_to_cpu(ptr->index.extent.logical_blk),
+		  le32_to_cpu(ptr->index.extent.len));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	return 0;
+}
+
+/*
+ * ssdfs_btree_common_node_extract_index() - extract index from node
+ * @node: node object
+ * @area: description of index area
+ * @found_index: identification number of found index
+ * @search: btree search object [out]
+ *
+ * This method tries to extract index record from the index area.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-ERANGE     - internal error.
+ */
+static inline
+int ssdfs_btree_common_node_extract_index(struct ssdfs_btree_node *node,
+				    struct ssdfs_btree_node_index_area *area,
+				    u16 found_index,
+				    struct ssdfs_btree_search *search)
+{
+	struct ssdfs_btree_index_key *ptr;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node || !area || !search);
+	BUG_ON(!rwsem_is_locked(&node->full_lock));
+	BUG_ON(!rwsem_is_locked(&node->tree->lock));
+
+	SSDFS_DBG("node_id %u, node_type %#x, found_index %u\n",
+		  node->node_id, atomic_read(&node->type),
+		  found_index);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	ptr = &search->node.found_index;
+	return __ssdfs_btree_common_node_extract_index(node, area,
+							found_index, ptr);
+}
+
+/*
+ * ssdfs_find_index_by_hash() - find index record in the node by hash
+ * @node: node object
+ * @area: description of index area
+ * @hash: hash value for the search
+ * @found_index: found position of index record in the node [out]
+ *
+ * This method tries to find node's index for
+ * the requested hash value.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENODATA    - unable to find the node's index.
+ * %-EEXIST     - search hash has been found.
+ */
+int ssdfs_find_index_by_hash(struct ssdfs_btree_node *node,
+			     struct ssdfs_btree_node_index_area *area,
+			     u64 hash,
+			     u16 *found_index)
+{
+	int node_type;
+	int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node || !area || !found_index);
+
+	SSDFS_DBG("node_id %u, hash %llx, "
+		  "area->start_hash %llx, area->end_hash %llx\n",
+		  node->node_id, hash,
+		  area->start_hash, area->end_hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	*found_index = U16_MAX;
+
+	node_type = atomic_read(&node->type);
+	if (node_type <= SSDFS_BTREE_NODE_UNKNOWN_TYPE ||
+	    node_type >= SSDFS_BTREE_NODE_TYPE_MAX) {
+		SSDFS_ERR("invalid node type %#x\n",
+			  node_type);
+		return -ERANGE;
+	}
+
+	if (atomic_read(&area->state) != SSDFS_BTREE_NODE_INDEX_AREA_EXIST) {
+		SSDFS_ERR("index area hasn't been created: "
+			  "node_id %u, node_type %#x\n",
+			  node->node_id,
+			  atomic_read(&node->type));
+		return -ERANGE;
+	}
+
+	if (area->index_count == 0) {
+		*found_index = 0;
+		SSDFS_DBG("index area is empty\n");
+		return -ENODATA;
+	}
+
+	if (area->index_count > area->index_capacity) {
+		SSDFS_ERR("index_count %u > index_capacity %u\n",
+			  area->index_count,
+			  area->index_capacity);
+		return -ERANGE;
+	}
+
+	if (area->start_hash == U64_MAX) {
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("start_hash is invalid: node_id %u\n",
+			  node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+		return -ENODATA;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	if (hash == U64_MAX) {
+		SSDFS_ERR("invalid requested hash\n");
+		return -ERANGE;
+	}
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (hash < area->start_hash) {
+		err = 0;
+		*found_index = 0;
+		goto finish_hash_search;
+	}
+
+	if (area->end_hash == U64_MAX)
+		*found_index = 0;
+	else if (hash >= area->end_hash) {
+		*found_index = area->index_count - 1;
+	} else {
+		if (node_type == SSDFS_BTREE_ROOT_NODE) {
+			err = ssdfs_btree_root_node_find_index(node, hash,
+								found_index);
+			if (err == -ENODATA) {
+				SSDFS_DBG("unable to find index\n");
+				goto finish_hash_search;
+			} else if (err == -EEXIST) {
+#ifdef CONFIG_SSDFS_DEBUG
+				SSDFS_DBG("index exists already: "
+					  "hash %llx, index %u\n",
+					  hash, *found_index);
+#endif /* CONFIG_SSDFS_DEBUG */
+				goto finish_hash_search;
+			} else if (unlikely(err)) {
+				SSDFS_ERR("fail to find index in root node: "
+					  "err %d\n",
+					  err);
+				goto finish_hash_search;
+			} else if (*found_index == U16_MAX) {
+				err = -ERANGE;
+				SSDFS_ERR("invalid index was found\n");
+				goto finish_hash_search;
+			}
+		} else {
+			err = ssdfs_btree_common_node_find_index(node, area,
+								 hash,
+								 found_index);
+			if (err == -ENODATA) {
+#ifdef CONFIG_SSDFS_DEBUG
+				SSDFS_DBG("unable to find index: "
+					  "node_id %u\n",
+					  node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+				goto finish_hash_search;
+			} else if (err == -EEXIST) {
+#ifdef CONFIG_SSDFS_DEBUG
+				SSDFS_DBG("index exists already: "
+					  "hash %llx, index %u\n",
+					  hash, *found_index);
+#endif /* CONFIG_SSDFS_DEBUG */
+				goto finish_hash_search;
+			} else if (unlikely(err)) {
+				SSDFS_ERR("fail to find index in the node: "
+					  "node_id %u, err %d\n",
+					  node->node_id, err);
+				goto finish_hash_search;
+			} else if (*found_index == U16_MAX) {
+				err = -ERANGE;
+				SSDFS_ERR("invalid index was found\n");
+				goto finish_hash_search;
+			}
+		}
+	}
+
+finish_hash_search:
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("hash %llx, found_index %u, err %d\n",
+		  hash, *found_index, err);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	return err;
+}
+
+/*
+ * ssdfs_btree_node_find_index_position() - find index's position
+ * @node: node object
+ * @hash: hash value
+ * @found_position: pointer on returned value [out]
+ *
+ * This method tries to find node's index for
+ * the requested hash value.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENODATA    - unable to find the node's index.
+ * %-ENOENT     - node hasn't the index area.
+ * %-EACCES     - node is under initialization yet.
+ */
+int ssdfs_btree_node_find_index_position(struct ssdfs_btree_node *node,
+					 u64 hash,
+					 u16 *found_position)
+{
+	struct ssdfs_btree_node_index_area area;
+	size_t desc_size = sizeof(struct ssdfs_btree_node_index_area);
+	int node_type;
+	int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node || !found_position);
+	BUG_ON(!node->tree);
+	BUG_ON(!rwsem_is_locked(&node->tree->lock));
+
+	SSDFS_DBG("node_id %u, node_type %#x, hash %llx\n",
+		  node->node_id,
+		  atomic_read(&node->type),
+		  hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	switch (atomic_read(&node->state)) {
+	case SSDFS_BTREE_NODE_CREATED:
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("node %u is under initialization\n",
+			  node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+		return -EACCES;
+
+	case SSDFS_BTREE_NODE_INITIALIZED:
+	case SSDFS_BTREE_NODE_DIRTY:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid node state %#x\n",
+			  atomic_read(&node->state));
+		return -ERANGE;
+	}
+
+	if (!is_ssdfs_btree_node_index_area_exist(node)) {
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("node %u hasn't index area\n",
+			  node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+		return -ENOENT;
+	}
+
+	*found_position = U16_MAX;
+
+	down_read(&node->full_lock);
+
+	node_type = atomic_read(&node->type);
+	if (node_type <= SSDFS_BTREE_NODE_UNKNOWN_TYPE ||
+	    node_type >= SSDFS_BTREE_NODE_TYPE_MAX) {
+		err = -ERANGE;
+		SSDFS_ERR("invalid node type %#x\n",
+			  node_type);
+		goto finish_index_search;
+	}
+
+	down_read(&node->header_lock);
+	ssdfs_memcpy(&area, 0, desc_size,
+		     &node->index_area, 0, desc_size,
+		     desc_size);
+	err = ssdfs_find_index_by_hash(node, &area, hash,
+					found_position);
+	up_read(&node->header_lock);
+
+	if (err == -EEXIST) {
+		/* hash == found hash */
+		err = 0;
+	} else if (err == -ENODATA) {
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("unable to find an index: "
+			  "node_id %u, hash %llx\n",
+			  node->node_id, hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+		goto finish_index_search;
+	} else if (unlikely(err)) {
+		SSDFS_ERR("fail to find an index: "
+			  "node_id %u, hash %llx, err %d\n",
+			  node->node_id, hash, err);
+		goto finish_index_search;
+	}
+
+finish_index_search:
+	up_read(&node->full_lock);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(*found_position == U16_MAX);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	return err;
+}
+
+/*
+ * ssdfs_btree_node_find_index() - find node's index
+ * @search: btree search object
+ *
+ * This method tries to find node's index for
+ * the requested hash value.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENODATA    - unable to find the node's index.
+ * %-ENOENT     - node hasn't the index area.
+ * %-EACCES     - node is under initialization yet.
+ */
+int ssdfs_btree_node_find_index(struct ssdfs_btree_search *search)
+{
+	struct ssdfs_btree_node *node;
+	struct ssdfs_btree_node_index_area area;
+	size_t desc_size = sizeof(struct ssdfs_btree_node_index_area);
+	int tree_height;
+	int node_type;
+	u16 found_index = U16_MAX;
+	int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!search);
+
+	SSDFS_DBG("type %#x, flags %#x, "
+		  "start_hash %llx, end_hash %llx, "
+		  "state %#x, node_id %u, height %u, "
+		  "parent %p, child %p\n",
+		  search->request.type, search->request.flags,
+		  search->request.start.hash, search->request.end.hash,
+		  search->node.state, search->node.id,
+		  search->node.height, search->node.parent,
+		  search->node.child);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (search->node.parent) {
+		node = search->node.parent;
+
+#ifdef CONFIG_SSDFS_DEBUG
+		BUG_ON(!node->tree);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+		tree_height = atomic_read(&node->tree->height);
+		if (tree_height <= (SSDFS_BTREE_LEAF_NODE_HEIGHT + 1)) {
+			/* tree has only root node */
+			return -ENODATA;
+		}
+	}
+
+	node = search->node.child;
+	if (!node) {
+		SSDFS_WARN("child node is NULL\n");
+		return -ERANGE;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node->tree);
+	BUG_ON(!rwsem_is_locked(&node->tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	switch (atomic_read(&node->state)) {
+	case SSDFS_BTREE_NODE_CREATED:
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("node %u is under initialization\n",
+			  node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+		return -EACCES;
+
+	case SSDFS_BTREE_NODE_INITIALIZED:
+	case SSDFS_BTREE_NODE_DIRTY:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid node state %#x\n",
+			  atomic_read(&node->state));
+		return -ERANGE;
+	}
+
+	if (!is_ssdfs_btree_node_index_area_exist(node)) {
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("node %u hasn't index area\n",
+			  node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+		node = search->node.parent;
+
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("try parent node %u\n",
+			  node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+	}
+
+	down_read(&node->full_lock);
+
+	node_type = atomic_read(&node->type);
+	if (node_type <= SSDFS_BTREE_NODE_UNKNOWN_TYPE ||
+	    node_type >= SSDFS_BTREE_NODE_TYPE_MAX) {
+		err = -ERANGE;
+		SSDFS_ERR("invalid node type %#x\n",
+			  node_type);
+		goto finish_index_search;
+	}
+
+	down_read(&node->header_lock);
+	ssdfs_memcpy(&area, 0, desc_size,
+		     &node->index_area, 0, desc_size,
+		     desc_size);
+	err = ssdfs_find_index_by_hash(node, &area,
+					search->request.start.hash,
+					&found_index);
+	up_read(&node->header_lock);
+
+	if (err == -EEXIST) {
+		/* hash == found hash */
+		err = 0;
+	} else if (err == -ENODATA) {
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("unable to find an index: "
+			  "node_id %u, hash %llx\n",
+			  node->node_id, search->request.start.hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+		goto finish_index_search;
+	} else if (unlikely(err)) {
+		SSDFS_WARN("fail to find an index: "
+			  "node_id %u, hash %llx, err %d\n",
+			  node->node_id, search->request.start.hash,
+			  err);
+		goto finish_index_search;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(found_index == U16_MAX);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (node_type == SSDFS_BTREE_ROOT_NODE) {
+		err = ssdfs_btree_root_node_extract_index(node,
+							  found_index,
+							  search);
+	} else {
+		err = ssdfs_btree_common_node_extract_index(node, &area,
+							    found_index,
+							    search);
+	}
+
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to extract index: "
+			  "node_id %u, node_type %#x, "
+			  "found_index %u, err %d\n",
+			  node->node_id, node_type,
+			  found_index, err);
+		goto finish_index_search;
+	}
+
+finish_index_search:
+	up_read(&node->full_lock);
+
+	if (unlikely(err))
+		ssdfs_debug_show_btree_node_indexes(node->tree, node);
+
+	return err;
+}
+
+/*
+ * can_add_new_index() - check that index area has free space
+ * @node: node object
+ */
+bool can_add_new_index(struct ssdfs_btree_node *node)
+{
+	bool can_add = false;
+	u16 count, capacity;
+	int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node);
+
+	SSDFS_DBG("node_id %u\n", node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	down_read(&node->header_lock);
+	count = node->index_area.index_count;
+	capacity = node->index_area.index_capacity;
+	if (count > capacity)
+		err = -ERANGE;
+	else
+		can_add = count < capacity;
+	up_read(&node->header_lock);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("count %u, capacity %u, can_add %#x, err %d\n",
+		  count, capacity, can_add, err);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (unlikely(err)) {
+		SSDFS_WARN("count %u > capacity %u\n",
+			   count, capacity);
+		return false;
+	}
+
+	return can_add;
+}
+
+/*
+ * ssdfs_btree_root_node_add_index() - add index record into the root node
+ * @node: node object
+ * @position: position in the node for storing the new index record
+ * @ptr: pointer on storing index record [in]
+ *
+ * This method tries to add index record into the root node.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENOSPC     - root node hasn't free space.
+ * %-EEXIST     - root node contains such record already.
+ */
+static
+int ssdfs_btree_root_node_add_index(struct ssdfs_btree_node *node,
+				    u16 position,
+				    struct ssdfs_btree_index_key *ptr)
+{
+	struct ssdfs_btree_index *found = NULL;
+	size_t index_size = sizeof(struct ssdfs_btree_index);
+	u64 hash1, hash2;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node || !ptr);
+	BUG_ON(!rwsem_is_locked(&node->full_lock));
+	BUG_ON(!rwsem_is_locked(&node->header_lock));
+
+	SSDFS_DBG("node_id %u, position %u\n",
+		  node->node_id, position);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (position >= SSDFS_BTREE_ROOT_NODE_INDEX_COUNT) {
+		SSDFS_ERR("invalid position %u\n",
+			  position);
+		return -ERANGE;
+	}
+
+	if (node->index_area.index_count > node->index_area.index_capacity) {
+		SSDFS_ERR("index_count %u > index_capacity %u\n",
+			  node->index_area.index_count,
+			  node->index_area.index_capacity);
+		return -ERANGE;
+	}
+
+	if (node->index_area.index_count == node->index_area.index_capacity) {
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("unable to add the index: "
+			  "index_count %u, index_capacity %u\n",
+			  node->index_area.index_count,
+			  node->index_area.index_capacity);
+#endif /* CONFIG_SSDFS_DEBUG */
+		return -ENOSPC;
+	}
+
+	found = &node->raw.root_node.indexes[position];
+
+	hash1 = le64_to_cpu(found->hash);
+	hash2 = le64_to_cpu(ptr->index.hash);
+
+	if (hash1 == hash2) {
+		ssdfs_memcpy(&node->raw.root_node.indexes[position],
+			     0, index_size,
+			     &ptr->index, 0, index_size,
+			     index_size);
+	} else if (hash1 < hash2) {
+		ssdfs_memcpy(&node->raw.root_node.indexes[position + 1],
+			     0, index_size,
+			     &ptr->index, 0, index_size,
+			     index_size);
+		position++;
+		node->index_area.index_count++;
+	} else {
+		void *indexes = node->raw.root_node.indexes;
+		u32 dst_off = (u32)(position + 1) * index_size;
+		u32 src_off = (u32)position * index_size;
+		u32 array_size = index_size * SSDFS_BTREE_ROOT_NODE_INDEX_COUNT;
+		u32 move_size = (u32)(node->index_area.index_count - position) *
+					index_size;
+
+		err = ssdfs_memmove(indexes, dst_off, array_size,
+				    indexes, src_off, array_size,
+				    move_size);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to move: err %d\n", err);
+			return err;
+		}
+
+		ssdfs_memcpy(&node->raw.root_node.indexes[position],
+			     0, index_size,
+			     &ptr->index, 0, index_size,
+			     index_size);
+		node->index_area.index_count++;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("node_id %u, node_type %#x, hash %llx, "
+		  "seg_id %llu, logical_blk %u, len %u\n",
+		  le32_to_cpu(ptr->node_id),
+		  ptr->node_type,
+		  le64_to_cpu(ptr->index.hash),
+		  le64_to_cpu(ptr->index.extent.seg_id),
+		  le32_to_cpu(ptr->index.extent.logical_blk),
+		  le32_to_cpu(ptr->index.extent.len));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	found = &node->raw.root_node.indexes[0];
+	node->index_area.start_hash = le64_to_cpu(found->hash);
+
+	found = &node->raw.root_node.indexes[node->index_area.index_count - 1];
+	node->index_area.end_hash = le64_to_cpu(found->hash);
+
+	ssdfs_memcpy(&node->raw.root_node.header.node_ids[position],
+		     0, sizeof(__le32),
+		     &ptr->node_id, 0, sizeof(__le32),
+		     sizeof(__le32));
+
+	return 0;
+}
+
+/*
+ * __ssdfs_btree_common_node_add_index() - add index record into the node
+ * @node: node object
+ * @position: position in the node for storing the new index record
+ * @ptr: pointer on storing index record [in]
+ *
+ * This method tries to add index record into the common node.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ */
+static
+int __ssdfs_btree_common_node_add_index(struct ssdfs_btree_node *node,
+					u16 position,
+					struct ssdfs_btree_index_key *ptr)
+{
+	struct page *page;
+	size_t index_key_len = sizeof(struct ssdfs_btree_index_key);
+	u32 page_index;
+	u32 page_off;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node || !ptr);
+	BUG_ON(!rwsem_is_locked(&node->full_lock));
+	BUG_ON(!rwsem_is_locked(&node->header_lock));
+
+	SSDFS_DBG("node_id %u, position %u\n",
+		  node->node_id, position);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (position != node->index_area.index_count) {
+		SSDFS_ERR("cannot add index: "
+			  "position %u, index_count %u\n",
+			  position,
+			  node->index_area.index_count);
+		return -ERANGE;
+	}
+
+	err = ssdfs_define_memory_page(node, &node->index_area,
+					position,
+					&page_index, &page_off);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to define memory page: "
+			  "node_id %u, position %u, err %d\n",
+			  node->node_id, position, err);
+		return err;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(page_index >= U32_MAX);
+	BUG_ON(page_off >= U32_MAX);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (page_index >= pagevec_count(&node->content.pvec)) {
+		SSDFS_ERR("page_index %u > pvec_size %u\n",
+			  page_index,
+			  pagevec_count(&node->content.pvec));
+		return -ERANGE;
+	}
+
+	page = node->content.pvec.pages[page_index];
+
+	ssdfs_lock_page(page);
+	err = ssdfs_memcpy_to_page(page, page_off, PAGE_SIZE,
+				   ptr, 0, index_key_len,
+				   index_key_len);
+	ssdfs_unlock_page(page);
+
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to copy: err %d\n", err);
+		return err;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("page_index %u, page_off %u\n",
+		  page_index, page_off);
+	SSDFS_DBG("node_id %u, node_type %#x, hash %llx, "
+		  "seg_id %llu, logical_blk %u, len %u\n",
+		  le32_to_cpu(ptr->node_id),
+		  ptr->node_type,
+		  le64_to_cpu(ptr->index.hash),
+		  le64_to_cpu(ptr->index.extent.seg_id),
+		  le32_to_cpu(ptr->index.extent.logical_blk),
+		  le32_to_cpu(ptr->index.extent.len));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	return 0;
+}
+
+/*
+ * ssdfs_btree_root_node_change_index() - change index record into root node
+ * @node: node object
+ * @found_index: position in the node of the changing index record
+ * @new_index: pointer on new index record state [in]
+ *
+ * This method tries to change the index record into the root node.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-ERANGE     - internal error.
+ */
+static inline
+int ssdfs_btree_root_node_change_index(struct ssdfs_btree_node *node,
+				       u16 found_index,
+				       struct ssdfs_btree_index_key *new_index)
+{
+	size_t index_size = sizeof(struct ssdfs_btree_index);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node || !new_index);
+	BUG_ON(!rwsem_is_locked(&node->full_lock));
+	BUG_ON(!rwsem_is_locked(&node->header_lock));
+
+	SSDFS_DBG("node_id %u, node_type %#x, found_index %u\n",
+		  node->node_id, atomic_read(&node->type),
+		  found_index);
+	SSDFS_DBG("node_id %u, node_type %#x, hash %llx, "
+		  "seg_id %llu, logical_blk %u, len %u\n",
+		  le32_to_cpu(new_index->node_id),
+		  new_index->node_type,
+		  le64_to_cpu(new_index->index.hash),
+		  le64_to_cpu(new_index->index.extent.seg_id),
+		  le32_to_cpu(new_index->index.extent.logical_blk),
+		  le32_to_cpu(new_index->index.extent.len));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (found_index >= SSDFS_BTREE_ROOT_NODE_INDEX_COUNT) {
+		SSDFS_ERR("invalid found_index %u\n",
+			  found_index);
+		return -ERANGE;
+	}
+
+	ssdfs_memcpy(&node->raw.root_node.indexes[found_index],
+		     0, index_size,
+		     &new_index->index, 0, index_size,
+		     index_size);
+
+	switch (found_index) {
+	case SSDFS_ROOT_NODE_LEFT_LEAF_NODE:
+		node->index_area.start_hash =
+			le64_to_cpu(new_index->index.hash);
+		break;
+
+	case SSDFS_ROOT_NODE_RIGHT_LEAF_NODE:
+		node->index_area.end_hash =
+			le64_to_cpu(new_index->index.hash);
+		break;
+
+	default:
+		BUG();
+	}
+
+	ssdfs_memcpy(&node->raw.root_node.header.node_ids[found_index],
+		     0, sizeof(__le32),
+		     &new_index->node_id, 0, sizeof(__le32),
+		     sizeof(__le32));
+
+	return 0;
+}
+
+/*
+ * ssdfs_btree_common_node_change_index() - change index record into common node
+ * @node: node object
+ * @found_index: position in the node of the changing index record
+ * @new_index: pointer on new index record state [in]
+ *
+ * This method tries to change the index record into the common node.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-ERANGE     - internal error.
+ */
+static
+int ssdfs_btree_common_node_change_index(struct ssdfs_btree_node *node,
+				    struct ssdfs_btree_node_index_area *area,
+				    u16 found_index,
+				    struct ssdfs_btree_index_key *new_index)
+{
+	struct page *page;
+	size_t index_key_len = sizeof(struct ssdfs_btree_index_key);
+	u32 page_index;
+	u32 page_off;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node || !area);
+	BUG_ON(!rwsem_is_locked(&node->full_lock));
+	BUG_ON(!rwsem_is_locked(&node->header_lock));
+
+	SSDFS_DBG("node_id %u, node_type %#x, found_index %u\n",
+		  node->node_id, atomic_read(&node->type),
+		  found_index);
+	SSDFS_DBG("node_id %u, node_type %#x, hash %llx, "
+		  "seg_id %llu, logical_blk %u, len %u\n",
+		  le32_to_cpu(new_index->node_id),
+		  new_index->node_type,
+		  le64_to_cpu(new_index->index.hash),
+		  le64_to_cpu(new_index->index.extent.seg_id),
+		  le32_to_cpu(new_index->index.extent.logical_blk),
+		  le32_to_cpu(new_index->index.extent.len));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (found_index == area->index_count) {
+		SSDFS_ERR("found_index %u == index_count %u\n",
+			  found_index, area->index_count);
+		return -ERANGE;
+	}
+
+	err = ssdfs_define_memory_page(node, area, found_index,
+					&page_index, &page_off);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to define memory page: "
+			  "node_id %u, found_index %u, err %d\n",
+			  node->node_id, found_index, err);
+		return err;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(page_index >= U32_MAX);
+	BUG_ON(page_off >= U32_MAX);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (page_index >= pagevec_count(&node->content.pvec)) {
+		SSDFS_ERR("page_index %u > pvec_size %u\n",
+			  page_index,
+			  pagevec_count(&node->content.pvec));
+		return -ERANGE;
+	}
+
+	page = node->content.pvec.pages[page_index];
+	err = ssdfs_memcpy_to_page(page, page_off, PAGE_SIZE,
+				   new_index, 0, index_key_len,
+				   index_key_len);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to copy: err %d\n", err);
+		return err;
+	}
+
+	if (found_index == 0)
+		area->start_hash = le64_to_cpu(new_index->index.hash);
+	else if (found_index == (area->index_count - 1))
+		area->end_hash = le64_to_cpu(new_index->index.hash);
+
+	return 0;
+}
+
+/*
+ * ssdfs_btree_common_node_insert_index() - insert index record into the node
+ * @node: node object
+ * @position: position in the node for storing the new index record
+ * @ptr: pointer on storing index record [in]
+ *
+ * This method tries to insert the index record into the common node.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ */
+static
+int ssdfs_btree_common_node_insert_index(struct ssdfs_btree_node *node,
+					 u16 position,
+					 struct ssdfs_btree_index_key *ptr)
+{
+	struct ssdfs_btree_index_key buffer[2];
+	struct page *page;
+	void *kaddr;
+	u32 page_index;
+	u32 page_off;
+	u16 cur_pos = position;
+	u8 index_size;
+	bool is_valid_index_in_buffer = false;
+	int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node || !ptr);
+	BUG_ON(!rwsem_is_locked(&node->full_lock));
+	BUG_ON(!rwsem_is_locked(&node->header_lock));
+
+	SSDFS_DBG("node_id %u, position %u\n",
+		  node->node_id, position);
+	SSDFS_DBG("node_id %u, node_type %#x, hash %llx, "
+		  "seg_id %llu, logical_blk %u, len %u\n",
+		  le32_to_cpu(ptr->node_id),
+		  ptr->node_type,
+		  le64_to_cpu(ptr->index.hash),
+		  le64_to_cpu(ptr->index.extent.seg_id),
+		  le32_to_cpu(ptr->index.extent.logical_blk),
+		  le32_to_cpu(ptr->index.extent.len));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (!(position < node->index_area.index_count)) {
+		SSDFS_ERR("cannot insert index: "
+			  "position %u, index_count %u\n",
+			  position,
+			  node->index_area.index_count);
+		return -ERANGE;
+	}
+
+	index_size = node->index_area.index_size;
+	if (index_size != sizeof(struct ssdfs_btree_index_key)) {
+		SSDFS_ERR("invalid index_size %u\n",
+			  index_size);
+		return -ERANGE;
+	}
+
+	ssdfs_memcpy(&buffer[0], 0, index_size,
+		     ptr, 0, index_size,
+		     index_size);
+
+	do {
+		u32 rest_capacity;
+		u32 moving_count;
+		u32 moving_bytes;
+
+		if (cur_pos > node->index_area.index_count) {
+			SSDFS_ERR("cur_pos %u, index_area.index_count %u\n",
+				  cur_pos, node->index_area.index_count);
+			return -ERANGE;
+		}
+
+		err = ssdfs_define_memory_page(node, &node->index_area,
+						cur_pos,
+						&page_index, &page_off);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to define memory page: "
+				  "node_id %u, position %u, err %d\n",
+				  node->node_id, cur_pos, err);
+			return err;
+		}
+
+#ifdef CONFIG_SSDFS_DEBUG
+		BUG_ON(page_index >= U32_MAX);
+		BUG_ON(page_off >= U32_MAX);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+		rest_capacity = PAGE_SIZE - page_off;
+		rest_capacity /= index_size;
+
+		if (rest_capacity == 0) {
+			SSDFS_WARN("rest_capacity == 0\n");
+			return -ERANGE;
+		}
+
+		moving_count = node->index_area.index_count - cur_pos;
+		moving_count = min_t(u32, moving_count, rest_capacity);
+
+		if (moving_count == rest_capacity) {
+			/*
+			 * Latest item will be moved into
+			 * temporary buffer (exclude from count)
+			 */
+			moving_bytes = (moving_count - 1) * index_size;
+		} else
+			moving_bytes = moving_count * index_size;
+
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("page_index %u, page_off %u, cur_pos %u, "
+			  "moving_count %u, rest_capacity %u\n",
+			  page_index, page_off, cur_pos,
+			  moving_count, rest_capacity);
+
+		if ((page_off + index_size) > PAGE_SIZE) {
+			SSDFS_WARN("invalid offset: "
+				   "page_off %u, index_size %u\n",
+				   page_off, index_size);
+			return -ERANGE;
+		}
+
+		if ((page_off + moving_bytes + index_size) > PAGE_SIZE) {
+			SSDFS_WARN("invalid offset: "
+				   "page_off %u, moving_bytes %u, "
+				   "index_size %u\n",
+				   page_off, moving_bytes, index_size);
+			return -ERANGE;
+		}
+#endif /* CONFIG_SSDFS_DEBUG */
+
+		if (page_index >= pagevec_count(&node->content.pvec)) {
+			SSDFS_ERR("page_index %u > pvec_size %u\n",
+				  page_index,
+				  pagevec_count(&node->content.pvec));
+			return -ERANGE;
+		}
+
+		page = node->content.pvec.pages[page_index];
+
+		ssdfs_lock_page(page);
+		kaddr = kmap_local_page(page);
+
+		if (moving_count == 0) {
+			err = ssdfs_memcpy(kaddr, page_off, PAGE_SIZE,
+					   &buffer[0], 0, index_size,
+					   index_size);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to copy: err %d\n", err);
+				goto finish_copy;
+			}
+
+			is_valid_index_in_buffer = false;
+			cur_pos++;
+		} else {
+			if (moving_count == rest_capacity) {
+				err = ssdfs_memcpy(&buffer[1],
+						   0, index_size,
+						   kaddr,
+						   PAGE_SIZE - index_size,
+						   PAGE_SIZE,
+						   index_size);
+				if (unlikely(err)) {
+					SSDFS_ERR("fail to copy: err %d\n",
+						  err);
+					goto finish_copy;
+				}
+
+				is_valid_index_in_buffer = true;
+			} else
+				is_valid_index_in_buffer = false;
+
+			err = ssdfs_memmove(kaddr,
+					    page_off + index_size,
+					    PAGE_SIZE,
+					    kaddr,
+					    page_off,
+					    PAGE_SIZE,
+					    moving_bytes);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to move: err %d\n",
+					  err);
+				goto finish_copy;
+			}
+
+			err = ssdfs_memcpy(kaddr, page_off, PAGE_SIZE,
+					   &buffer[0], 0, index_size,
+					   index_size);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to copy: err %d\n",
+					  err);
+				goto finish_copy;
+			}
+
+			if (is_valid_index_in_buffer) {
+				ssdfs_memcpy(&buffer[0], 0, index_size,
+					     &buffer[1], 0, index_size,
+					     index_size);
+			}
+
+			cur_pos += moving_count;
+		}
+
+finish_copy:
+		flush_dcache_page(page);
+		kunmap_local(kaddr);
+		ssdfs_unlock_page(page);
+
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("cur_pos %u, index_area.index_count %u, "
+			  "is_valid_index_in_buffer %#x\n",
+			  cur_pos, node->index_area.index_count,
+			  is_valid_index_in_buffer);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+		if (unlikely(err)) {
+			SSDFS_ERR("cur_pos %u, index_area.index_count %u, "
+				  "is_valid_index_in_buffer %#x\n",
+				  cur_pos, node->index_area.index_count,
+				  is_valid_index_in_buffer);
+			return err;
+		}
+	} while (is_valid_index_in_buffer);
+
+	return 0;
+}
+
+/*
+ * ssdfs_btree_common_node_add_index() - add index record into the node
+ * @node: node object
+ * @position: position in the node for storing the new index record
+ * @ptr: pointer on storing index record [in]
+ *
+ * This method tries to add the index record into the common node.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENOSPC     - node hasn't free space.
+ */
+static
+int ssdfs_btree_common_node_add_index(struct ssdfs_btree_node *node,
+				      u16 position,
+				      struct ssdfs_btree_index_key *ptr)
+{
+	struct ssdfs_btree_index_key tmp_key;
+	u64 hash1, hash2;
+	int err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node || !ptr);
+	BUG_ON(!rwsem_is_locked(&node->full_lock));
+	BUG_ON(!rwsem_is_locked(&node->header_lock));
+
+	SSDFS_DBG("node_id %u, position %u, index_count %u\n",
+		  node->node_id, position,
+		  node->index_area.index_count);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (node->index_area.index_count > node->index_area.index_capacity) {
+		SSDFS_ERR("index_count %u > index_capacity %u\n",
+			  node->index_area.index_count,
+			  node->index_area.index_capacity);
+		return -ERANGE;
+	}
+
+	if (node->index_area.index_count == node->index_area.index_capacity) {
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("unable to add the index: "
+			  "index_count %u, index_capacity %u\n",
+			  node->index_area.index_count,
+			  node->index_area.index_capacity);
+#endif /* CONFIG_SSDFS_DEBUG */
+		return -ENOSPC;
+	}
+
+	if (position > node->index_area.index_count) {
+		SSDFS_ERR("invalid index place: "
+			  "position %u, index_count %u\n",
+			  position,
+			  node->index_area.index_count);
+		return -ERANGE;
+	}
+
+	if (position == node->index_area.index_count) {
+		err = __ssdfs_btree_common_node_add_index(node, position, ptr);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to add index: "
+				  "node_id %u, position %u, err %d\n",
+				  node->node_id, position, err);
+			return err;
+		}
+
+		node->index_area.index_count++;
+	} else {
+		err = __ssdfs_btree_common_node_extract_index(node,
+							      &node->index_area,
+							      position,
+							      &tmp_key);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to extract the index: err %d\n", err);
+			return err;
+		}
+
+		hash1 = le64_to_cpu(tmp_key.index.hash);
+		hash2 = le64_to_cpu(ptr->index.hash);
+
+		if (hash1 == hash2) {
+			err = ssdfs_btree_common_node_change_index(node,
+							&node->index_area,
+							position,
+							ptr);
+			if (unlikely(err)) {
+				SSDFS_ERR("fail to change index: "
+					  "node_id %u, position %u, err %d\n",
+					  node->node_id, position, err);
+				return err;
+			}
+		} else {
+			if (hash2 > hash1)
+				position++;
+
+			if (position == node->index_area.index_count) {
+				err = __ssdfs_btree_common_node_add_index(node,
+								    position,
+								    ptr);
+				if (unlikely(err)) {
+					SSDFS_ERR("fail to add index: "
+						  "node_id %u, position %u, "
+						  "err %d\n",
+						  node->node_id, position, err);
+					return err;
+				}
+			} else {
+				err = ssdfs_btree_common_node_insert_index(node,
+								    position,
+								    ptr);
+				if (unlikely(err)) {
+					SSDFS_ERR("fail to insert index: "
+						  "node_id %u, position %u, "
+						  "err %d\n",
+						  node->node_id, position, err);
+					return err;
+				}
+			}
+
+			node->index_area.index_count++;
+		}
+	}
+
+	err = __ssdfs_btree_common_node_extract_index(node,
+						      &node->index_area,
+						      0,
+						      &tmp_key);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to extract the index: err %d\n", err);
+		return err;
+	}
+
+	node->index_area.start_hash = le64_to_cpu(tmp_key.index.hash);
+
+	err = __ssdfs_btree_common_node_extract_index(node,
+					&node->index_area,
+					node->index_area.index_count - 1,
+					&tmp_key);
+	if (unlikely(err)) {
+		SSDFS_ERR("fail to extract the index: err %d\n", err);
+		return err;
+	}
+
+	node->index_area.end_hash = le64_to_cpu(tmp_key.index.hash);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("start_hash %llx, end_hash %llx, "
+		  "index_count %u, index_capacity %u\n",
+		  node->index_area.start_hash,
+		  node->index_area.end_hash,
+		  node->index_area.index_count,
+		  node->index_area.index_capacity);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	return 0;
+}
+
+/*
+ * ssdfs_btree_node_add_index() - add index into node's index area
+ * @node: node object
+ * @index: new index
+ *
+ * This method tries to insert the index into node's index area.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENOSPC     - index area hasn't free space.
+ * %-ENOENT     - node hasn't the index area.
+ * %-EFAULT     - corrupted index or node's index area.
+ * %-EACCES     - node is under initialization yet.
+ */
+int ssdfs_btree_node_add_index(struct ssdfs_btree_node *node,
+				struct ssdfs_btree_index_key *index)
+{
+	struct ssdfs_fs_info *fsi;
+	u64 hash;
+	int node_type;
+	u16 found = U16_MAX;
+	u16 count;
+	int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node || !node->tree || !node->tree->fsi || !index);
+	BUG_ON(!rwsem_is_locked(&node->tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	hash = le64_to_cpu(index->index.hash);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("node_id %u, hash %llx\n",
+		  node->node_id, hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	fsi = node->tree->fsi;
+
+	switch (atomic_read(&node->state)) {
+	case SSDFS_BTREE_NODE_CREATED:
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("node %u is under initialization\n",
+			  node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+		return -EACCES;
+
+	case SSDFS_BTREE_NODE_INITIALIZED:
+	case SSDFS_BTREE_NODE_DIRTY:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid node state %#x\n",
+			  atomic_read(&node->state));
+		return -ERANGE;
+	}
+
+	if (!is_ssdfs_btree_node_index_area_exist(node)) {
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("node %u hasn't index area\n",
+			  node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+		return -ENOENT;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	if (hash == U64_MAX) {
+		SSDFS_ERR("invalid hash %llx\n", hash);
+		return -ERANGE;
+	}
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	node_type = atomic_read(&node->type);
+	if (node_type <= SSDFS_BTREE_NODE_UNKNOWN_TYPE ||
+	    node_type >= SSDFS_BTREE_NODE_TYPE_MAX) {
+		SSDFS_ERR("invalid node type %#x\n",
+			  node_type);
+		return -ERANGE;
+	}
+
+	if (!can_add_new_index(node)) {
+		u32 new_size;
+
+		down_read(&node->header_lock);
+		new_size = node->index_area.area_size * 2;
+		up_read(&node->header_lock);
+
+		err = ssdfs_btree_node_resize_index_area(node, new_size);
+		if (err == -EACCES) {
+#ifdef CONFIG_SSDFS_DEBUG
+			SSDFS_DBG("node %u is under initialization\n",
+				  node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+			return err;
+		} else if (err == -ENOSPC) {
+#ifdef CONFIG_SSDFS_DEBUG
+			SSDFS_DBG("index area cannot be resized: "
+				  "node_id %u\n", node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+			return err;
+		} else if (unlikely(err)) {
+			SSDFS_ERR("fail to resize index area: "
+				  "node_id %u, new_size %u, err %d\n",
+				  node->node_id, new_size, err);
+			return err;
+		}
+	}
+
+	if (node_type == SSDFS_BTREE_ROOT_NODE) {
+		down_read(&node->full_lock);
+		down_write(&node->header_lock);
+
+		err = ssdfs_find_index_by_hash(node, &node->index_area,
+						hash, &found);
+
+#ifdef CONFIG_SSDFS_DEBUG
+		BUG_ON(found >= U16_MAX);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+		if (err == -ENODATA) {
+			/* node hasn't any index */
+			err = 0;
+		} else if (unlikely(err)) {
+			SSDFS_ERR("fail to find an index: "
+				  "node_id %u, hash %llx, err %d\n",
+				  node->node_id, hash, err);
+			goto finish_change_root_node;
+		}
+
+		err = ssdfs_btree_root_node_add_index(node, found,
+							index);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to change index: "
+				  "node_id %u, node_type %#x, "
+				  "found_index %u, err %d\n",
+				  node->node_id, node_type,
+				  found, err);
+		}
+
+finish_change_root_node:
+		up_write(&node->header_lock);
+		up_read(&node->full_lock);
+
+		if (unlikely(err)) {
+			ssdfs_debug_show_btree_node_indexes(node->tree, node);
+			return err;
+		}
+	} else {
+		down_write(&node->full_lock);
+		down_write(&node->header_lock);
+
+		err = ssdfs_find_index_by_hash(node, &node->index_area,
+						hash, &found);
+
+#ifdef CONFIG_SSDFS_DEBUG
+		BUG_ON(found >= U16_MAX);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+		if (err == -EEXIST) {
+			/* index exist already */
+			err = 0;
+		} else if (err == -ENODATA) {
+			/* node hasn't any index */
+			err = 0;
+		} else if (unlikely(err)) {
+			SSDFS_ERR("fail to find an index: "
+				  "node_id %u, hash %llx, err %d\n",
+				  node->node_id, hash, err);
+			up_write(&node->header_lock);
+			up_write(&node->full_lock);
+			return err;
+		}
+
+		count = (node->index_area.index_count + 1) - found;
+		err = ssdfs_lock_index_range(node, found, count);
+		BUG_ON(err == -ENODATA);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to lock index range: "
+				  "start %u, count %u, err %d\n",
+				  found, count, err);
+			up_write(&node->header_lock);
+			up_write(&node->full_lock);
+			return err;
+		}
+
+		downgrade_write(&node->full_lock);
+
+		err = ssdfs_btree_common_node_add_index(node, found,
+							index);
+		ssdfs_unlock_index_range(node, found, count);
+
+		if (!err)
+			err = ssdfs_set_dirty_index_range(node, found, count);
+
+		up_write(&node->header_lock);
+		up_read(&node->full_lock);
+
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to add index: "
+				  "node_id %u, node_type %#x, "
+				  "found_index %u, err %d\n",
+				  node->node_id, node_type,
+				  found, err);
+			ssdfs_debug_show_btree_node_indexes(node->tree, node);
+		}
+	}
+
+	ssdfs_set_node_update_cno(node);
+	set_ssdfs_btree_node_dirty(node);
+
+	return 0;
+}
+
+static inline
+bool is_ssdfs_btree_index_key_identical(struct ssdfs_btree_index_key *index1,
+					struct ssdfs_btree_index_key *index2)
+{
+	u32 node_id1, node_id2;
+	u8 node_type1, node_type2;
+	u64 hash1, hash2;
+	u64 seg_id1, seg_id2;
+	u32 logical_blk1, logical_blk2;
+	u32 len1, len2;
+
+	node_id1 = le32_to_cpu(index1->node_id);
+	node_type1 = index1->node_type;
+	hash1 = le64_to_cpu(index1->index.hash);
+	seg_id1 = le64_to_cpu(index1->index.extent.seg_id);
+	logical_blk1 = le32_to_cpu(index1->index.extent.logical_blk);
+	len1 = le32_to_cpu(index1->index.extent.len);
+
+	node_id2 = le32_to_cpu(index2->node_id);
+	node_type2 = index2->node_type;
+	hash2 = le64_to_cpu(index2->index.hash);
+	seg_id2 = le64_to_cpu(index2->index.extent.seg_id);
+	logical_blk2 = le32_to_cpu(index2->index.extent.logical_blk);
+	len2 = le32_to_cpu(index2->index.extent.len);
+
+	return node_id1 == node_id2 && node_type1 == node_type2 &&
+		hash1 == hash2 && seg_id1 == seg_id2 &&
+		logical_blk1 == logical_blk2 && len1 == len2;
+}
+
+/*
+ * __ssdfs_btree_node_change_index() - change existing index
+ * @node: node object
+ * @old_index: old index
+ * @new_index: new index
+ *
+ * This method tries to change @old_index on @new_index into
+ * node's index area.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENODATA    - node's index area doesn't contain @old_index.
+ * %-ENOENT     - node hasn't the index area.
+ * %-EFAULT     - corrupted index or node's index area.
+ * %-EACCES     - node is under initialization yet.
+ */
+static
+int __ssdfs_btree_node_change_index(struct ssdfs_btree_node *node,
+				    struct ssdfs_btree_index_key *old_index,
+				    struct ssdfs_btree_index_key *new_index)
+{
+	struct ssdfs_fs_info *fsi;
+	struct ssdfs_btree_node_index_area area;
+	size_t desc_size = sizeof(struct ssdfs_btree_node_index_area);
+	int node_type;
+	u64 old_hash, new_hash;
+	u16 found = U16_MAX;
+	int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node || !node->tree || !node->tree->fsi);
+	BUG_ON(!old_index || !new_index);
+	BUG_ON(!rwsem_is_locked(&node->tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	fsi = node->tree->fsi;
+	old_hash = le64_to_cpu(old_index->index.hash);
+	new_hash = le64_to_cpu(new_index->index.hash);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("node_id %u, old_hash %llx, new_hash %llx\n",
+		  node->node_id, old_hash, new_hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	switch (atomic_read(&node->state)) {
+	case SSDFS_BTREE_NODE_CREATED:
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("node %u is under initialization\n",
+			  node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+		return -EACCES;
+
+	case SSDFS_BTREE_NODE_INITIALIZED:
+	case SSDFS_BTREE_NODE_DIRTY:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid node state %#x\n",
+			  atomic_read(&node->state));
+		return -ERANGE;
+	}
+
+	if (!is_ssdfs_btree_node_index_area_exist(node)) {
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("node %u hasn't index area\n",
+			  node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+		return -ENOENT;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	if (old_hash == U64_MAX || new_hash == U64_MAX) {
+		SSDFS_ERR("invalid old_hash %llx or new_hash %llx\n",
+			  old_hash, new_hash);
+		return -ERANGE;
+	}
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	node_type = atomic_read(&node->type);
+	if (node_type <= SSDFS_BTREE_NODE_UNKNOWN_TYPE ||
+	    node_type >= SSDFS_BTREE_NODE_TYPE_MAX) {
+		SSDFS_ERR("invalid node type %#x\n",
+			  node_type);
+		return -ERANGE;
+	}
+
+	if (node_type == SSDFS_BTREE_ROOT_NODE) {
+		down_read(&node->full_lock);
+
+		err = ssdfs_find_index_by_hash(node, &node->index_area,
+						old_hash, &found);
+		if (err == -EEXIST) {
+			err = 0;
+			/*
+			 * Index has been found.
+			 * Continue logic.
+			 */
+		} else if (err == -ENODATA) {
+#ifdef CONFIG_SSDFS_DEBUG
+			SSDFS_DBG("unable to find an index: "
+				  "node_id %u, hash %llx\n",
+				  node->node_id, old_hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+			goto finish_change_root_node;
+		} else if (unlikely(err)) {
+			SSDFS_ERR("fail to find an index: "
+				  "node_id %u, hash %llx, err %d\n",
+				  node->node_id, old_hash, err);
+			goto finish_change_root_node;
+		} else {
+			err = -ERANGE;
+			SSDFS_ERR("no index for the hash %llx\n",
+				  old_hash);
+			goto finish_change_root_node;
+		}
+
+#ifdef CONFIG_SSDFS_DEBUG
+		BUG_ON(found == U16_MAX);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+		down_write(&node->header_lock);
+
+		err = ssdfs_btree_root_node_change_index(node, found,
+							 new_index);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to change index: "
+				  "node_id %u, node_type %#x, "
+				  "found %u, err %d\n",
+				  node->node_id, node_type,
+				  found, err);
+		}
+
+		up_write(&node->header_lock);
+finish_change_root_node:
+		up_read(&node->full_lock);
+
+		if (unlikely(err))
+			return err;
+	} else {
+		down_read(&node->full_lock);
+
+		down_read(&node->header_lock);
+		ssdfs_memcpy(&area, 0, desc_size,
+			     &node->index_area, 0, desc_size,
+			     desc_size);
+		up_read(&node->header_lock);
+
+		err = ssdfs_find_index_by_hash(node, &area,
+						old_hash, &found);
+		if (err == -EEXIST) {
+			err = 0;
+			/*
+			 * Index has been found.
+			 * Continue logic.
+			 */
+		} else if (unlikely(err)) {
+			SSDFS_ERR("fail to find an index: "
+				  "node_id %u, hash %llx, err %d\n",
+				  node->node_id, old_hash, err);
+		} else {
+			err = -ERANGE;
+			SSDFS_ERR("no index for the hash %llx\n",
+				  old_hash);
+		}
+
+		up_read(&node->full_lock);
+
+		if (unlikely(err))
+			return err;
+
+#ifdef CONFIG_SSDFS_DEBUG
+		BUG_ON(found == U16_MAX);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+		down_write(&node->full_lock);
+		down_write(&node->header_lock);
+
+		err = ssdfs_lock_index_range(node, found, 1);
+		BUG_ON(err == -ENODATA);
+
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to lock index %u, err %d\n",
+				  found, err);
+			up_write(&node->header_lock);
+			up_write(&node->full_lock);
+			return err;
+		}
+
+		downgrade_write(&node->full_lock);
+
+		err = ssdfs_btree_common_node_change_index(node,
+							   &node->index_area,
+							   found, new_index);
+		ssdfs_unlock_index_range(node, found, 1);
+
+		if (!err)
+			err = ssdfs_set_dirty_index_range(node, found, 1);
+
+		up_write(&node->header_lock);
+		up_read(&node->full_lock);
+
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to change index: "
+				  "node_id %u, node_type %#x, "
+				  "found %u, err %d\n",
+				  node->node_id, node_type,
+				  found, err);
+			return err;
+		}
+	}
+
+	ssdfs_set_node_update_cno(node);
+	set_ssdfs_btree_node_dirty(node);
+
+	return 0;
+}
+
+/*
+ * ssdfs_btree_node_change_index() - change existing index
+ * @node: node object
+ * @old_index: old index
+ * @new_index: new index
+ *
+ * This method tries to change @old_index on @new_index into
+ * node's index area.
+ *
+ * RETURN:
+ * [success]
+ * [failure] - error code:
+ *
+ * %-EINVAL     - invalid input.
+ * %-ERANGE     - internal error.
+ * %-ENODATA    - node's index area doesn't contain @old_index.
+ * %-ENOENT     - node hasn't the index area.
+ * %-EFAULT     - corrupted index or node's index area.
+ * %-EACCES     - node is under initialization yet.
+ */
+int ssdfs_btree_node_change_index(struct ssdfs_btree_node *node,
+				  struct ssdfs_btree_index_key *old_index,
+				  struct ssdfs_btree_index_key *new_index)
+{
+	u64 old_hash, new_hash;
+	int err = 0;
+
+#ifdef CONFIG_SSDFS_DEBUG
+	BUG_ON(!node || !node->tree || !node->tree->fsi);
+	BUG_ON(!old_index || !new_index);
+	BUG_ON(!rwsem_is_locked(&node->tree->lock));
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	old_hash = le64_to_cpu(old_index->index.hash);
+	new_hash = le64_to_cpu(new_index->index.hash);
+
+#ifdef CONFIG_SSDFS_DEBUG
+	SSDFS_DBG("node_id %u, old_hash %llx, new_hash %llx\n",
+		  node->node_id, old_hash, new_hash);
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	switch (atomic_read(&node->state)) {
+	case SSDFS_BTREE_NODE_CREATED:
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("node %u is under initialization\n",
+			  node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+		return -EACCES;
+
+	case SSDFS_BTREE_NODE_INITIALIZED:
+	case SSDFS_BTREE_NODE_DIRTY:
+		/* expected state */
+		break;
+
+	default:
+		SSDFS_ERR("invalid node state %#x\n",
+			  atomic_read(&node->state));
+		return -ERANGE;
+	}
+
+	if (!is_ssdfs_btree_node_index_area_exist(node)) {
+#ifdef CONFIG_SSDFS_DEBUG
+		SSDFS_DBG("node %u hasn't index area\n",
+			  node->node_id);
+#endif /* CONFIG_SSDFS_DEBUG */
+		return -ENOENT;
+	}
+
+#ifdef CONFIG_SSDFS_DEBUG
+	if (old_hash == U64_MAX || new_hash == U64_MAX) {
+		SSDFS_ERR("invalid old_hash %llx or new_hash %llx\n",
+			  old_hash, new_hash);
+		return -ERANGE;
+	}
+#endif /* CONFIG_SSDFS_DEBUG */
+
+	if (is_ssdfs_btree_index_key_identical(old_index, new_index)) {
+		SSDFS_DBG("old and new index are identical\n");
+		return 0;
+	}
+
+	if (old_hash == new_hash) {
+		err = __ssdfs_btree_node_change_index(node, old_index,
+							new_index);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to change index: "
+				  "old_hash %llx, err %d\n",
+				  old_hash, err);
+			goto fail_change_index;
+		}
+	} else {
+		err = ssdfs_btree_node_delete_index(node, old_hash);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to delete index: "
+				  "old_hash %llx, err %d\n",
+				  old_hash, err);
+			goto fail_change_index;
+		}
+
+		err = ssdfs_btree_node_add_index(node, new_index);
+		if (unlikely(err)) {
+			SSDFS_ERR("fail to add index: "
+				  "new_hash %llx, err %d\n",
+				  new_hash, err);
+			goto fail_change_index;
+		}
+	}
+
+	return 0;
+
+fail_change_index:
+	SSDFS_ERR("node_id %u, node_type %#x\n",
+		  node->node_id,
+		  atomic_read(&node->type));
+	SSDFS_ERR("node_id %u, node_type %#x, old_hash %llx, "
+		  "seg_id %llu, logical_blk %u, len %u\n",
+		  le32_to_cpu(old_index->node_id),
+		  old_index->node_type,
+		  le64_to_cpu(old_index->index.hash),
+		  le64_to_cpu(old_index->index.extent.seg_id),
+		  le32_to_cpu(old_index->index.extent.logical_blk),
+		  le32_to_cpu(old_index->index.extent.len));
+	SSDFS_ERR("node_id %u, node_type %#x, new_hash %llx, "
+		  "seg_id %llu, logical_blk %u, len %u\n",
+		  le32_to_cpu(new_index->node_id),
+		  new_index->node_type,
+		  le64_to_cpu(new_index->index.hash),
+		  le64_to_cpu(new_index->index.extent.seg_id),
+		  le32_to_cpu(new_index->index.extent.logical_blk),
+		  le32_to_cpu(new_index->index.extent.len));
+
+	return err;
+}
