diff --git a/core/core.services.yml b/core/core.services.yml
index f8c7c5d..70ca09c 100644
--- a/core/core.services.yml
+++ b/core/core.services.yml
@@ -263,10 +263,10 @@ services:
     arguments: ['@container.namespaces', '@cache.discovery', '@module_handler']
   plugin.manager.menu.link:
     class: Drupal\Core\Menu\MenuLinkManager
-    arguments: ['@menu.tree_storage', '@menu_link.static.overrides', '@module_handler', '@entity.manager', '@config.factory']
+    arguments: ['@menu.tree_storage', '@menu_link.static.overrides', '@module_handler']
   menu.link_tree:
     class: Drupal\Core\Menu\MenuLinkTree
-    arguments: ['@menu.tree_storage', '@plugin.manager.menu.link', '@request_stack', '@router.route_provider', '@module_handler', '@cache.menu', '@language_manager', '@access_manager', '@current_user', '@entity.manager', '@config.factory']
+    arguments: ['@menu.tree_storage', '@plugin.manager.menu.link', '@request_stack', '@router.route_provider', '@cache.menu', '@access_manager', '@current_user', '@entity.manager', '@config.factory']
   plugin.manager.menu.local_action:
     class: Drupal\Core\Menu\LocalActionManager
     arguments: ['@controller_resolver', '@request_stack', '@router.route_provider', '@module_handler', '@cache.discovery', '@language_manager', '@access_manager', '@current_user']
@@ -285,7 +285,7 @@ services:
     arguments: ['@plugin.manager.menu.link']
   menu.tree_storage:
     class: Drupal\Core\Menu\MenuTreeStorage
-    arguments: ['@database', '@url_generator', 'menu_tree']
+    arguments: ['@database', '@cache.menu', 'menu_tree']
     public: false  # Private to plugin.manager.menu.link and menu.link_tree
   menu_link.static.overrides:
     class: Drupal\Core\Menu\StaticMenuLinkOverrides
diff --git a/core/lib/Drupal/Core/Menu/MenuLinkManager.php b/core/lib/Drupal/Core/Menu/MenuLinkManager.php
index 0c0bc09..f7abe48 100644
--- a/core/lib/Drupal/Core/Menu/MenuLinkManager.php
+++ b/core/lib/Drupal/Core/Menu/MenuLinkManager.php
@@ -11,7 +11,6 @@
 use Drupal\Component\Plugin\Exception\PluginNotFoundException;
 use Drupal\Component\Utility\NestedArray;
 use Drupal\Component\Utility\String;
-use Drupal\Core\Cache\Cache;
 use Drupal\Core\Extension\ModuleHandlerInterface;
 use Drupal\Core\Plugin\Discovery\ContainerDerivativeDiscoveryDecorator;
 use Drupal\Core\Plugin\Discovery\YamlDiscovery;
@@ -177,9 +176,6 @@ public function getDefinitions() {
    * {@inheritdoc}
    */
   public function rebuild() {
-    // Fetch the list of existing menus, in case some are not longer populated
-    // after the rebuild.
-    $before_menus = $this->treeStorage->getMenuNames();
     $definitions = $this->getDefinitions();
     // Apply overrides from config.
     $overrides = $this->overrides->loadMultipleOverrides(array_keys($definitions));
@@ -189,8 +185,6 @@ public function rebuild() {
       }
     }
     $this->treeStorage->rebuild($definitions);
-    $affected_menus = $this->treeStorage->getMenuNames() + $before_menus;
-    Cache::invalidateTags(array('menu' => $affected_menus));
   }
 
   /**
@@ -240,8 +234,7 @@ public function getInstance(array $options) {
    * @param string $menu_name
    *   The name of the menu whose links will be deleted.
    */
