diff --git a/clang-tools-extra/clangd/CMakeLists.txt b/clang-tools-extra/clangd/CMakeLists.txt
--- a/clang-tools-extra/clangd/CMakeLists.txt
+++ b/clang-tools-extra/clangd/CMakeLists.txt
@@ -77,6 +77,7 @@
   index/MemIndex.cpp
   index/Merge.cpp
   index/Ref.cpp
+  index/Relation.cpp
   index/Serialization.cpp
   index/Symbol.cpp
   index/SymbolCollector.cpp
diff --git a/clang-tools-extra/clangd/index/Index.h b/clang-tools-extra/clangd/index/Index.h
--- a/clang-tools-extra/clangd/index/Index.h
+++ b/clang-tools-extra/clangd/index/Index.h
@@ -10,6 +10,7 @@
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H
 
 #include "Ref.h"
+#include "Relation.h"
 #include "Symbol.h"
 #include "SymbolID.h"
 #include "llvm/ADT/DenseSet.h"
diff --git a/clang-tools-extra/clangd/index/Relation.h b/clang-tools-extra/clangd/index/Relation.h
new file mode 100644
--- /dev/null
+++ b/clang-tools-extra/clangd/index/Relation.h
@@ -0,0 +1,98 @@
+//===--- Relation.h ----------------------------------------------*- C++-*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_RELATION_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_RELATION_H
+
+#include "SymbolID.h"
+#include "SymbolLocation.h"
+#include "clang/Index/IndexSymbol.h"
+#include "llvm/ADT/iterator_range.h"
+#include <cstdint>
+#include <utility>
+
+namespace clang {
+namespace clangd {
+
+/// Represents a relation between two symbols.
+/// For an example "A is a base class of B" may be represented
+/// as { Subject = A, Predicate = RelationBaseOf, Object = B }.
+struct Relation {
+  SymbolID Subject;
+  index::SymbolRole Predicate;
+  SymbolID Object;
+
+  bool operator==(const Relation &Other) const {
+    return Subject == Other.Subject && Predicate == Other.Predicate &&
+           Object == Other.Object;
+  }
+  // SPO order
+  bool operator<(const Relation &Other) const {
+    if (Subject < Other.Subject) {
+      return true;
+    }
+    if (Subject == Other.Subject) {
+      if (Predicate < Other.Predicate) {
+        return true;
+      }
+
+      if (Predicate == Other.Predicate) {
+        return Object < Other.Object;
+      }
+    }
+    return false;
+  }
+};
+
+class RelationSlab {
+public:
+  using value_type = Relation;
+  using const_iterator = std::vector<value_type>::const_iterator;
+  using iterator = const_iterator;
+
+  // We don't need a separate builder type for this, but reserve
+  // that possibility for the future. Having a build() method is
+  // also useful so when know when to sort the relations.
+  using Builder = RelationSlab;
+
+  RelationSlab() = default;
+  RelationSlab(RelationSlab &&Slab) = default;
+  RelationSlab &operator=(RelationSlab &&RHS) = default;
+
+  const_iterator begin() const { return Relations.begin(); }
+  const_iterator end() const { return Relations.end(); }
+  size_t size() const { return Relations.size(); }
+  bool empty() const { return Relations.empty(); }
+
+  void push_back(const Relation &R) { Relations.push_back(R); }
+
+  size_t bytes() const {
+    return sizeof(*this) + sizeof(value_type) * Relations.capacity();
+  }
+
+  /// Sort relations in SPO order.
+  void sort();
+
+  /// Lookup all relations matching the given subject and predicate.
+  /// Assumes the slab is sorted in SPO order.
+  llvm::iterator_range<iterator> lookup(const SymbolID &Subject,
+                                        index::SymbolRole Predicate) const;
+
+  RelationSlab build() &&;
+
+private:
+  RelationSlab(std::vector<Relation> Relations)
+      : Relations(std::move(Relations)) {}
+
+  std::vector<Relation> Relations;
+};
+
+} // namespace clangd
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_RELATION_H
diff --git a/clang-tools-extra/clangd/index/Relation.cpp b/clang-tools-extra/clangd/index/Relation.cpp
new file mode 100644
--- /dev/null
+++ b/clang-tools-extra/clangd/index/Relation.cpp
@@ -0,0 +1,37 @@
+//===--- Relation.cpp --------------------------------------------*- C++-*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "Relation.h"
+
+#include <algorithm>
+
+namespace clang {
+namespace clangd {
+
+void RelationSlab::sort() { std::sort(Relations.begin(), Relations.end()); }
+
+llvm::iterator_range<RelationSlab::iterator>
+RelationSlab::lookup(const SymbolID &Subject,
+                     index::SymbolRole Predicate) const {
+  auto IterPair = std::equal_range(Relations.begin(), Relations.end(),
+                                   Relation{Subject, Predicate, SymbolID{}},
+                                   [](const Relation &A, const Relation &B) {
+                                     return (A.Subject < B.Subject) ||
+                                            (A.Subject == B.Subject &&
+                                             A.Predicate < B.Predicate);
+                                   });
+  return {IterPair.first, IterPair.second};
+}
+
+RelationSlab RelationSlab::build() && {
+  sort();
+  return std::move(*this);
+}
+
+} // namespace clangd
+} // namespace clang
diff --git a/clang-tools-extra/clangd/unittests/IndexTests.cpp b/clang-tools-extra/clangd/unittests/IndexTests.cpp
--- a/clang-tools-extra/clangd/unittests/IndexTests.cpp
+++ b/clang-tools-extra/clangd/unittests/IndexTests.cpp
@@ -76,6 +76,29 @@
     EXPECT_THAT(*S.find(SymbolID(Sym)), Named(Sym));
 }
 
+TEST(RelationSlab, Lookup) {
+  SymbolID A{"A"};
+  SymbolID B{"B"};
+  SymbolID C{"C"};
+  SymbolID D{"D"};
+
+  RelationSlab::Builder Builder;
+  Builder.push_back(Relation{A, index::SymbolRole::RelationBaseOf, B});
+  Builder.push_back(Relation{A, index::SymbolRole::RelationBaseOf, C});
+  Builder.push_back(Relation{B, index::SymbolRole::RelationBaseOf, D});
+  Builder.push_back(Relation{C, index::SymbolRole::RelationBaseOf, D});
+  Builder.push_back(Relation{B, index::SymbolRole::RelationChildOf, A});
+  Builder.push_back(Relation{C, index::SymbolRole::RelationChildOf, A});
+  Builder.push_back(Relation{D, index::SymbolRole::RelationChildOf, B});
+  Builder.push_back(Relation{D, index::SymbolRole::RelationChildOf, C});
+
+  RelationSlab Slab = std::move(Builder).build();
+  EXPECT_THAT(
+      Slab.lookup(A, index::SymbolRole::RelationBaseOf),
+      UnorderedElementsAre(Relation{A, index::SymbolRole::RelationBaseOf, B},
+                           Relation{A, index::SymbolRole::RelationBaseOf, C}));
+}
+
 TEST(SwapIndexTest, OldIndexRecycled) {
   auto Token = std::make_shared<int>();
   std::weak_ptr<int> WeakToken = Token;