diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c
index 55d78e2..f76f790 100644
--- a/lib/ext2fs/blkmap64_rb.c
+++ b/lib/ext2fs/blkmap64_rb.c
@@ -304,8 +304,8 @@ static errcode_t rb_resize_bmap(ext2fs_generic_bitmap bmap,
 inline static int
 rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
 {
-	struct bmap_rb_extent *rcursor;
-	struct rb_node *parent = NULL;
+	struct bmap_rb_extent *rcursor, *next_ext;
+	struct rb_node *parent = NULL, *next;
 	struct rb_node **n = &bp->root.rb_node;
 	struct bmap_rb_extent *ext;
 
@@ -320,6 +320,23 @@ rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
 		return 1;
 	}
 
+	next = ext2fs_rb_next(&rcursor->node);
+	if (next && (bit >= rcursor->start + rcursor->count)) {
+		next_ext = ext2fs_rb_entry(next, struct bmap_rb_extent, node);
+		if (bit < next_ext->start) {
+#ifdef BMAP_STATS_OPS
+			bp->test_hit++;
+#endif
+			return 0;
+		} else if (bit < next_ext->start + next_ext->count) {
+#ifdef BMAP_STATS_OPS
+			bp->test_hit++;
+#endif
+			bp->rcursor = next_ext;
+			return 1;
+		}
+	}
+
 	rcursor = bp->wcursor;
 	if (!rcursor)
 		goto search_tree;