-  public function deleteLinksInMenu($menu_name) {
-    $affected_menus = array($menu_name => $menu_name);
+  public function deleteLinksInMenu($menu_name) {;
     foreach ($this->treeStorage->loadByProperties(array('menu_name' => $menu_name)) as $plugin_id => $definition) {
       $instance = $this->createInstance($plugin_id);
       if ($instance->isResetable()) {
@@ -252,7 +245,6 @@ public function deleteLinksInMenu($menu_name) {
         $this->deleteInstance($instance, TRUE);
       }
     }
-    Cache::invalidateTags(array('menu' => $affected_menus));
   }
 
   /**
@@ -280,9 +272,6 @@ public function deleteLink($id, $persist = TRUE) {
     if ($definition) {
       $instance = $this->createInstance($id);
       $this->deleteInstance($instance, $persist);
-      // Many children may have moved.
-      $this->resetDefinitions();
-      Cache::invalidateTags(array('menu' => array($definition['menu_name'])));
     }
   }
 
@@ -340,9 +329,8 @@ public function createLink($id, array $definition) {
     // everything.
     $this->processDefinition($definition, $id);
 
-    // Store the new link in the tree and invalidate some caches.
-    $affected_menus = $this->treeStorage->save($definition);
-    Cache::invalidateTags(array('menu' => $affected_menus));
+    // Store the new link in the tree.
+    $this->treeStorage->save($definition);
     return $this->createInstance($id);
   }
 
@@ -354,9 +342,7 @@ public function updateLink($id, array $new_definition_values, $persist = TRUE) {
     if ($instance) {
       $new_definition_values['id'] = $id;
       $changed_definition = $instance->updateLink($new_definition_values, $persist);
-      $affected_menus = $this->treeStorage->save($changed_definition);
-      $this->resetDefinitions();
-      Cache::invalidateTags(array('menu' => $affected_menus));
+      $this->treeStorage->save($changed_definition);
     }
     return $instance;
   }
@@ -366,10 +352,7 @@ public function updateLink($id, array $new_definition_values, $persist = TRUE) {
    */
   public function resetLink($id) {
     $instance = $this->createInstance($id);
-    $affected_menus[$instance->getMenuName()] = $instance->getMenuName();
     $new_instance = $this->resetInstance($instance);
-    $affected_menus[$new_instance->getMenuName()] = $new_instance->getMenuName();
-    Cache::invalidateTags(array('menu' => $affected_menus));
     return $new_instance;
   }
 
diff --git a/core/lib/Drupal/Core/Menu/MenuLinkTree.php b/core/lib/Drupal/Core/Menu/MenuLinkTree.php
index 528863b..8997161 100644
--- a/core/lib/Drupal/Core/Menu/MenuLinkTree.php
+++ b/core/lib/Drupal/Core/Menu/MenuLinkTree.php
@@ -7,21 +7,13 @@
 
 namespace Drupal\Core\Menu;
 
-use Drupal\Component\Plugin\Exception\PluginException;
-use Drupal\Component\Plugin\Exception\PluginNotFoundException;
-use Drupal\Component\Utility\NestedArray;
-use Drupal\Component\Utility\String;
 use Drupal\Component\Utility\Unicode;
 use Drupal\Core\Access\AccessManager;
 use Drupal\Core\Cache\Cache;
+use Drupal\Core\Menu\MenuLinkManagerInterface;
 use Drupal\Core\Cache\CacheBackendInterface;
 use Drupal\Core\Config\ConfigFactoryInterface;
 use Drupal\Core\Entity\EntityManagerInterface;
-use Drupal\Core\Extension\ModuleHandlerInterface;
-use Drupal\Core\Language\LanguageManagerInterface;
-use Drupal\Core\Plugin\Discovery\ContainerDerivativeDiscoveryDecorator;
-use Drupal\Core\Plugin\Discovery\YamlDiscovery;
-use Drupal\Core\Plugin\Factory\ContainerFactory;
 use Drupal\Core\Routing\RouteProviderInterface;
 use Drupal\Core\Session\AccountInterface;
 use Symfony\Cmf\Component\Routing\RouteObjectInterface;
@@ -72,26 +64,6 @@ class MenuLinkTree implements MenuLinkTreeInterface {
     'id' => '',
   );
 
-  /**
-   * The object that discovers plugins managed by this manager.
-   *
-   * @var \Drupal\Component\Plugin\Discovery\DiscoveryInterface
-   */
-  protected $discovery;
-
-  /**
-   * The object that instantiates plugins managed by this manager.
-   *
-   * @var \Drupal\Component\Plugin\Factory\FactoryInterface
-   */
-  protected $factory;
-
-  /**
-   * The language manager.
-   *
-   * @var \Drupal\Core\Language\LanguageManagerInterface
-   */
-  protected $languageManager;
 
   /**
    * Cache backend instance for the extracted tree data.
@@ -164,13 +136,6 @@ class MenuLinkTree implements MenuLinkTreeInterface {
   protected $entityManager;
 
   /**
-   * The module handler.
-   *
-   * @var \Drupal\Core\Extension\ModuleHandlerInterface
-   */
-  protected $moduleHandler;
-
-  /**
    * The configuration factory.
    *
    * @var \Drupal\Core\Config\ConfigFactoryInterface
@@ -220,19 +185,15 @@ class MenuLinkTree implements MenuLinkTreeInterface {
    *
    * @param \Drupal\Core\Menu\MenuTreeStorageInterface $tree_storage
    *   The menu link tree storage.
-   * @param \Drupal\Core\Menu\StaticMenuLinkOverridesInterface $overrides
-   *   Service providing overrides for static links
+   * @param \Drupal\Core\Menu\MenuLinkManagerInterface $menu_link_manager
+   *   The menu link plugin manager.
    * @param \Symfony\Component\HttpFoundation\RequestStack $request_stack
    *   A request object for the controller resolver and finding the preferred
    *   menu and link for the current page.
    * @param \Drupal\Core\Routing\RouteProviderInterface $route_provider
    *   The route provider to load routes by name.
-   * @param \Drupal\Core\Extension\ModuleHandlerInterface $module_handler
-   *   The module handler.
    * @param \Drupal\Core\Cache\CacheBackendInterface $tree_cache_backend
    *   Cache backend instance for the extracted tree data.
-   * @param \Drupal\Core\Language\LanguageManagerInterface $language_manager
-   *   The language manager.
    * @param \Drupal\Core\Access\AccessManager $access_manager
    *   The access manager.
    * @param \Drupal\Core\Session\AccountInterface $account
@@ -242,16 +203,14 @@ class MenuLinkTree implements MenuLinkTreeInterface {
    * @param \Drupal\Core\Config\ConfigFactoryInterface $config_factory
    *   Configuration factory.
    */
-  public function __construct(MenuTreeStorageInterface $tree_storage, MenuLinkManagerInterface $menu_link_manager, RequestStack $request_stack, RouteProviderInterface $route_provider, ModuleHandlerInterface $module_handler, CacheBackendInterface $tree_cache_backend, LanguageManagerInterface $language_manager, AccessManager $access_manager, AccountInterface $account, EntityManagerInterface $entity_manager, ConfigFactoryInterface $config_factory) {
+  public function __construct(MenuTreeStorageInterface $tree_storage, MenuLinkManagerInterface $menu_link_manager, RequestStack $request_stack, RouteProviderInterface $route_provider, CacheBackendInterface $tree_cache_backend, AccessManager $access_manager, AccountInterface $account, EntityManagerInterface $entity_manager, ConfigFactoryInterface $config_factory) {
     $this->treeStorage = $tree_storage;
     $this->menuLinkManager = $menu_link_manager;
     $this->requestStack = $request_stack;
     $this->routeProvider = $route_provider;
     $this->accessManager = $access_manager;
     $this->account = $account;
-    $this->moduleHandler = $module_handler;
     $this->treeCacheBackend = $tree_cache_backend;
-    $this->languageManager = $language_manager;
     $this->entityManager = $entity_manager;
     $this->configFactory = $config_factory;
   }
@@ -439,8 +398,7 @@ protected function listSystemMenus() {
   /**
    * {@inheritdoc}
    */
-  public function buildPageData($menu_name, $max_depth = NULL, $only_active_trail = FALSE) {
-    $language_interface = $this->languageManager->getCurrentLanguage();
+  public function buildPageData($menu_name, $max_depth = NULL) {
 
     // Load the request corresponding to the current page.
     $request = $this->requestStack->getCurrentRequest();
@@ -455,18 +413,7 @@ public function buildPageData($menu_name, $max_depth = NULL, $only_active_trail
       $max_depth = min($max_depth, $this->treeStorage->maxDepth());
     }
     // Generate a cache ID (cid) specific for this page.
-    $cid = 'links:' . $menu_name . ':page:' . $system_path . ':' . $language_interface->id . ':' . $page_is_403 . ':' . (int) $max_depth;
-    // If we are asked for the active trail only, and $menu_name has not been
-    // built and cached for this page yet, then this likely means that it
-    // won't be built anymore, as this function is invoked from
-    // template_preprocess_page(). So in order to not build a giant menu tree
-    // that needs to be checked for access on all levels, we simply check
-    // whether we have the menu already in cache, or otherwise, build a
-    // minimum tree containing the active trail only.
-    // @see menu_set_active_trail()
-    if (!isset($this->menuPageTrees[$cid]) && $only_active_trail) {
-      $cid .= ':trail';
-    }
+    $cid = 'links:' . $menu_name . ':page:' . $system_path . ':' . $page_is_403 . ':' . (int) $max_depth;
 
     // @todo Decide whether it makes sense to static cache page menu trees.
     if (!isset($this->menuPageTrees[$cid])) {
@@ -478,7 +425,7 @@ public function buildPageData($menu_name, $max_depth = NULL, $only_active_trail
         $tree_parameters = $cache->data;
       }
       else {
-        $tree_parameters = $this->doBuildPageDataTreeParameters($menu_name, $max_depth, $only_active_trail, $page_is_403);
+        $tree_parameters = $this->doBuildPageDataTreeParameters($menu_name, $max_depth, $page_is_403);
 
         // Cache the tree building parameters using the page-specific cid.
         $this->treeCacheBackend->set($cid, $tree_parameters, Cache::PERMANENT, array('menu' => $menu_name));
@@ -500,8 +447,6 @@ public function buildPageData($menu_name, $max_depth = NULL, $only_active_trail
    *   The menu name.
    * @param int $max_depth
    *   The maximum allowed depth of menus.
-   * @param bool $only_active_trail
-   *   If TRUE, just load level 0 plus the active trail, otherwise load the full
    *   menu tree.
    * @param bool $page_is_403
    *   Is the current request happening on a 403 subrequest.
@@ -509,7 +454,7 @@ public function buildPageData($menu_name, $max_depth = NULL, $only_active_trail
    * @return array
    *   An array of tree parameters.
    */
-  protected function doBuildPageDataTreeParameters($menu_name, $max_depth, $only_active_trail, $page_is_403) {
+  protected function doBuildPageDataTreeParameters($menu_name, $max_depth, $page_is_403) {
     $tree_parameters = array(
       'min_depth' => 1,
       'max_depth' => $max_depth,
@@ -519,21 +464,9 @@ protected function doBuildPageDataTreeParameters($menu_name, $max_depth, $only_a
     // parameters accordingly.
     if (!$page_is_403) {
       $active_trail = $this->getActiveTrailIds($menu_name);
-      // The active trail contains more than only array(0 => 0).
-      if (count($active_trail) > 1) {
-        // If we are asked to build links for the active trail only,skip
-        // the entire 'expanded' handling.
-        if ($only_active_trail) {
-          $tree_parameters['only_active_trail'] = TRUE;
-        }
-      }
-      $parents = $active_trail;
-
-      if (!$only_active_trail) {
-        // Collect all the links set to be expanded, and then add all of
-        // their children to the list as well.
-        $parents = $this->treeStorage->getExpanded($menu_name, $parents);
-      }
+      // Collect all the links set to be expanded, and then add all of
+      // their children to the list as well.
+      $parents = $this->treeStorage->getExpanded($menu_name, $active_trail);
     }
     else {
       // If access is denied, we only show top-level links in menus.
@@ -551,14 +484,13 @@ protected function doBuildPageDataTreeParameters($menu_name, $max_depth, $only_a
    * @todo should this accept a menu link instance or just the ID?
    */
   public function buildAllData($menu_name, $id = NULL, $max_depth = NULL) {
-    $language_interface = $this->languageManager->getCurrentLanguage();
 
     // Use ID as a flag for whether the data being loaded is for the whole
     // tree.
     $id = isset($id) ? $id : '%';
     // Generate a cache ID (cid) specific for this $menu_name, $link, $language,
     // and depth.
-    $cid = 'links:' . $menu_name . ':all:' . $id . ':' . $language_interface->id . ':' . (int) $max_depth;
+    $cid = 'links:' . $menu_name . ':all:' . $id . ':' . (int) $max_depth;
     if (!isset($this->buildAllDataParameters[$cid])) {
       $tree_parameters = array(
         'min_depth' => 1,
@@ -598,16 +530,16 @@ public function getChildLinks($id, $max_relative_depth = NULL) {
    * {@inheritdoc}
    */
   public function buildSubtree($id, $max_relative_depth = NULL) {
-    $subtree = $this->treeStorage->loadSubtree($id, $max_relative_depth);
-    if ($subtree) {
-      // Check access and instantiate. @todo rename these methods.
+    $data = $this->treeStorage->loadSubtreeData($id, $max_relative_depth);
+    if ($data['subtree']) {
+      $subtree = $data['subtree'];
+      // Check access and instantiate.
       $instance = $this->menuLinkCheckAccess($subtree['definition']);
       if ($instance) {
         $subtree['link'] = $instance;
-        $route_names = $this->collectRoutes($subtree['below']);
         // Pre-load all the route objects in the tree for access checks.
-        if ($route_names) {
-          $this->routeProvider->getRoutesByNames($route_names);
+        if ($data['route_names']) {
+          $this->routeProvider->getRoutesByNames($data['route_names']);
         }
         $this->treeCheckAccess($subtree['below']);
         return $subtree;
@@ -620,36 +552,7 @@ public function buildSubtree($id, $max_relative_depth = NULL) {
    * {@inheritdoc}
    */
   public function buildTree($menu_name, array $parameters = array()) {
-    $language_interface = $this->languageManager->getCurrentLanguage();
-
-    // Build the cache id; sort parents to prevent duplicate storage and remove
-    // default parameter values.
-    asort($parameters);
-    if (isset($parameters['expanded'])) {
-      sort($parameters['expanded']);
-    }
-    $tree_cid = 'links:' . $menu_name . ':tree-data:' . $language_interface->id . ':' . hash('sha256', serialize($parameters));
-
-    // If we do not have this tree in the static cache, check cache.menu.
-    if (!isset($this->menuTree[$tree_cid])) {
-      $cache = $this->treeCacheBackend->get($tree_cid);
-      if ($cache && isset($cache->data)) {
-        $this->menuTree[$tree_cid] = $cache->data;
-      }
-    }
-
-    if (!isset($this->menuTree[$tree_cid])) {
-      // Rebuild the links which are stored.
-      $data['tree'] = $this->treeStorage->loadTree($menu_name, $parameters);
-      $data['route_names'] = $this->collectRoutes($data['tree']);
-      // Cache the data, if it is not already in the cache.
-      $this->treeCacheBackend->set($tree_cid, $data, Cache::PERMANENT, array('menu' => $menu_name));
-      $this->menuTree[$tree_cid] = $data;
-    }
-    else {
-      $data = $this->menuTree[$tree_cid];
-    }
-
+    $data = $this->treeStorage->loadTreeData($menu_name, $parameters);
     // Pre-load all the route objects in the tree for access checks.
     if ($data['route_names']) {
       $this->routeProvider->getRoutesByNames($data['route_names']);
@@ -660,36 +563,6 @@ public function buildTree($menu_name, array $parameters = array()) {
   }
 
   /**
-   * Traverses the menu tree and collects all the route names.
-   *
-   * @param array $tree
-   *   The menu tree you wish to operate on.
-   *
-   * @return array
-   *   Array of route names, with all values being unique.
-   */
-  protected function collectRoutes($tree) {
-    return array_values($this->doCollectRoutes($tree));
-  }
-
-  /**
-   * Recursive helper function to collect all the route names.
-   */
-  protected function doCollectRoutes($tree) {
-    $route_names = array();
-    foreach ($tree as $key => $v) {
-      $definition = $tree[$key]['definition'];
-      if (!empty($definition['route_name'])) {
-        $route_names[$definition['route_name']] = $definition['route_name'];
-      }
-      if ($tree[$key]['below']) {
-        $route_names += $this->doCollectRoutes($tree[$key]['below']);
-      }
-    }
-    return $route_names;
-  }
-
-  /**
    * Sorts the menu tree and recursively checks access for each item.
    *
    * @param array $tree
diff --git a/core/lib/Drupal/Core/Menu/MenuLinkTreeInterface.php b/core/lib/Drupal/Core/Menu/MenuLinkTreeInterface.php
index 10b05d7..7b49790 100644
--- a/core/lib/Drupal/Core/Menu/MenuLinkTreeInterface.php
+++ b/core/lib/Drupal/Core/Menu/MenuLinkTreeInterface.php
@@ -81,10 +81,6 @@ public function setActiveMenuNames(array $menu_names);
    *   The named menu links to return.
    * @param int $max_depth
    *   (optional) The maximum depth of links to retrieve.
-   * @param bool $only_active_trail
-   *   (optional) Whether to only return the links in the active trail (TRUE)
-   *   instead of all links on every level of the menu link tree (FALSE).
-   *   Defaults to FALSE.
    *
    * @return array
    *   An array of menu links, in the order they should be rendered. The array
@@ -98,7 +94,7 @@ public function setActiveMenuNames(array $menu_names);
    *                   is a hint for adding appropriate classes for theming.
    *   - in_active_trail: boolean
    */
-  public function buildPageData($menu_name, $max_depth = NULL, $only_active_trail = FALSE);
+  public function buildPageData($menu_name, $max_depth = NULL);
 
   /**
    * Gets the data structure representing a named menu tree.
diff --git a/core/lib/Drupal/Core/Menu/MenuTreeStorage.php b/core/lib/Drupal/Core/Menu/MenuTreeStorage.php
index d2e136c..85025d8 100644
--- a/core/lib/Drupal/Core/Menu/MenuTreeStorage.php
+++ b/core/lib/Drupal/Core/Menu/MenuTreeStorage.php
@@ -13,7 +13,8 @@
 use Drupal\Component\Plugin\Exception\PluginException;
 use Drupal\Core\Database\SchemaObjectExistsException;
 use Drupal\Core\Database\Database;
-use Drupal\Core\Routing\UrlGeneratorInterface;
+use Drupal\Core\Cache\Cache;
+use Drupal\Core\Cache\CacheBackendInterface;
 
 /**
  * Provides a tree storage using the database.
@@ -33,11 +34,11 @@ class MenuTreeStorage implements MenuTreeStorageInterface {
   protected $connection;
 
   /**
-   * The URL generator.
+   * Cache backend instance for the extracted tree data.
    *
-   * @var \Drupal\Core\Routing\UrlGenerator
+   * @var \Drupal\Core\Cache\CacheBackendInterface
    */
-  protected $urlGenerator;
+  protected $treeCacheBackend;
 
   /**
    * The database table name.
@@ -99,16 +100,16 @@ class MenuTreeStorage implements MenuTreeStorageInterface {
    *
    * @param \Drupal\Core\Database\Connection $connection
    *   A Database connection to use for reading and writing configuration data.
-   * @param \Drupal\Core\Routing\UrlGeneratorInterface $url_generator
-   *   The url generator.
+   * @param \Drupal\Core\Cache\CacheBackendInterface $tree_cache_backend
+   *   Cache backend instance for the extracted tree data.
    * @param string $table
    *   A database table name to store configuration data in.
    * @param array $options
    *   (optional) Any additional database connection options to use in queries.
    */
-  public function __construct(Connection $connection, UrlGeneratorInterface $url_generator, $table, array $options = array()) {
+  public function __construct(Connection $connection, CacheBackendInterface $tree_cache_backend, $table, array $options = array()) {
     $this->connection = $connection;
-    $this->urlGenerator = $url_generator;
+    $this->treeCacheBackend = $tree_cache_backend;
     $this->table = $table;
     $this->options = $options;
   }
@@ -134,6 +135,9 @@ public function rebuild(array $definitions) {
     $links = array();
     $children = array();
     $top_links = array();
+    // Fetch the list of existing menus, in case some are not longer populated
+    // after the rebuild.
+    $before_menus = $this->getMenuNames();
     if ($definitions) {
       foreach ($definitions as $id => $link) {
         if (!empty($link['parent'])) {
@@ -177,6 +181,8 @@ public function rebuild(array $definitions) {
       $this->purgeMultiple($result);
     }
     $this->resetDefinitions();
+    $affected_menus = $this->getMenuNames() + $before_menus;
+    Cache::invalidateTags(array('menu' => $affected_menus));
   }
 
   /**
@@ -272,6 +278,7 @@ public function save(array $link) {
       throw $e;
     }
     $this->resetDefinitions();
+    Cache::invalidateTags(array('menu' => $affected_menus));
     return $affected_menus;
   }
 
@@ -389,7 +396,9 @@ public function delete($id) {
         ->execute();
 
       $this->updateParentalStatus($item);
+      // Many children may have moved.
       $this->resetDefinitions();
+      Cache::invalidateTags(array('menu' => $item['menu_name']));
     }
   }
 
@@ -740,74 +749,149 @@ protected function saveRecursive($id, &$children, &$links) {
   /**
    * {@inheritdoc}
    */
-  public function loadTree($menu_name, array $parameters = array()) {
-    $query = $this->connection->select($this->table, $this->options);
-    $query->fields($this->table);
-    for ($i = 1; $i <= $this->maxDepth(); $i++) {
-      $query->orderBy('p' . $i, 'ASC');
+  public function loadTreeData($menu_name, array $parameters = array()) {
+    // Build the cache id; sort parents to prevent duplicate storage and remove
+    // default parameter values.
+    asort($parameters);
+    if (isset($parameters['expanded'])) {
+      sort($parameters['expanded']);
+    }
+    // @todo - may be able to skip hashing after https://drupal.org/node/2224847
+    $tree_cid = "tree-data:$menu_name:" . hash('sha256', serialize($parameters));
+    $cache = $this->treeCacheBackend->get($tree_cid);
+    if ($cache && isset($cache->data)) {
+      $data = $cache->data;
+      // Cache the definitions in memory so they don't need to be loaded again.
+      $this->definitions += $data['definitions'];
+      unset($data['definitions']);
     }
+    else {
+      $query = $this->connection->select($this->table, $this->options);
+      $query->fields($this->table);
+      for ($i = 1; $i <= $this->maxDepth(); $i++) {
+        $query->orderBy('p' . $i, 'ASC');
+      }
 
-    $query->condition('menu_name', $menu_name);
+      $query->condition('menu_name', $menu_name);
 
-    if (!empty($parameters['expanded'])) {
-      $query->condition('parent', $parameters['expanded'], 'IN');
-    }
-    elseif (!empty($parameters['only_active_trail'])) {
-      $query->condition('id', $parameters['active_trail'], 'IN');
-    }
-    $min_depth = (isset($parameters['min_depth']) ? $parameters['min_depth'] : NULL);
-    if ($min_depth) {
-      $query->condition('depth', $min_depth, '>=');
-    }
-    if (isset($parameters['max_depth'])) {
-      $query->condition('depth', $parameters['max_depth'], '<=');
-    }
-    // Add custom query conditions, if any were passed.
-    if (!empty($parameters['conditions'])) {
-      // Only allow conditions that are testing definition fields.
-      $parameters['conditions'] = array_intersect_key($parameters['conditions'], array_flip($this->definitionFields()));
-      foreach ($parameters['conditions'] as $column => $value) {
-        $query->condition($column, $value);
+      if (!empty($parameters['expanded'])) {
+        $query->condition('parent', $parameters['expanded'], 'IN');
       }
-    }
-    $active_trail = (isset($parameters['active_trail']) ? $parameters['active_trail'] : array());
-    $links = $this->safeExecuteSelect($query)->fetchAll(\PDO::FETCH_ASSOC);
-    if (!isset($min_depth)) {
-      $first_link = reset($links);
-      if ($first_link) {
-        $min_depth = $first_link['depth'];
+      elseif (!empty($parameters['only_active_trail'])) {
+        $query->condition('id', $parameters['active_trail'], 'IN');
+      }
+      $min_depth = (isset($parameters['min_depth']) ? $parameters['min_depth'] : NULL);
+      if ($min_depth) {
+        $query->condition('depth', $min_depth, '>=');
+      }
+      if (isset($parameters['max_depth'])) {
+        $query->condition('depth', $parameters['max_depth'], '<=');
+      }
+      // Add custom query conditions, if any were passed.
+      if (!empty($parameters['conditions'])) {
+        // Only allow conditions that are testing definition fields.
+        $parameters['conditions'] = array_intersect_key($parameters['conditions'], array_flip($this->definitionFields()));
+        foreach ($parameters['conditions'] as $column => $value) {
+          $query->condition($column, $value);
+        }
+      }
+      $active_trail = (isset($parameters['active_trail']) ? $parameters['active_trail'] : array());
+      $links = $this->safeExecuteSelect($query)->fetchAll(\PDO::FETCH_ASSOC);
+      if (!isset($min_depth)) {
+        $first_link = reset($links);
+        if ($first_link) {
+          $min_depth = $first_link['depth'];
+        }
+      }
+      $data['tree'] = $this->doBuildTreeData($links, $active_trail, $min_depth);
+      $data['definitions'] = array();
+      $data['route_names'] = $this->collectRoutes($data['tree'], $data['definitions']);
+      $this->treeCacheBackend->set($tree_cid, $data, Cache::PERMANENT, array('menu' => $menu_name));
+      // The definitions were already added to $this->definitions in
+      // $this->doBuildTreeData()
+      unset($data['definitions']);
+    }
+    return $data;
+  }
+
+  /**
+   * Traverses the menu tree and collects all the route names.
+   *
+   * @param array $tree
+   *   The menu tree you wish to operate on.
+   * @param array $definitions
+   *   An array to accumulate definitions.
+   *
+   * @return array
+   *   Array of route names, with all values being unique.
+   */
+  protected function collectRoutes(array $tree, array &$definitions) {
+    return array_values($this->doCollectRoutes($tree, $definitions));
+  }
+
+  /**
+   * Recursive helper function to collect all the route names and defintions.
+   */
+  protected function doCollectRoutes(array $tree, array &$definitions) {
+    $route_names = array();
+    foreach ($tree as $key => $v) {
+      $definition = $tree[$key]['definition'];
+      $definitions[$definition['id']] = $definition;
+      if (!empty($definition['route_name'])) {
+        $route_names[$definition['route_name']] = $definition['route_name'];
+      }
+      if ($tree[$key]['below']) {
+        $route_names += $this->doCollectRoutes($tree[$key]['below'], $definitions);
       }
     }
-    $tree = $this->doBuildTreeData($links, $active_trail, $min_depth);
-    return $tree;
+    return $route_names;
   }
 
   /**
    * {@inheritdoc}
    */
-  public function loadSubtree($id, $max_relative_depth = NULL) {
-    $tree = array();
-    $root = $this->loadFull($id);
-    if (!$root) {
-      return $tree;
-    }
-    $query = $this->connection->select($this->table, $this->options);
-    $query->fields($this->table);
-    for ($i = 1; $i <= $this->maxDepth(); $i++) {
-      $query->orderBy('p' . $i, 'ASC');
-    }
-    $query->condition('hidden', 0);
-    $query->condition('menu_name', $root['menu_name']);
-    for ($i = 1; $i <= $root['depth']; $i++) {
-      $query->condition("p$i", $root["p$i"]);
+  public function loadSubtreeData($id, $max_relative_depth = NULL) {
+    $tree_cid = "subtree-data:$id:$max_relative_depth";
+    $cache = $this->treeCacheBackend->get($tree_cid);
+    if ($cache && isset($cache->data)) {
+      $data = $cache->data;
+      // Cache the definitions in memory so they don't need to be loaded again.
+      $this->definitions += $data['definitions'];
+      unset($data['definitions']);
     }
-    if (!empty($max_relative_depth)) {
-      $query->condition('depth', (int) $root['depth'] + $max_relative_depth, '<=');
+    else {
+      $tree = array();
+      $root = $this->loadFull($id);
+      if (!$root) {
+        return $tree;
+      }
+      $query = $this->connection->select($this->table, $this->options);
+      $query->fields($this->table);
+      for ($i = 1; $i <= $this->maxDepth(); $i++) {
+        $query->orderBy('p' . $i, 'ASC');
+      }
+      $query->condition('hidden', 0);
+      $query->condition('menu_name', $root['menu_name']);
+      for ($i = 1; $i <= $root['depth']; $i++) {
+        $query->condition("p$i", $root["p$i"]);
+      }
+      if (!empty($max_relative_depth)) {
+        $query->condition('depth', (int) $root['depth'] + $max_relative_depth, '<=');
+      }
+      $links = $this->safeExecuteSelect($query)->fetchAll(\PDO::FETCH_ASSOC);
+      $tree = $this->doBuildTreeData($links, array(), $root['depth']);
+      $data['definitions'] = array();
+      $data['route_names'] = $this->collectRoutes($tree, $data['definitions']);
+      $data['subtree'] = current($tree);
+      if ($data['subtree']) {
+        $menu_name = $data['subtree']['definition']['menu_name'];
+        $this->treeCacheBackend->set($tree_cid, $data, Cache::PERMANENT, array('menu' => $menu_name));
+      }
+      // The definitions were already added to $this->definitions in
+      // $this->doBuildTreeData()
+      unset($data['definitions']);
     }
-    $links = $this->safeExecuteSelect($query)->fetchAll(\PDO::FETCH_ASSOC);
-    $tree = $this->doBuildTreeData($links, array(), $root['depth']);
-    $subtree = current($tree);
-    return $subtree;
+    return $data;
   }
 
   /**
diff --git a/core/lib/Drupal/Core/Menu/MenuTreeStorageInterface.php b/core/lib/Drupal/Core/Menu/MenuTreeStorageInterface.php
index ca878ad..c9472f6 100644
--- a/core/lib/Drupal/Core/Menu/MenuTreeStorageInterface.php
+++ b/core/lib/Drupal/Core/Menu/MenuTreeStorageInterface.php
@@ -140,9 +140,11 @@ public function delete($id);
    *     in the plugin definition.
    *
    * @return array
-   *   A fully built menu tree.
+   *   An array with 2 elements:
+   *   - tree: A fully built menu tree.
+   *   - route_names: An array of all route names used in the tree.
    */
-  public function loadTree($menu_name, array $parameters = array());
+  public function loadTreeData($menu_name, array $parameters = array());
 
   /**
    * Loads all the visible menu links that are below the given ID.
@@ -175,7 +177,7 @@ public function getAllChildIds($id);
   /**
    * Loads a subtree rooted by the given menu link plugin ID.
    *
-   * The returned links are structured like those from loadTree().
+   * The returned links are structured like those from loadTreeData().
    *
    * @param string $id
    *   The menu link plugin ID.
@@ -183,9 +185,11 @@ public function getAllChildIds($id);
    *   The maximum depth of child menu links relative to the passed in.
    *
    * @return array
-   *   A fully built menu subtree.
+   *   An array with 2 elements:
+   *   - subtree: A fully built menu tree element or FALSE.
+   *   - route_names: An array of all route names used in the subtree.
    */
-  public function loadSubtree($id, $max_relative_depth = NULL);
+  public function loadSubtreeData($id, $max_relative_depth = NULL);
 
   /**
    * Returns all the IDs that represent the path to the root of the tree.
diff --git a/core/modules/system/src/Tests/Menu/MenuTreeStorageTest.php b/core/modules/system/src/Tests/Menu/MenuTreeStorageTest.php
index 647ade1..04572cf 100644
--- a/core/modules/system/src/Tests/Menu/MenuTreeStorageTest.php
+++ b/core/modules/system/src/Tests/Menu/MenuTreeStorageTest.php
@@ -56,7 +56,7 @@ public static function getInfo() {
   protected function setUp() {
     parent::setUp();
 
-    $this->treeStorage = new MenuTreeStorage($this->container->get('database'), $this->container->get('url_generator'), 'menu_tree');
+    $this->treeStorage = new MenuTreeStorage($this->container->get('database'), $this->container->get('cache.menu'), 'menu_tree');
     $this->connection = $this->container->get('database');
   }
 
@@ -81,7 +81,7 @@ protected function doTestEmptyStorage() {
   protected function doTestTable() {
     // Test that we can create a tree storage with an arbitrary table name and
     // that selecting from the storage creates the table.
-    $tree_storage = new MenuTreeStorage($this->container->get('database'), $this->container->get('url_generator'), 'test_menu_tree');
+    $tree_storage = new MenuTreeStorage($this->container->get('database'), $this->container->get('cache.menu'), 'test_menu_tree');
     $this->assertFalse($this->connection->schema()->tableExists('test_menu_tree'), 'Test table is not yet created');
     $tree_storage->countMenuLinks();
     $this->assertTrue($this->connection->schema()->tableExists('test_menu_tree'), 'Test table was created');
@@ -243,7 +243,7 @@ public function testMenuHiddenChildLinks() {
   }
 
   /**
-   * Tests the loadTree method.
+   * Tests the loadTreeData method.
    */
   public function testLoadTree() {
     $this->addMenuLink('test1', '');
@@ -252,31 +252,34 @@ public function testLoadTree() {
     $this->addMenuLink('test4');
     $this->addMenuLink('test5', 'test4');
 
-    $result = $this->treeStorage->loadTree('tools');
-    $this->assertEqual(count($result['test1']['below']), 1);
-    $this->assertEqual(count($result['test1']['below']['test2']['below']), 1);
-    $this->assertEqual(count($result['test1']['below']['test2']['below']['test3']['below']), 0);
-    $this->assertEqual(count($result['test4']['below']), 1);
-    $this->assertEqual(count($result['test4']['below']['test5']['below']), 0);
-
-    $result = $this->treeStorage->loadTree('tools', array('active_trail' => array('test4', 'test5')));
-    $this->assertEqual(count($result['test1']['below']), 1);
-    $this->assertFalse($result['test1']['in_active_trail']);
-    $this->assertEqual(count($result['test1']['below']['test2']['below']), 1);
-    $this->assertFalse($result['test1']['below']['test2']['in_active_trail']);
-    $this->assertEqual(count($result['test1']['below']['test2']['below']['test3']['below']), 0);
-    $this->assertFalse($result['test1']['below']['test2']['below']['test3']['in_active_trail']);
-    $this->assertEqual(count($result['test4']['below']), 1);
-    $this->assertTrue($result['test4']['in_active_trail']);
-    $this->assertEqual(count($result['test4']['below']['test5']['below']), 0);
-    $this->assertTrue($result['test4']['below']['test5']['in_active_trail']);
-
-    $result = $this->treeStorage->loadTree('tools', array('active_trail' => array('test4', 'test5'), 'only_active_trail' => TRUE));
-    $this->assertTrue(empty($result['test1']));
-    $this->assertEqual(count($result['test4']['below']), 1);
-    $this->assertTrue($result['test4']['in_active_trail']);
-    $this->assertEqual(count($result['test4']['below']['test5']['below']), 0);
-    $this->assertTrue($result['test4']['below']['test5']['in_active_trail']);
+    $data = $this->treeStorage->loadTreeData('tools');
+    $tree = $data['tree'];
+    $this->assertEqual(count($tree['test1']['below']), 1);
+    $this->assertEqual(count($tree['test1']['below']['test2']['below']), 1);
+    $this->assertEqual(count($tree['test1']['below']['test2']['below']['test3']['below']), 0);
+    $this->assertEqual(count($tree['test4']['below']), 1);
+    $this->assertEqual(count($tree['test4']['below']['test5']['below']), 0);
+
+    $data = $this->treeStorage->loadTreeData('tools', array('active_trail' => array('test4', 'test5')));
+    $tree = $data['tree'];
+    $this->assertEqual(count($tree['test1']['below']), 1);
+    $this->assertFalse($tree['test1']['in_active_trail']);
+    $this->assertEqual(count($tree['test1']['below']['test2']['below']), 1);
+    $this->assertFalse($tree['test1']['below']['test2']['in_active_trail']);
+    $this->assertEqual(count($tree['test1']['below']['test2']['below']['test3']['below']), 0);
+    $this->assertFalse($tree['test1']['below']['test2']['below']['test3']['in_active_trail']);
+    $this->assertEqual(count($tree['test4']['below']), 1);
+    $this->assertTrue($tree['test4']['in_active_trail']);
+    $this->assertEqual(count($tree['test4']['below']['test5']['below']), 0);
+    $this->assertTrue($tree['test4']['below']['test5']['in_active_trail']);
+
+    $data = $this->treeStorage->loadTreeData('tools', array('active_trail' => array('test4', 'test5'), 'only_active_trail' => TRUE));
+    $tree = $data['tree'];
+    $this->assertTrue(empty($tree['test1']));
+    $this->assertEqual(count($tree['test4']['below']), 1);
+    $this->assertTrue($tree['test4']['in_active_trail']);
+    $this->assertEqual(count($tree['test4']['below']['test5']['below']), 0);
+    $this->assertTrue($tree['test4']['below']['test5']['in_active_trail']);
   }
 
   /**