diff --git a/swh/storage/in_memory.py b/swh/storage/in_memory.py
--- a/swh/storage/in_memory.py
+++ b/swh/storage/in_memory.py
@@ -600,12 +600,13 @@
         snapshot = self._snapshots.get(snapshot_id)
         if snapshot is None:
             return None
-        sorted_branch_names = sorted(snapshot.branches)
+        sorted_branches = sorted(snapshot.branches.items())
+        sorted_branch_names = [k for (k, v) in sorted_branches]
         from_index = bisect.bisect_left(sorted_branch_names, branches_from)
         if target_types:
             next_branch = None
             branches = {}
-            for (branch_name, branch) in snapshot.branches.items():
+            for (branch_name, branch) in sorted_branches:
                 if branch_name in sorted_branch_names[from_index:]:
                     if branch and branch.target_type.value in target_types:
                         if len(branches) < branches_count:
diff --git a/swh/storage/tests/test_storage.py b/swh/storage/tests/test_storage.py
--- a/swh/storage/tests/test_storage.py
+++ b/swh/storage/tests/test_storage.py
@@ -2749,6 +2749,36 @@
 
         assert snapshot == expected_snapshot
 
+    def test_snapshot_add_get_branch_by_type(self, swh_storage):
+        snapshot = copy.deepcopy(data.complete_snapshot)
+
+        alias1 = b"alias1"
+        alias2 = b"alias2"
+        target1 = random.choice(list(snapshot["branches"].keys()))
+        target2 = random.choice(list(snapshot["branches"].keys()))
+
+        snapshot["branches"][alias2] = {
+            "target": target2,
+            "target_type": "alias",
+        }
+
+        snapshot["branches"][alias1] = {
+            "target": target1,
+            "target_type": "alias",
+        }
+
+        swh_storage.snapshot_add([snapshot])
+
+        branches = swh_storage.snapshot_get_branches(
+            snapshot["id"],
+            target_types=["alias"],
+            branches_from=alias1,
+            branches_count=1,
+        )["branches"]
+
+        assert len(branches) == 1
+        assert alias1 in branches
+
     def test_snapshot_add_get(self, swh_storage):
         origin_url = swh_storage.origin_add_one(data.origin)
         visit = OriginVisit(