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
@@ -63,6 +63,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,124 @@
+//===--- Ref.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/DenseMap.h"
+#include "llvm/Support/StringSaver.h"
+#include "llvm/Support/raw_ostream.h"
+#include <cstdint>
+#include <set>
+#include <utility>
+
+namespace clang {
+namespace clangd {
+
+struct RelationKey {
+  SymbolID Symbol;
+  index::SymbolRole Kind;
+
+  bool operator==(const RelationKey &Other) const {
+    return Symbol == Other.Symbol && Kind == Other.Kind;
+  }
+
+private:
+  friend llvm::hash_code hash_value(const RelationKey &Key) {
+    return llvm::hash_combine(Key.Symbol, static_cast<uint32_t>(Key.Kind));
+  }
+};
+
+class RelationSlab {
+public:
+  // Key.Symbol is Key.Kind of every symbol in Value.
+  // For example, if Key.Kind == SymbolRole::RelationChildOf,
+  // then Key.Symbol is the child of every symbol in Value (i.e. the symbols
+  // in Value are the base classes of Key.Symbol).
+  struct Relation {
+    RelationKey Key;
+    llvm::ArrayRef<SymbolID> Value;
+  };
+  using value_type = std::pair<RelationKey, llvm::ArrayRef<SymbolID>>;
+  using const_iterator = std::vector<value_type>::const_iterator;
+  using iterator = const_iterator;
+
+  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(); }
+  size_t numRelations() const { return NumRelations; }
+  bool empty() const { return Relations.empty(); }
+
+  size_t bytes() const {
+    return sizeof(*this) + Arena.getTotalMemory() +
+           sizeof(value_type) * Relations.capacity();
+  }
+
+  // RelationSlab::Builder is a mutable container that can 'freeze' to
+  // RelationSlab.
+  class Builder {
+  public:
+    Builder() {}
+    // Adds a relation to the slab.
+    void insert(const RelationKey &Key, const SymbolID &S);
+    // Consumes the builder to finalize the slab.
+    RelationSlab build() &&;
+
+  private:
+    llvm::BumpPtrAllocator Arena;
+    llvm::DenseMap<RelationKey, std::vector<SymbolID>> Relations;
+  };
+
+private:
+  RelationSlab(std::vector<value_type> Relations, llvm::BumpPtrAllocator Arena,
+               size_t NumRelations)
+      : Arena(std::move(Arena)), Relations(std::move(Relations)),
+        NumRelations(NumRelations) {}
+
+  llvm::BumpPtrAllocator Arena;
+  std::vector<value_type> Relations;
+  // Number of all relations.
+  size_t NumRelations = 0;
+};
+
+} // namespace clangd
+} // namespace clang
+
+namespace llvm {
+
+// Support RelationKeys as DenseMap keys.
+template <> struct DenseMapInfo<clang::clangd::RelationKey> {
+  static inline clang::clangd::RelationKey getEmptyKey() {
+    return {DenseMapInfo<clang::clangd::SymbolID>::getEmptyKey(),
+            clang::index::SymbolRole::RelationChildOf};
+  }
+
+  static inline clang::clangd::RelationKey getTombstoneKey() {
+    return {DenseMapInfo<clang::clangd::SymbolID>::getTombstoneKey(),
+            clang::index::SymbolRole::RelationChildOf};
+  }
+
+  static unsigned getHashValue(const clang::clangd::RelationKey &Key) {
+    return hash_value(Key);
+  }
+
+  static bool isEqual(const clang::clangd::RelationKey &LHS,
+                      const clang::clangd::RelationKey &RHS) {
+    return LHS == RHS;
+  }
+};
+
+} // namespace llvm
+
+#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,35 @@
+//===--- Ref.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"
+
+namespace clang {
+namespace clangd {
+
+void RelationSlab::Builder::insert(const RelationKey &Key, const SymbolID &S) {
+  Relations[Key].push_back(S);
+}
+
+RelationSlab RelationSlab::Builder::build() && {
+  // Reallocate relations on the arena to reduce waste and indirections when
+  // reading.
+  std::vector<std::pair<RelationKey, llvm::ArrayRef<SymbolID>>> Result;
+  Result.reserve(Relations.size());
+  size_t NumRelations = 0;
+  for (auto &Entry : Relations) {
+    auto &Rels = Entry.second;
+
+    NumRelations += Rels.size();
+    Result.emplace_back(Entry.first,
+                        llvm::ArrayRef<SymbolID>(Rels).copy(Arena));
+  }
+  return RelationSlab(std::move(Result), std::move(Arena), NumRelations);
+}
+
+} // namespace clangd
+} // namespace clang