[SyncFS] Wire up MetadataDatabaseIndex to MetadataDatabase

chrome/browser/sync_file_system/drive_backend/metadata_database.cc

 // Copyright 2013 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "chrome/browser/sync_file_system/drive_backend/metadata_database.h"
 
 #include <algorithm>
 #include <stack>
 
 #include "base/bind.h"
 #include "base/callback.h"
 #include "base/file_util.h"
 #include "base/files/file_path.h"
 #include "base/location.h"
 #include "base/memory/scoped_vector.h"
 #include "base/message_loop/message_loop_proxy.h"
 #include "base/sequenced_task_runner.h"
 #include "base/stl_util.h"
 #include "base/strings/string_number_conversions.h"
 #include "base/strings/string_util.h"
 #include "base/strings/stringprintf.h"
 #include "base/task_runner_util.h"
 #include "base/threading/thread_restrictions.h"
 #include "chrome/browser/drive/drive_api_util.h"
 #include "chrome/browser/sync_file_system/drive_backend/drive_backend_constants.h"
 #include "chrome/browser/sync_file_system/drive_backend/drive_backend_util.h"
 #include "chrome/browser/sync_file_system/drive_backend/metadata_database.pb.h"
+#include "chrome/browser/sync_file_system/drive_backend/metadata_database_index.h"
 #include "chrome/browser/sync_file_system/drive_backend/metadata_db_migration_util.h"
 #include "chrome/browser/sync_file_system/logger.h"
 #include "chrome/browser/sync_file_system/syncable_file_system_util.h"
 #include "google_apis/drive/drive_api_parser.h"
 #include "google_apis/drive/drive_entry_kinds.h"
 #include "third_party/leveldatabase/src/include/leveldb/db.h"
 #include "third_party/leveldatabase/src/include/leveldb/env.h"
 #include "third_party/leveldatabase/src/include/leveldb/write_batch.h"
 #include "webkit/common/fileapi/file_system_util.h"
 
 namespace sync_file_system {
 namespace drive_backend {
 
 namespace {
 
-typedef MetadataDatabase::MetadataByID MetadataByID;
-typedef MetadataDatabase::TrackerByID TrackerByID;
-typedef MetadataDatabase::TrackerIDsByParentAndTitle TrackerIDsByParentAndTitle;
-typedef MetadataDatabase::TrackerIDsByTitle TrackerIDsByTitle;
-
 bool IsAppRoot(const FileTracker& tracker) {
   return tracker.tracker_kind() == TRACKER_KIND_APP_ROOT ||
       tracker.tracker_kind() == TRACKER_KIND_DISABLED_APP_ROOT;
 }
 
 std::string RemovePrefix(const std::string& str, const std::string& prefix) {
   if (StartsWithASCII(str, prefix, true))
     return str.substr(prefix.size());
   return str;
 }
@@ skipping 49 matching lines @@
   app_root_tracker->set_needs_folder_listing(false);
   *app_root_tracker->mutable_synced_details() = app_root_metadata.details();
   return app_root_tracker.Pass();
 }
 
 void AdaptLevelDBStatusToSyncStatusCode(const SyncStatusCallback& callback,
                                         const leveldb::Status& status) {
   callback.Run(LevelDBStatusToSyncStatusCode(status));
 }
 
-template <typename OutputIterator>
-OutputIterator PushChildTrackersToContainer(
-    const TrackerIDsByParentAndTitle& trackers_by_parent,
-    int64 parent_tracker_id,
-    OutputIterator target_itr) {
-  TrackerIDsByParentAndTitle::const_iterator found =
-      trackers_by_parent.find(parent_tracker_id);
-  if (found == trackers_by_parent.end())
-    return target_itr;
-
-  for (TrackerIDsByTitle::const_iterator title_itr = found->second.begin();
-       title_itr != found->second.end(); ++title_itr) {
-    const TrackerIDSet& trackers = title_itr->second;
-    for (TrackerIDSet::const_iterator tracker_itr = trackers.begin();
-         tracker_itr != trackers.end(); ++tracker_itr) {
-      *target_itr = *tracker_itr;
-      ++target_itr;
-    }
-  }
-  return target_itr;
-}
-
 std::string GetTrackerTitle(const FileTracker& tracker) {
   if (tracker.has_synced_details())
     return tracker.synced_details().title();
   return std::string();
 }
 
 // Returns true if |db| has no content.
 bool IsDatabaseEmpty(leveldb::DB* db) {
   DCHECK(db);
   scoped_ptr<leveldb::Iterator> itr(db->NewIterator(leveldb::ReadOptions()));
@@ skipping 223 matching lines @@
       contents->file_metadata[i] = NULL;
     } else {
       PutFileMetadataDeletionToBatch(metadata->file_id(), batch);
     }
   }
   contents->file_metadata = referred_file_metadata.Pass();
 
   return SYNC_STATUS_OK;
 }
 
-template <typename Container, typename Key, typename Value>
-bool FindItem(const Container& container, const Key& key, Value* value) {
-  typename Container::const_iterator found = container.find(key);
-  if (found == container.end())
-    return false;
-  if (value)
-    *value = *found->second;
-  return true;
-}
-
-template <typename Container, typename Key>
-typename Container::mapped_type FindAndEraseItem(Container* container,
-                                                 const Key& key) {
-  typedef typename Container::mapped_type Value;
-  typename Container::iterator found = container->find(key);
-  if (found == container->end())
-    return Value();
-
-  Value result = found->second;
-  container->erase(found);
-  return result;
-}
-
 void RunSoon(const tracked_objects::Location& from_here,
              const base::Closure& closure) {
   base::MessageLoopProxy::current()->PostTask(from_here, closure);
 }
 
 bool HasInvalidTitle(const std::string& title) {
   return title.empty() ||
       title.find('/') != std::string::npos ||
       title.find('\\') != std::string::npos;
 }
 
+void MarkTrackerSetDirty(const TrackerIDSet& trackers,
+                         MetadataDatabaseIndex* index,
+                         leveldb::WriteBatch* batch) {
+  for (TrackerIDSet::const_iterator itr = trackers.begin();
+       itr != trackers.end(); ++itr) {
+    scoped_ptr<FileTracker> tracker =
+        CloneFileTracker(index->GetFileTracker(*itr));
+    if (tracker->dirty())
+      continue;
+    tracker->set_dirty(true);
+    PutFileTrackerToBatch(*tracker, batch);
+    index->StoreFileTracker(tracker.Pass());
+  }
+}
+
+void MarkTrackersDirtyByPath(int64 parent_tracker_id,
+                             const std::string& title,
+                             MetadataDatabaseIndex* index,
+                             leveldb::WriteBatch* batch) {
+  if (parent_tracker_id == kInvalidTrackerID || title.empty())
+    return;
+  MarkTrackerSetDirty(
+      index->GetFileTrackerIDsByParentAndTitle(parent_tracker_id, title),
+      index, batch);
+}
+
+void MarkTrackersDirtyByFileID(const std::string& file_id,
+                               MetadataDatabaseIndex* index,
+                               leveldb::WriteBatch* batch) {
+  MarkTrackerSetDirty(index->GetFileTrackerIDsByFileID(file_id),
+                      index, batch);
+}
+
+void MarkTrackersDirtyRecursively(int64 root_tracker_id,
+                                  MetadataDatabaseIndex* index,
+                                  leveldb::WriteBatch* batch) {
+  std::vector<int64> stack;
+  stack.push_back(root_tracker_id);
+  while (!stack.empty()) {
+    int64 tracker_id = stack.back();
+    stack.pop_back();
+    AppendContents(index->GetFileTrackerIDsByParent(tracker_id), &stack);
+
+    scoped_ptr<FileTracker> tracker =
+        CloneFileTracker(index->GetFileTracker(tracker_id));
+    tracker->set_dirty(true);
+
+    PutFileTrackerToBatch(*tracker, batch);
+    index->StoreFileTracker(tracker.Pass());
+  }
+}
+
+void RemoveAllDescendantTrackers(int64 root_tracker_id,
+                                 MetadataDatabaseIndex* index,
+                                 leveldb::WriteBatch* batch) {
+  std::vector<int64> pending_trackers;
+  AppendContents(index->GetFileTrackerIDsByParent(root_tracker_id),
+                 &pending_trackers);
+
+  std::vector<int64> to_be_removed;
+
+  // List trackers to remove.
+  while (!pending_trackers.empty()) {
+    int64 tracker_id = pending_trackers.back();
+    pending_trackers.pop_back();
+    AppendContents(index->GetFileTrackerIDsByParent(tracker_id),
+                   &pending_trackers);
+    to_be_removed.push_back(tracker_id);
+  }
+
+  // Remove trackers in the reversed order.
+  base::hash_set<std::string> affected_file_ids;
+  for (std::vector<int64>::reverse_iterator itr = to_be_removed.rbegin();
+       itr != to_be_removed.rend(); ++itr) {
+    const FileTracker* trackers = index->GetFileTracker(*itr);
+    affected_file_ids.insert(trackers->file_id());
+    PutFileTrackerDeletionToBatch(*itr, batch);
+    index->RemoveFileTracker(*itr);
+  }
+
+  for (base::hash_set<std::string>::iterator itr = affected_file_ids.begin();
+       itr != affected_file_ids.end(); ++itr) {
+    TrackerIDSet trackers = index->GetFileTrackerIDsByFileID(*itr);
+    if (trackers.empty()) {
+      // Remove metadata that no longer has any tracker.
+      PutFileMetadataDeletionToBatch(*itr, batch);
+      index->RemoveFileMetadata(*itr);
+    } else {
+      MarkTrackerSetDirty(trackers, index, batch);
+    }
+  }
+}
+
+const FileTracker* FilterFileTrackersByParent(
+    const MetadataDatabaseIndex& index,
+    const TrackerIDSet& trackers,
+    int64 parent_tracker_id) {
+  for (TrackerIDSet::const_iterator itr = trackers.begin();
+       itr != trackers.end(); ++itr) {
+    const FileTracker* tracker = index.GetFileTracker(*itr);
+    if (!tracker) {
+      NOTREACHED();
+      continue;
+    }
+
+    if (tracker->parent_tracker_id() == parent_tracker_id)
+      return tracker;
+  }
+  return NULL;
+}
+
+const FileTracker* FilterFileTrackersByParentAndTitle(
+    const MetadataDatabaseIndex& index,
+    const TrackerIDSet& trackers,
+    int64 parent_tracker_id,
+    const std::string& title) {
+  const FileTracker* result = NULL;
+
+  for (TrackerIDSet::const_iterator itr = trackers.begin();
+       itr != trackers.end(); ++itr) {
+    const FileTracker* tracker = index.GetFileTracker(*itr);
+    if (!tracker) {
+      NOTREACHED();
+      continue;
+    }
+
+    if (tracker->parent_tracker_id() != parent_tracker_id)
+      continue;
+
+    if (tracker->has_synced_details() &&
+        tracker->synced_details().title() != title)
+      continue;
+
+    // Prioritize trackers that has |synced_details|.
+    if (!result || !tracker->has_synced_details())
+      result = tracker;
+  }
+
+  return result;
+}
+
+const FileTracker* FilterFileTrackersByFileID(
+    const MetadataDatabaseIndex& index,
+    const TrackerIDSet& trackers,
+    const std::string& file_id) {
+  for (TrackerIDSet::const_iterator itr = trackers.begin();
+       itr != trackers.end(); ++itr) {
+    const FileTracker* tracker = index.GetFileTracker(*itr);
+    if (!tracker) {
+      NOTREACHED();
+      continue;
+    }
+
+    if (tracker->file_id() == file_id)
+      return tracker;
+  }
+
+  return NULL;
+}
+
+enum DirtyingOption {
+  MARK_NOTHING_DIRTY = 0,
+  MARK_ITSELF_DIRTY = 1 << 0,
+  MARK_SAME_FILE_ID_TRACKERS_DIRTY = 1 << 1,
+  MARK_SAME_PATH_TRACKERS_DIRTY = 1 << 2,
+};
+
+void ActivateFileTracker(int64 tracker_id,
+                         int dirtying_options,
+                         MetadataDatabaseIndex* index,
+                         leveldb::WriteBatch* batch) {
+  DCHECK(dirtying_options == MARK_NOTHING_DIRTY ||
+         dirtying_options == MARK_ITSELF_DIRTY);
+
+  scoped_ptr<FileTracker> tracker =
+      CloneFileTracker(index->GetFileTracker(tracker_id));
+  tracker->set_active(true);
+  if (dirtying_options & MARK_ITSELF_DIRTY) {
+    tracker->set_dirty(true);
+    tracker->set_needs_folder_listing(
+        tracker->has_synced_details() &&
+        tracker->synced_details().file_kind() == FILE_KIND_FOLDER);
+  } else {
+    tracker->set_dirty(false);
+    tracker->set_needs_folder_listing(false);
+  }
+
+  PutFileTrackerToBatch(*tracker, batch);
+  index->StoreFileTracker(tracker.Pass());
+}
+
+void DeactivateFileTracker(int64 tracker_id,
+                           int dirtying_options,
+                           MetadataDatabaseIndex* index,
+                           leveldb::WriteBatch* batch) {
+  RemoveAllDescendantTrackers(tracker_id, index, batch);
+
+  scoped_ptr<FileTracker> tracker =
+      CloneFileTracker(index->GetFileTracker(tracker_id));
+
+  if (dirtying_options & MARK_SAME_FILE_ID_TRACKERS_DIRTY)
+    MarkTrackersDirtyByFileID(tracker->file_id(), index, batch);
+  if (dirtying_options & MARK_SAME_PATH_TRACKERS_DIRTY) {
+    MarkTrackersDirtyByPath(tracker->parent_tracker_id(),
+                            GetTrackerTitle(*tracker),
+                            index, batch);
+  }
+
+  tracker->set_dirty(dirtying_options & MARK_ITSELF_DIRTY);
+  tracker->set_active(false);
+  PutFileTrackerToBatch(*tracker, batch);
+  index->StoreFileTracker(tracker.Pass());
+}
+
+void RemoveFileTracker(int64 tracker_id,
+                       int dirtying_options,
+                       MetadataDatabaseIndex* index,
+                       leveldb::WriteBatch* batch) {
+  DCHECK(!(dirtying_options & MARK_ITSELF_DIRTY));
+
+  const FileTracker* tracker = index->GetFileTracker(tracker_id);
+  if (!tracker)
+    return;
+
+  std::string file_id = tracker->file_id();
+  int64 parent_tracker_id = tracker->parent_tracker_id();
+  std::string title = GetTrackerTitle(*tracker);
+
+  RemoveAllDescendantTrackers(tracker_id, index, batch);
+  PutFileTrackerDeletionToBatch(tracker_id, batch);
+  index->RemoveFileTracker(tracker_id);
+
+  if (dirtying_options & MARK_SAME_FILE_ID_TRACKERS_DIRTY)
+    MarkTrackersDirtyByFileID(file_id, index, batch);
+  if (dirtying_options & MARK_SAME_PATH_TRACKERS_DIRTY)
+    MarkTrackersDirtyByPath(parent_tracker_id, title, index, batch);
+
+  if (index->GetFileTrackerIDsByFileID(file_id).empty()) {
+    PutFileMetadataDeletionToBatch(file_id, batch);
+    index->RemoveFileMetadata(file_id);
+  }
+}
+
 }  // namespace
 
 DatabaseContents::DatabaseContents() {}
 DatabaseContents::~DatabaseContents() {}
 
-bool MetadataDatabase::DirtyTrackerComparator::operator()(
-    const FileTracker* left,
-    const FileTracker* right) const {
-  return left->tracker_id() < right->tracker_id();
-}
-
 // static
 void MetadataDatabase::Create(base::SequencedTaskRunner* task_runner,
                               const base::FilePath& database_path,
                               leveldb::Env* env_override,
                               const CreateCallback& callback) {
   task_runner->PostTask(FROM_HERE, base::Bind(
       &CreateOnTaskRunner,
       base::MessageLoopProxy::current(),
       make_scoped_refptr(task_runner),
       database_path, env_override, callback));
@@ skipping 55 matching lines @@
 bool MetadataDatabase::HasSyncRoot() const {
   return service_metadata_->has_sync_root_tracker_id() &&
       !!service_metadata_->sync_root_tracker_id();
 }
 
 void MetadataDatabase::PopulateInitialData(
     int64 largest_change_id,
     const google_apis::FileResource& sync_root_folder,
     const ScopedVector<google_apis::FileResource>& app_root_folders,
     const SyncStatusCallback& callback) {
-  DCHECK(tracker_by_id_.empty());
-  DCHECK(metadata_by_id_.empty());
+  DCHECK(index_->tracker_by_id_.empty());
+  DCHECK(index_->metadata_by_id_.empty());
 
   scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
   service_metadata_->set_largest_change_id(largest_change_id);
   UpdateLargestKnownChangeID(largest_change_id);
 
   AttachSyncRoot(sync_root_folder, batch.get());
   for (size_t i = 0; i < app_root_folders.size(); ++i)
     AttachInitialAppRoot(*app_root_folders[i], batch.get());
 
   WriteToDatabase(batch.Pass(), callback);
 }
 
 bool MetadataDatabase::IsAppEnabled(const std::string& app_id) const {
-  FileTracker tracker;
-  if (!FindAppRootTracker(app_id, &tracker))
+  int64 tracker_id = index_->GetAppRootTracker(app_id);
+  if (tracker_id == kInvalidTrackerID)
     return false;
-  return tracker.tracker_kind() == TRACKER_KIND_APP_ROOT;
+
+  const FileTracker* tracker = index_->GetFileTracker(tracker_id);
+  return tracker && tracker->tracker_kind() == TRACKER_KIND_APP_ROOT;
 }
 
 void MetadataDatabase::RegisterApp(const std::string& app_id,
                                    const std::string& folder_id,
                                    const SyncStatusCallback& callback) {
-  if (FindAppRootTracker(app_id, NULL)) {
+  if (index_->GetAppRootTracker(app_id)) {
     // The app-root is already registered.
     RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
     return;
   }
 
-  TrackerIDSet trackers;
-  if (!FindTrackersByFileID(folder_id, &trackers) || trackers.has_active()) {
+  TrackerIDSet trackers = index_->GetFileTrackerIDsByFileID(folder_id);
+  if (trackers.empty()) {
+    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
+    return;
+  }
+
+  if (trackers.has_active()) {
     // The folder is tracked by another tracker.
     util::Log(logging::LOG_WARNING, FROM_HERE,
               "Failed to register App for %s", app_id.c_str());
     RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_HAS_CONFLICT));
     return;
   }
 
   int64 sync_root_tracker_id = service_metadata_->sync_root_tracker_id();
   if (!sync_root_tracker_id) {
     util::Log(logging::LOG_WARNING, FROM_HERE,
               "Sync-root needs to be set up before registering app-root");
     RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
     return;
   }
 
-  // Make this tracker an app-root tracker.
-  const FileTracker* app_root_tracker = NULL;
-  for (TrackerIDSet::iterator itr = trackers.begin();
-       itr != trackers.end(); ++itr) {
-    const FileTracker* tracker = tracker_by_id_.get(*itr);
-    if (!tracker) {
-      NOTREACHED();
-      continue;
-    }
-
-    if (tracker->parent_tracker_id() == sync_root_tracker_id)
-      app_root_tracker = tracker;
-  }
-
-  if (!app_root_tracker) {
+  scoped_ptr<FileTracker> tracker =
+      CloneFileTracker(FilterFileTrackersByParent(*index_, trackers,
+                                                  sync_root_tracker_id));
+  if (!tracker) {
     RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
     return;
   }
 
   scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
-  RegisterTrackerAsAppRoot(app_id, app_root_tracker->tracker_id(), batch.get());
+  tracker->set_app_id(app_id);
+  tracker->set_tracker_kind(TRACKER_KIND_APP_ROOT);
+  tracker->set_active(true);
+  tracker->set_needs_folder_listing(true);
+  tracker->set_dirty(true);
+
+  PutFileTrackerToBatch(*tracker, batch.get());
+  index_->StoreFileTracker(tracker.Pass());
   WriteToDatabase(batch.Pass(), callback);
 }
 
 void MetadataDatabase::DisableApp(const std::string& app_id,
                                   const SyncStatusCallback& callback) {
-  FileTracker tracker;
-  if (!FindAppRootTracker(app_id, &tracker)) {
+  int64 tracker_id = index_->GetAppRootTracker(app_id);
+  scoped_ptr<FileTracker> tracker =
+      CloneFileTracker(index_->GetFileTracker(tracker_id));
+  if (!tracker) {
     RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
     return;
   }
 
-  if (tracker.tracker_kind() == TRACKER_KIND_DISABLED_APP_ROOT) {
+  if (tracker->tracker_kind() == TRACKER_KIND_DISABLED_APP_ROOT) {
+    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
+    return;
+  }
+
+  DCHECK_EQ(TRACKER_KIND_APP_ROOT, tracker->tracker_kind());
+  DCHECK(tracker->active());
+
+  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
+
+  // Keep the app-root tracker active (but change the tracker_kind) so that
+  // other conflicting trackers won't become active.
+  tracker->set_tracker_kind(TRACKER_KIND_DISABLED_APP_ROOT);
+
+  PutFileTrackerToBatch(*tracker, batch.get());
+  index_->StoreFileTracker(tracker.Pass());
+  WriteToDatabase(batch.Pass(), callback);
+}
+
+void MetadataDatabase::EnableApp(const std::string& app_id,
+                                 const SyncStatusCallback& callback) {
+  int64 tracker_id = index_->GetAppRootTracker(app_id);
+  scoped_ptr<FileTracker> tracker =
+      CloneFileTracker(index_->GetFileTracker(tracker_id));
+  if (!tracker) {
+    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
+    return;
+  }
+
+  if (tracker->tracker_kind() == TRACKER_KIND_APP_ROOT) {
+    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
+    return;
+  }
+
+  DCHECK_EQ(TRACKER_KIND_DISABLED_APP_ROOT, tracker->tracker_kind());
+  DCHECK(tracker->active());
+
+  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
+
+  tracker->set_tracker_kind(TRACKER_KIND_APP_ROOT);
+  PutFileTrackerToBatch(*tracker, batch.get());
+  index_->StoreFileTracker(tracker.Pass());
+
+  MarkTrackersDirtyRecursively(tracker_id, index_.get(), batch.get());
+  WriteToDatabase(batch.Pass(), callback);
+}
+
+void MetadataDatabase::UnregisterApp(const std::string& app_id,
+                                     const SyncStatusCallback& callback) {
+  int64 tracker_id = index_->GetAppRootTracker(app_id);
+  scoped_ptr<FileTracker> tracker =
+      CloneFileTracker(index_->GetFileTracker(tracker_id));
+  if (!tracker || tracker->tracker_kind() == TRACKER_KIND_REGULAR) {
     RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
     return;
   }
 
   scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
-  MakeAppRootDisabled(tracker.tracker_id(), batch.get());
-  WriteToDatabase(batch.Pass(), callback);
-}
+  RemoveAllDescendantTrackers(tracker_id, index_.get(), batch.get());
 
-void MetadataDatabase::EnableApp(const std::string& app_id,
-                                 const SyncStatusCallback& callback) {
-  FileTracker tracker;
-  if (!FindAppRootTracker(app_id, &tracker) ||
-      tracker.tracker_kind() == TRACKER_KIND_REGULAR) {
-    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
-    return;
-  }
+  tracker->clear_app_id();
+  tracker->set_tracker_kind(TRACKER_KIND_REGULAR);
+  tracker->set_active(false);
+  tracker->set_dirty(true);
 
-  if (tracker.tracker_kind() == TRACKER_KIND_APP_ROOT) {
-    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
-    return;
-  }
-
-  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
-  MakeAppRootEnabled(tracker.tracker_id(), batch.get());
-  WriteToDatabase(batch.Pass(), callback);
-}
-
-void MetadataDatabase::UnregisterApp(const std::string& app_id,
-                                     const SyncStatusCallback& callback) {
-  FileTracker tracker;
-  if (!FindAppRootTracker(app_id, &tracker) ||
-      tracker.tracker_kind() == TRACKER_KIND_REGULAR) {
-    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
-    return;
-  }
-
-  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
-  UnregisterTrackerAsAppRoot(app_id, batch.get());
+  PutFileTrackerToBatch(*tracker, batch.get());
+  index_->StoreFileTracker(tracker.Pass());
   WriteToDatabase(batch.Pass(), callback);
 }
 
 bool MetadataDatabase::FindAppRootTracker(const std::string& app_id,
-                                          FileTracker* tracker) const {
-  TrackerIDByAppID::const_iterator found = app_root_by_app_id_.find(app_id);
-  if (found == app_root_by_app_id_.end())
+                                          FileTracker* tracker_out) const {
+  int64 app_root_tracker_id = index_->GetAppRootTracker(app_id);
+  if (!app_root_tracker_id)
     return false;
 
-  if (tracker)
-    *tracker = *tracker_by_id_.get(found->second);
+  if (tracker_out) {
+    const FileTracker* app_root_tracker =
+        index_->GetFileTracker(app_root_tracker_id);
+    if (!app_root_tracker) {
+      NOTREACHED();
+      return false;
+    }
+    *tracker_out = *app_root_tracker;
+  }
   return true;
 }
 
 bool MetadataDatabase::FindFileByFileID(const std::string& file_id,
-                                        FileMetadata* file) const {
-  return FindItem(metadata_by_id_, file_id, file);
+                                        FileMetadata* metadata_out) const {
+  const FileMetadata* metadata = index_->GetFileMetadata(file_id);
+  if (!metadata)
+    return false;
+  if (metadata_out)
+    *metadata_out = *metadata;
+  return true;
 }
 
 bool MetadataDatabase::FindTrackersByFileID(const std::string& file_id,
-                                            TrackerIDSet* trackers) const {
-  TrackerIDsByFileID::const_iterator found = trackers_by_file_id_.find(file_id);
-  if (found == trackers_by_file_id_.end())
+                                            TrackerIDSet* trackers_out) const {
+  TrackerIDSet trackers = index_->GetFileTrackerIDsByFileID(file_id);
+  if (trackers.empty())
     return false;
-  if (trackers)
-    *trackers = found->second;
+
+  if (trackers_out)
+    std::swap(trackers, *trackers_out);
   return true;
 }
 
 bool MetadataDatabase::FindTrackersByParentAndTitle(
     int64 parent_tracker_id,
     const std::string& title,
-    TrackerIDSet* trackers) const {
-  TrackerIDsByParentAndTitle::const_iterator found_by_parent =
-      trackers_by_parent_and_title_.find(parent_tracker_id);
-  if (found_by_parent == trackers_by_parent_and_title_.end())
+    TrackerIDSet* trackers_out) const {
+  TrackerIDSet trackers =
+      index_->GetFileTrackerIDsByParentAndTitle(parent_tracker_id, title);
+  if (trackers.empty())
     return false;
 
-  TrackerIDsByTitle::const_iterator found_by_title =
-      found_by_parent->second.find(title);
-  if (found_by_title == found_by_parent->second.end())
-    return false;
-
-  if (trackers)
-    *trackers = found_by_title->second;
+  if (trackers_out)
+    std::swap(trackers, *trackers_out);
   return true;
 }
 
 bool MetadataDatabase::FindTrackerByTrackerID(int64 tracker_id,
-                                              FileTracker* tracker) const {
-  return FindItem(tracker_by_id_, tracker_id, tracker);
+                                              FileTracker* tracker_out) const {
+  const FileTracker* tracker = index_->GetFileTracker(tracker_id);
+  if (!tracker)
+    return false;
+  if (tracker_out)
+    *tracker_out = *tracker;
+  return true;
 }
 
 bool MetadataDatabase::BuildPathForTracker(int64 tracker_id,
                                            base::FilePath* path) const {
   FileTracker current;
   if (!FindTrackerByTrackerID(tracker_id, &current) || !current.active())
     return false;
 
   std::vector<base::FilePath> components;
   while (!IsAppRoot(current)) {
@@ skipping 49 matching lines @@
 
   for (size_t i = 0; i < components.size(); ++i) {
     const std::string title = base::FilePath(components[i]).AsUTF8Unsafe();
     TrackerIDSet trackers;
     if (!FindTrackersByParentAndTitle(
             tracker_out->tracker_id(), title, &trackers) ||
         !trackers.has_active()) {
       return true;
     }
 
-    TrackerByID::const_iterator found =
-        tracker_by_id_.find(trackers.active_tracker());
-    if (found == tracker_by_id_.end()) {
-      NOTREACHED();
-      return false;
-    }
-
-    FileTracker* tracker = found->second;
+    const FileTracker* tracker =
+        index_->GetFileTracker(trackers.active_tracker());;
 
     DCHECK(tracker->has_synced_details());
     const FileDetails& details = tracker->synced_details();
     if (details.file_kind() != FILE_KIND_FOLDER && i != components.size() - 1) {
       // This non-last component indicates file. Give up search.
       return true;
     }
 
     *tracker_out = *tracker;
     *path_out = path_out->Append(components[i]);
   }
 
   return true;
 }
 
 void MetadataDatabase::UpdateByChangeList(
     int64 largest_change_id,
     ScopedVector<google_apis::ChangeResource> changes,
     const SyncStatusCallback& callback) {
   DCHECK_LE(service_metadata_->largest_change_id(), largest_change_id);
 
   scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
 
-  for (ScopedVector<google_apis::ChangeResource>::const_iterator itr =
-           changes.begin();
-       itr != changes.end();
-       ++itr) {
-    const google_apis::ChangeResource& change = **itr;
+  for (size_t i = 0; i < changes.size(); ++i) {
+    const google_apis::ChangeResource& change = *changes[i];
     if (HasNewerFileMetadata(change.file_id(), change.change_id()))
       continue;
 
     scoped_ptr<FileMetadata> metadata(
         CreateFileMetadataFromChangeResource(change));
     UpdateByFileMetadata(FROM_HERE, metadata.Pass(),
                          UPDATE_TRACKER_FOR_UNSYNCED_FILE,
                          batch.get());
   }
 
@@ skipping 57 matching lines @@
                          UPDATE_TRACKER_FOR_UNSYNCED_FILE,
                          batch.get());
   }
   WriteToDatabase(batch.Pass(), callback);
 }
 
 void MetadataDatabase::ReplaceActiveTrackerWithNewResource(
     int64 parent_tracker_id,
     const google_apis::FileResource& resource,
     const SyncStatusCallback& callback) {
+  DCHECK(index_->GetFileTracker(parent_tracker_id));
+  DCHECK(!index_->GetFileMetadata(resource.file_id()));
+
   scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
-
-  DCHECK(!ContainsKey(metadata_by_id_, resource.file_id()));
   UpdateByFileMetadata(
       FROM_HERE,
       CreateFileMetadataFromFileResource(GetLargestKnownChangeID(), resource),
       UPDATE_TRACKER_FOR_SYNCED_FILE,
       batch.get());
-  DCHECK(ContainsKey(metadata_by_id_, resource.file_id()));
 
-  ForceActivateTrackerByPath(
-      parent_tracker_id, resource.title(), resource.file_id(), batch.get());
+  DCHECK(index_->GetFileMetadata(resource.file_id()));
+  DCHECK(!index_->GetFileTrackerIDsByFileID(resource.file_id()).has_active());
 
+  TrackerIDSet same_path_trackers =
+      index_->GetFileTrackerIDsByParentAndTitle(
+          parent_tracker_id, resource.title());
+  const FileTracker* to_be_activated =
+      FilterFileTrackersByFileID(*index_, same_path_trackers,
+                                 resource.file_id());
+  if (!to_be_activated) {
+    NOTREACHED();
+    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_FAILED));
+    return;
+  }
+
+  int64 tracker_id = to_be_activated->tracker_id();
+  if (same_path_trackers.has_active()) {
+    DeactivateFileTracker(same_path_trackers.active_tracker(),
+                          MARK_ITSELF_DIRTY |
+                          MARK_SAME_FILE_ID_TRACKERS_DIRTY,
+                          index_.get(), batch.get());
+  }
+
+  ActivateFileTracker(tracker_id, MARK_NOTHING_DIRTY,
+                      index_.get(), batch.get());
   WriteToDatabase(batch.Pass(), callback);
 }
 
 void MetadataDatabase::PopulateFolderByChildList(
     const std::string& folder_id,
     const FileIDList& child_file_ids,
     const SyncStatusCallback& callback) {
-  TrackerIDSet trackers;
-  if (!FindTrackersByFileID(folder_id, &trackers) ||
-      !trackers.has_active()) {
+  TrackerIDSet trackers = index_->GetFileTrackerIDsByFileID(folder_id);
+  if (!trackers.has_active()) {
     // It's OK that there is no folder to populate its children.
     // Inactive folders should ignore their contents updates.
     RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
     return;
   }
 
-  FileTracker* folder_tracker = tracker_by_id_.get(trackers.active_tracker());
-  DCHECK(folder_tracker);
-  std::set<std::string> children(child_file_ids.begin(), child_file_ids.end());
+  scoped_ptr<FileTracker> folder_tracker =
+      CloneFileTracker(index_->GetFileTracker(trackers.active_tracker()));
+  if (!folder_tracker) {
+    NOTREACHED();
+    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_FAILED));
+    return;
+  }
 
-  std::vector<int64> known_children;
-  PushChildTrackersToContainer(trackers_by_parent_and_title_,
-                               folder_tracker->tracker_id(),
-                               std::back_inserter(known_children));
-  for (std::vector<int64>::iterator itr = known_children.begin();
-       itr != known_children.end(); ++itr)
-    children.erase(tracker_by_id_.get(*itr)->file_id());
+  base::hash_set<std::string> children(child_file_ids.begin(),
+                                       child_file_ids.end());
+
+  std::vector<int64> known_children =
+      index_->GetFileTrackerIDsByParent(folder_tracker->tracker_id());
+  for (size_t i = 0; i < known_children.size(); ++i) {
+    const FileTracker* tracker = index_->GetFileTracker(known_children[i]);
+    if (!tracker) {
+      NOTREACHED();
+      continue;
+    }
+    children.erase(tracker->file_id());
+  }
 
   scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
-  for (FileIDList::const_iterator itr = child_file_ids.begin();
-       itr != child_file_ids.end(); ++itr)
+  for (base::hash_set<std::string>::const_iterator itr = children.begin();
+       itr != children.end(); ++itr)
     CreateTrackerForParentAndFileID(*folder_tracker, *itr, batch.get());
   folder_tracker->set_needs_folder_listing(false);
   if (folder_tracker->dirty() && !ShouldKeepDirty(*folder_tracker))
-    ClearDirty(folder_tracker, NULL);
+    folder_tracker->set_dirty(false);
   PutFileTrackerToBatch(*folder_tracker, batch.get());
+  index_->StoreFileTracker(folder_tracker.Pass());
 
   WriteToDatabase(batch.Pass(), callback);
 }
 
 void MetadataDatabase::UpdateTracker(int64 tracker_id,
                                      const FileDetails& updated_details,
                                      const SyncStatusCallback& callback) {
-  TrackerByID::iterator found = tracker_by_id_.find(tracker_id);
-  if (found == tracker_by_id_.end()) {
+  const FileTracker* tracker = index_->GetFileTracker(tracker_id);
+  if (!tracker) {
     RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
     return;
   }
-
-  FileTracker* tracker = found->second;
   DCHECK(tracker);
 
   scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
 
+  // Check if the tracker is to be deleted.
   if (updated_details.missing()) {
-    MetadataByID::iterator found = metadata_by_id_.find(tracker->file_id());
-    if (found == metadata_by_id_.end() || found->second->details().missing()) {
+    const FileMetadata* metadata = index_->GetFileMetadata(tracker->file_id());
+    if (!metadata || metadata->details().missing()) {
       // Both the tracker and metadata have the missing flag, now it's safe to
       // delete the |tracker|.
-      RemoveTracker(tracker->tracker_id(), batch.get());
+      RemoveFileTracker(tracker_id,
+                        MARK_SAME_FILE_ID_TRACKERS_DIRTY |
+                        MARK_SAME_PATH_TRACKERS_DIRTY,
+                        index_.get(), batch.get());
       WriteToDatabase(batch.Pass(), callback);
       return;
     }
   }
 
   // Sync-root deletion should be handled separately by SyncEngine.
   DCHECK(tracker_id != GetSyncRootTrackerID() ||
          (tracker->has_synced_details() &&
           tracker->synced_details().title() == updated_details.title() &&
           !updated_details.missing()));
 
   if (tracker_id != GetSyncRootTrackerID()) {
     // Check if the tracker's parent is still in |parent_tracker_ids|.
     // If not, there should exist another tracker for the new parent, so delete
     // old tracker.
-    DCHECK(ContainsKey(tracker_by_id_, tracker->parent_tracker_id()));
-    FileTracker* parent_tracker =
-        tracker_by_id_.get(tracker->parent_tracker_id());
+    const FileTracker* parent_tracker =
+        index_->GetFileTracker(tracker->parent_tracker_id());
+    DCHECK(parent_tracker);
+
     if (!HasFileAsParent(updated_details, parent_tracker->file_id())) {
-      RemoveTracker(tracker->tracker_id(), batch.get());
+      RemoveFileTracker(tracker->tracker_id(),
+                        MARK_SAME_PATH_TRACKERS_DIRTY,
+                        index_.get(), batch.get());
       WriteToDatabase(batch.Pass(), callback);
       return;
     }
 
     if (tracker->has_synced_details()) {
       // Check if the tracker was retitled.  If it was, there should exist
-      // another tracker for the new title, so delete old tracker.
+      // another tracker for the new title, so delete the tracker being updated.
       if (tracker->synced_details().title() != updated_details.title()) {
-        RemoveTracker(tracker->tracker_id(), batch.get());
+        RemoveFileTracker(tracker->tracker_id(),
+                          MARK_SAME_FILE_ID_TRACKERS_DIRTY,
+                          index_.get(), batch.get());
         WriteToDatabase(batch.Pass(), callback);
         return;
       }
     } else {
-      int64 parent_tracker_id = parent_tracker->tracker_id();
-      const std::string& title = updated_details.title();
-      TrackerIDSet* trackers =
-          &trackers_by_parent_and_title_[parent_tracker_id][title];
-
-      for (TrackerIDSet::iterator itr = trackers->begin();
-           itr != trackers->end(); ++itr) {
-        FileTracker* same_path_tracker = tracker_by_id_.get(*itr);
-        if (!same_path_tracker) {
-          NOTREACHED();
-          continue;
-        }
-
-        if (same_path_tracker->file_id() == tracker->file_id()) {
-          RemoveTracker(tracker->tracker_id(), batch.get());
-          WriteToDatabase(batch.Pass(), callback);
-          return;
-        }
+      // Check if any other tracker exists has the same parent, title and
+      // file_id to the updated tracker.  If it exists, delete the tracker being
+      // updated.
+      if (FilterFileTrackersByFileID(
+              *index_,
+              index_->GetFileTrackerIDsByParentAndTitle(
+                  parent_tracker->tracker_id(),
+                  updated_details.title()),
+              tracker->file_id())) {
+        RemoveFileTracker(tracker->tracker_id(),
+                          MARK_NOTHING_DIRTY,
+                          index_.get(), batch.get());
+        WriteToDatabase(batch.Pass(), callback);
+        return;
       }
-
-      trackers_by_parent_and_title_[parent_tracker_id][std::string()].Erase(
-          tracker_id);
-      trackers->Insert(*tracker);
     }
   }
 
-  *tracker->mutable_synced_details() = updated_details;
+  scoped_ptr<FileTracker> updated_tracker = CloneFileTracker(tracker);
+  *updated_tracker->mutable_synced_details() = updated_details;
 
   // Activate the tracker if:
   //   - There is no active tracker that tracks |tracker->file_id()|.
   //   - There is no active tracker that has the same |parent| and |title|.
-  if (!tracker->active() && CanActivateTracker(*tracker))
-    MakeTrackerActive(tracker->tracker_id(), batch.get());
-  if (tracker->dirty() && !ShouldKeepDirty(*tracker))
-    ClearDirty(tracker, NULL);
+  if (!tracker->active() && CanActivateTracker(*tracker)) {
+    updated_tracker->set_active(true);
+    updated_tracker->set_dirty(true);
+    updated_tracker->set_needs_folder_listing(
+        tracker->synced_details().file_kind() == FILE_KIND_FOLDER);
+  } else if (tracker->dirty() && !ShouldKeepDirty(*tracker)) {
+    updated_tracker->set_dirty(false);
+  }
   PutFileTrackerToBatch(*tracker, batch.get());
+  index_->StoreFileTracker(updated_tracker.Pass());
 
   WriteToDatabase(batch.Pass(), callback);
 }
 
 MetadataDatabase::ActivationStatus MetadataDatabase::TryActivateTracker(
     int64 parent_tracker_id,
     const std::string& file_id,
     const SyncStatusCallback& callback) {
-  DCHECK(ContainsKey(tracker_by_id_, parent_tracker_id));
-  DCHECK(ContainsKey(metadata_by_id_, file_id));
+  DCHECK(index_->GetFileTracker(parent_tracker_id));
 
-  FileMetadata metadata;
-  if (!FindFileByFileID(file_id, &metadata)) {
+  const FileMetadata* metadata = index_->GetFileMetadata(file_id);
+  if (!metadata) {
     NOTREACHED();
     RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_FAILED));
     return ACTIVATION_PENDING;
   }
-  std::string title = metadata.details().title();
+  std::string title = metadata->details().title();
   DCHECK(!HasInvalidTitle(title));
 
-  TrackerIDSet same_file_id;
-  FindTrackersByFileID(file_id, &same_file_id);
-
-  // Pick up the tracker to be activated, that has:
-  //  - |parent_tarcker_id| as the parent, and
-  //  - |file_id| as the tracker's |file_id|.
-  FileTracker* tracker = NULL;
-  for (TrackerIDSet::iterator itr = same_file_id.begin();
-       itr != same_file_id.end(); ++itr) {
-    FileTracker* candidate = tracker_by_id_.get(*itr);
-    if (!candidate) {
-      NOTREACHED();
-      continue;
-    }
-
-    if (candidate->parent_tracker_id() != parent_tracker_id)
-      continue;
-
-    if (candidate->has_synced_details() &&
-        candidate->synced_details().title() != title)
-      continue;
-    tracker = candidate;
-  }
-
-  DCHECK(tracker);
+  TrackerIDSet same_file_id_trackers =
+      index_->GetFileTrackerIDsByFileID(file_id);
+  scoped_ptr<FileTracker> tracker_to_be_activated =
+      CloneFileTracker(FilterFileTrackersByParentAndTitle(
+          *index_, same_file_id_trackers,
+          parent_tracker_id, title));
+  DCHECK(tracker_to_be_activated);
 
   // Check if there is another active tracker that tracks |file_id|.
   // This can happen when the tracked file has multiple parents.
   // In this case, report the failure to the caller.
-  if (!tracker->active() && same_file_id.has_active())
+  if (!tracker_to_be_activated->active() && same_file_id_trackers.has_active())
     return ACTIVATION_FAILED_ANOTHER_ACTIVE_TRACKER;
 
   scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
 
-  if (!tracker->active()) {
-    // Check if there is another active tracker that has the same path to
-    // the tracker to be activated.
-    // Assuming the caller already overrides local file with newly added file,
-    // inactivate existing active tracker.
-    TrackerIDSet same_title;
-    FindTrackersByParentAndTitle(parent_tracker_id, title, &same_title);
-    if (same_title.has_active()) {
-      MakeTrackerInactive(same_title.active_tracker(), batch.get());
+  if (!tracker_to_be_activated->active()) {
+    // Check if there exists another active tracker that has the same path to
+    // the tracker.  If there is, deactivate it, assuming the caller already
+    // overrides local file with newly added file,
+    TrackerIDSet same_title_trackers =
+        index_->GetFileTrackerIDsByParentAndTitle(parent_tracker_id, title);
+    if (same_title_trackers.has_active()) {
+      RemoveAllDescendantTrackers(same_title_trackers.active_tracker(),
+                                  index_.get(), batch.get());
+
+      scoped_ptr<FileTracker> tracker_to_be_deactivated =
+          CloneFileTracker(index_->GetFileTracker(
+              same_title_trackers.active_tracker()));
+      if (tracker_to_be_deactivated) {
+        const std::string file_id = tracker_to_be_deactivated->file_id();
+        tracker_to_be_deactivated->set_active(false);
+        PutFileTrackerToBatch(*tracker_to_be_deactivated, batch.get());
+        index_->StoreFileTracker(tracker_to_be_deactivated.Pass());
+
+        MarkTrackersDirtyByFileID(file_id, index_.get(), batch.get());
+      } else {
+        NOTREACHED();
+      }
     }
   }
 
-  if (!tracker->has_synced_details() ||
-      tracker->synced_details().title() != title) {
-    trackers_by_parent_and_title_[parent_tracker_id]
-        [GetTrackerTitle(*tracker)].Erase(tracker->tracker_id());
-    trackers_by_parent_and_title_[parent_tracker_id][title]
-        .InsertInactiveTracker(tracker->tracker_id());
+  tracker_to_be_activated->set_dirty(false);
+  tracker_to_be_activated->set_active(true);
+  *tracker_to_be_activated->mutable_synced_details() = metadata->details();
+  if (tracker_to_be_activated->synced_details().file_kind() ==
+      FILE_KIND_FOLDER) {
+    tracker_to_be_activated->set_needs_folder_listing(true);
   }
-  *tracker->mutable_synced_details() = metadata.details();
+  tracker_to_be_activated->set_dirty(false);
 
-  MakeTrackerActive(tracker->tracker_id(), batch.get());
-  ClearDirty(tracker_by_id_.get(tracker->tracker_id()), batch.get());
+  PutFileTrackerToBatch(*tracker_to_be_activated, batch.get());
+  index_->StoreFileTracker(tracker_to_be_activated.Pass());
 
   WriteToDatabase(batch.Pass(), callback);
   return ACTIVATION_PENDING;
 }
 
 void MetadataDatabase::LowerTrackerPriority(int64 tracker_id) {
-  TrackerByID::const_iterator found = tracker_by_id_.find(tracker_id);
-  if (found == tracker_by_id_.end())
-    return;
-
-  FileTracker* tracker = found->second;
-  if (dirty_trackers_.erase(tracker))
-    low_priority_dirty_trackers_.insert(tracker);
+  index_->DemoteDirtyTracker(tracker_id);
 }
 
 void MetadataDatabase::PromoteLowerPriorityTrackersToNormal() {
-  if (dirty_trackers_.empty()) {
-    dirty_trackers_.swap(low_priority_dirty_trackers_);
-    return;
-  }
-  dirty_trackers_.insert(low_priority_dirty_trackers_.begin(),
-                         low_priority_dirty_trackers_.end());
-  low_priority_dirty_trackers_.clear();
+  index_->PromoteDemotedDirtyTrackers();
 }
 
 bool MetadataDatabase::GetNormalPriorityDirtyTracker(
-    FileTracker* tracker) const {
-  DirtyTrackers::const_iterator itr = dirty_trackers_.begin();
-  if (itr == dirty_trackers_.end())
+    FileTracker* tracker_out) const {
+  int64 dirty_tracker_id = index_->PickDirtyTracker();
+  if (!dirty_tracker_id)
     return false;
-  if (tracker)
-    *tracker = **itr;
+
+  if (tracker_out) {
+    const FileTracker* tracker =
+        index_->GetFileTracker(dirty_tracker_id);
+    if (!tracker) {
+      NOTREACHED();
+      return false;
+    }
+    *tracker_out = *tracker;
+  }
   return true;
 }
 
 bool MetadataDatabase::HasLowPriorityDirtyTracker() const {
-  return !low_priority_dirty_trackers_.empty();
+  return index_->HasDemotedDirtyTracker();
 }
 
 bool MetadataDatabase::HasDirtyTracker() const {
-  return CountDirtyTracker() != 0;
+  return index_->PickDirtyTracker() != kInvalidTrackerID;
 }
 
 size_t MetadataDatabase::CountDirtyTracker() const {
-  return dirty_trackers_.size() + low_priority_dirty_trackers_.size();
+  return index_->dirty_trackers_.size() +
+      index_->demoted_dirty_trackers_.size();
+}
+
+bool MetadataDatabase::GetMultiParentFileTrackers(std::string* file_id_out,
+                                                  TrackerIDSet* trackers_out) {
+  DCHECK(file_id_out);
+  DCHECK(trackers_out);
+
+  std::string file_id = index_->PickMultiTrackerFileID();
+  if (file_id.empty())
+    return false;
+
+  TrackerIDSet trackers = index_->GetFileTrackerIDsByFileID(file_id);
+  if (trackers.size() <= 1) {
+    NOTREACHED();
+    return false;
+  }
+
+  *file_id_out = file_id;
+  std::swap(*trackers_out, trackers);
+  return true;
 }
 
 size_t MetadataDatabase::CountFileMetadata() const {
-  return metadata_by_id_.size();
+  return index_->metadata_by_id_.size();
 }
 
 size_t MetadataDatabase::CountFileTracker() const {
-  return tracker_by_id_.size();
+  return index_->tracker_by_id_.size();
 }
 
-bool MetadataDatabase::GetMultiParentFileTrackers(std::string* file_id,
-                                                  TrackerIDSet* trackers) {
-  DCHECK(file_id);
-  DCHECK(trackers);
-  // TODO(tzik): Make this function more efficient.
-  for (TrackerIDsByFileID::const_iterator itr = trackers_by_file_id_.begin();
-       itr != trackers_by_file_id_.end(); ++itr) {
-    if (itr->second.size() > 1 && itr->second.has_active()) {
-      *file_id = itr->first;
-      *trackers = itr->second;
-      return true;
-    }
+bool MetadataDatabase::GetConflictingTrackers(TrackerIDSet* trackers_out) {
+  DCHECK(trackers_out);
+
+  ParentIDAndTitle parent_and_title = index_->PickMultiBackingFilePath();
+  if (parent_and_title.parent_id == kInvalidTrackerID)
+    return false;
+
+  TrackerIDSet trackers = index_->GetFileTrackerIDsByParentAndTitle(
+      parent_and_title.parent_id, parent_and_title.title);
+  if (trackers.size() <= 1) {
+    NOTREACHED();
+    return false;
   }
-  return false;
-}
 
-bool MetadataDatabase::GetConflictingTrackers(TrackerIDSet* trackers) {
-  DCHECK(trackers);
-  // TODO(tzik): Make this function more efficient.
-  for (TrackerIDsByParentAndTitle::const_iterator parent_itr =
-           trackers_by_parent_and_title_.begin();
-       parent_itr != trackers_by_parent_and_title_.end();
-       ++parent_itr) {
-    const TrackerIDsByTitle& trackers_by_title = parent_itr->second;
-    for (TrackerIDsByTitle::const_iterator itr = trackers_by_title.begin();
-         itr != trackers_by_title.end();
-         ++itr) {
-      if (itr->second.size() > 1 && itr->second.has_active()) {
-        *trackers = itr->second;
-        return true;
-      }
-    }
-  }
-  return false;
+  std::swap(*trackers_out, trackers);
+  return true;
 }
 
 void MetadataDatabase::GetRegisteredAppIDs(std::vector<std::string>* app_ids) {
   DCHECK(app_ids);
-  app_ids->clear();
-  app_ids->reserve(app_root_by_app_id_.size());
-  for (TrackerIDByAppID::iterator itr = app_root_by_app_id_.begin();
-       itr != app_root_by_app_id_.end(); ++itr) {
-    app_ids->push_back(itr->first);
-  }
+  *app_ids = index_->GetRegisteredAppIDs();
 }
 
 MetadataDatabase::MetadataDatabase(base::SequencedTaskRunner* task_runner,
                                    const base::FilePath& database_path,
                                    leveldb::Env* env_override)
     : task_runner_(task_runner),
       database_path_(database_path),
       env_override_(env_override),
       largest_known_change_id_(0),
       weak_ptr_factory_(this) {
@@ skipping 60 matching lines @@
   if (status != SYNC_STATUS_OK)
     return status;
 
   BuildIndexes(&contents);
   return status;
 }
 
 void MetadataDatabase::BuildIndexes(DatabaseContents* contents) {
   service_metadata_ = contents->service_metadata.Pass();
   UpdateLargestKnownChangeID(service_metadata_->largest_change_id());
-
-  for (ScopedVector<FileMetadata>::const_iterator itr =
-           contents->file_metadata.begin();
-       itr != contents->file_metadata.end();
-       ++itr) {
-    // make_scoped_ptr balances weak_clear below.
-    metadata_by_id_.set((*itr)->file_id(), make_scoped_ptr(*itr));
-  }
-  contents->file_metadata.weak_clear();
-
-  for (ScopedVector<FileTracker>::const_iterator itr =
-           contents->file_trackers.begin();
-       itr != contents->file_trackers.end();
-       ++itr) {
-    FileTracker* tracker = *itr;
-    // make_scoped_ptr balances weak_clear below.
-    tracker_by_id_.set(tracker->tracker_id(), make_scoped_ptr(tracker));
-    trackers_by_file_id_[tracker->file_id()].Insert(*tracker);
-
-    if (IsAppRoot(*tracker))
-      app_root_by_app_id_[tracker->app_id()] = tracker->tracker_id();
-
-    if (tracker->parent_tracker_id()) {
-      std::string title = GetTrackerTitle(*tracker);
-      TrackerIDSet* trackers =
-          &trackers_by_parent_and_title_[tracker->parent_tracker_id()][title];
-      trackers->Insert(*tracker);
-    }
-
-    if (tracker->dirty())
-      dirty_trackers_.insert(tracker);
-  }
-  contents->file_trackers.weak_clear();
-}
-
-void MetadataDatabase::RegisterTrackerAsAppRoot(
-    const std::string& app_id,
-    int64 tracker_id,
-    leveldb::WriteBatch* batch) {
-  FileTracker* tracker = tracker_by_id_.get(tracker_id);
-  DCHECK(tracker);
-  tracker->set_app_id(app_id);
-  tracker->set_tracker_kind(TRACKER_KIND_APP_ROOT);
-  app_root_by_app_id_[app_id] = tracker_id;
-
-  MakeTrackerActive(tracker->tracker_id(), batch);
-}
-
-void MetadataDatabase::UnregisterTrackerAsAppRoot(
-    const std::string& app_id,
-    leveldb::WriteBatch* batch) {
-  int64 tracker_id = FindAndEraseItem(&app_root_by_app_id_, app_id);
-  FileTracker* tracker = tracker_by_id_.get(tracker_id);
-  tracker->set_app_id(std::string());
-  tracker->set_tracker_kind(TRACKER_KIND_REGULAR);
-
-  // Inactivate the tracker to drop all descendant.
-  // (Note that we set tracker_kind to TRACKER_KIND_REGULAR before calling
-  // this.)
-  MakeTrackerInactive(tracker_id, batch);
-}
-
-void MetadataDatabase::MakeTrackerActive(int64 tracker_id,
-                                         leveldb::WriteBatch* batch) {
-  FileTracker* tracker = tracker_by_id_.get(tracker_id);
-  DCHECK(tracker);
-  DCHECK(!tracker->active());
-
-  int64 parent_tracker_id = tracker->parent_tracker_id();
-  DCHECK(tracker->has_synced_details());
-  trackers_by_file_id_[tracker->file_id()].Activate(tracker_id);
-  if (parent_tracker_id) {
-    trackers_by_parent_and_title_[parent_tracker_id][
-        tracker->synced_details().title()].Activate(tracker_id);
-  }
-  tracker->set_active(true);
-  tracker->set_needs_folder_listing(
-      tracker->synced_details().file_kind() == FILE_KIND_FOLDER);
-
-  // Make |tracker| a normal priority dirty tracker.
-  MarkSingleTrackerAsDirty(tracker, NULL);
-  PutFileTrackerToBatch(*tracker, batch);
-}
-
-void MetadataDatabase::MakeTrackerInactive(int64 tracker_id,
-                                           leveldb::WriteBatch* batch) {
-  FileTracker* tracker = tracker_by_id_.get(tracker_id);
-  DCHECK(tracker);
-  DCHECK(tracker->active());
-  DCHECK_EQ(TRACKER_KIND_REGULAR, tracker->tracker_kind());
-  trackers_by_file_id_[tracker->file_id()].Deactivate(tracker_id);
-
-  std::string title = GetTrackerTitle(*tracker);
-  int64 parent_tracker_id = tracker->parent_tracker_id();
-  if (parent_tracker_id) {
-    trackers_by_parent_and_title_[parent_tracker_id][title]
-        .Deactivate(tracker_id);
-  }
-  tracker->set_active(false);
-
-  RemoveAllDescendantTrackers(tracker_id, batch);
-  MarkTrackersDirtyByFileID(tracker->file_id(), batch);
-  if (parent_tracker_id)
-    MarkTrackersDirtyByPath(parent_tracker_id, title, batch);
-  PutFileTrackerToBatch(*tracker, batch);
-}
-
-void MetadataDatabase::MakeAppRootDisabled(int64 tracker_id,
-                                           leveldb::WriteBatch* batch) {
-  FileTracker* tracker = tracker_by_id_.get(tracker_id);
-  DCHECK(tracker);
-  DCHECK_EQ(TRACKER_KIND_APP_ROOT, tracker->tracker_kind());
-  DCHECK(tracker->active());
-
-  // Keep the app-root tracker active (but change the tracker_kind) so that
-  // other conflicting trackers won't become active.
-  tracker->set_tracker_kind(TRACKER_KIND_DISABLED_APP_ROOT);
-  PutFileTrackerToBatch(*tracker, batch);
-}
-
-void MetadataDatabase::MakeAppRootEnabled(int64 tracker_id,
-                                          leveldb::WriteBatch* batch) {
-  FileTracker* tracker = tracker_by_id_.get(tracker_id);
-  DCHECK(tracker);
-  DCHECK_EQ(TRACKER_KIND_DISABLED_APP_ROOT, tracker->tracker_kind());
-  DCHECK(tracker->active());
-
-  tracker->set_tracker_kind(TRACKER_KIND_APP_ROOT);
-  // Mark descendant trackers as dirty to handle changes in disable period.
-  RecursiveMarkTrackerAsDirty(tracker_id, batch);
-  PutFileTrackerToBatch(*tracker, batch);
+  index_.reset(new MetadataDatabaseIndex(contents));
 }
 
 void MetadataDatabase::CreateTrackerForParentAndFileID(
     const FileTracker& parent_tracker,
     const std::string& file_id,
     leveldb::WriteBatch* batch) {
   CreateTrackerInternal(parent_tracker, file_id, NULL,
                         UPDATE_TRACKER_FOR_UNSYNCED_FILE,
                         batch);
 }
@@ skipping 27 matching lines @@
   tracker->set_active(false);
   tracker->set_needs_folder_listing(false);
   if (details) {
     *tracker->mutable_synced_details() = *details;
     if (option == UPDATE_TRACKER_FOR_UNSYNCED_FILE) {
       tracker->mutable_synced_details()->set_missing(true);
       tracker->mutable_synced_details()->clear_md5();
     }
   }
   PutFileTrackerToBatch(*tracker, batch);
-
-  trackers_by_file_id_[file_id].InsertInactiveTracker(tracker->tracker_id());
-  // Note: |trackers_by_parent_and_title_| does not map from
-  // FileMetadata::details but from FileTracker::synced_details, which is filled
-  // on tracker updated phase.  Use empty string as the title since
-  // FileTracker::synced_details is empty here.
-  std::string title;
-  if (details)
-    title = details->title();
-  trackers_by_parent_and_title_[parent_tracker.tracker_id()][title]
-      .InsertInactiveTracker(tracker->tracker_id());
-  dirty_trackers_.insert(tracker.get());
-  StoreFileTracker(tracker.Pass());
-}
-
-void MetadataDatabase::RemoveTracker(int64 tracker_id,
-                                     leveldb::WriteBatch* batch) {
-  RemoveTrackerInternal(tracker_id, batch, false);
-  RemoveAllDescendantTrackers(tracker_id, batch);
-}
-
-void MetadataDatabase::RemoveTrackerIgnoringSameTitle(
-    int64 tracker_id,
-    leveldb::WriteBatch* batch) {
-  RemoveTrackerInternal(tracker_id, batch, true);
-}
-
-void MetadataDatabase::RemoveTrackerInternal(
-    int64 tracker_id,
-    leveldb::WriteBatch* batch,
-    bool ignoring_same_title) {
-  scoped_ptr<FileTracker> tracker(
-      tracker_by_id_.take_and_erase(tracker_id));
-  if (!tracker)
-    return;
-
-  EraseTrackerFromFileIDIndex(tracker.get(), batch);
-  if (IsAppRoot(*tracker))
-    app_root_by_app_id_.erase(tracker->app_id());
-  EraseTrackerFromPathIndex(tracker.get());
-  dirty_trackers_.erase(tracker.get());
-  low_priority_dirty_trackers_.erase(tracker.get());
-
-  MarkTrackersDirtyByFileID(tracker->file_id(), batch);
-  if (!ignoring_same_title) {
-    // Mark trackers having the same title with the given tracker as dirty.
-    MarkTrackersDirtyByPath(tracker->parent_tracker_id(),
-                            GetTrackerTitle(*tracker),
-                            batch);
-  }
-  PutFileTrackerDeletionToBatch(tracker_id, batch);
+  index_->StoreFileTracker(tracker.Pass());
 }
 
 void MetadataDatabase::MaybeAddTrackersForNewFile(
     const FileMetadata& metadata,
     UpdateOption option,
     leveldb::WriteBatch* batch) {
   std::set<int64> parents_to_exclude;
-  TrackerIDsByFileID::iterator found =
-      trackers_by_file_id_.find(metadata.file_id());
-  if (found != trackers_by_file_id_.end()) {
-    for (TrackerIDSet::const_iterator itr = found->second.begin();
-         itr != found->second.end(); ++itr) {
-      const FileTracker& tracker = *tracker_by_id_.get(*itr);
-      int64 parent_tracker_id = tracker.parent_tracker_id();
-      if (!parent_tracker_id)
-        continue;
+  TrackerIDSet existing_trackers =
+      index_->GetFileTrackerIDsByFileID(metadata.file_id());
+  for (TrackerIDSet::const_iterator itr = existing_trackers.begin();
+       itr != existing_trackers.end(); ++itr) {
+    const FileTracker* tracker = index_->GetFileTracker(*itr);
+    if (!tracker) {
+      NOTREACHED();
+      continue;
+    }
 
-      // Exclude |parent_tracker_id| if it already has a tracker that has
-      // unknown title or has the same title with |file|.
-      if (!tracker.has_synced_details() ||
-          tracker.synced_details().title() == metadata.details().title()) {
-        parents_to_exclude.insert(parent_tracker_id);
-      }
+    int64 parent_tracker_id = tracker->parent_tracker_id();
+    if (!parent_tracker_id)
+      continue;
+
+    // Exclude |parent_tracker_id| if it already has a tracker that has
+    // unknown title or has the same title with |file|.
+    if (!tracker->has_synced_details() ||
+        tracker->synced_details().title() == metadata.details().title()) {
+      parents_to_exclude.insert(parent_tracker_id);
     }
   }
 
   for (int i = 0; i < metadata.details().parent_folder_ids_size(); ++i) {
     std::string parent_folder_id = metadata.details().parent_folder_ids(i);
-    TrackerIDsByFileID::iterator found =
-        trackers_by_file_id_.find(parent_folder_id);
-    if (found == trackers_by_file_id_.end())
-      continue;
-
-    for (TrackerIDSet::const_iterator itr = found->second.begin();
-         itr != found->second.end(); ++itr) {
-      FileTracker* parent_tracker = tracker_by_id_.get(*itr);
-      int64 parent_tracker_id = parent_tracker->tracker_id();
+    TrackerIDSet parent_trackers =
+        index_->GetFileTrackerIDsByFileID(parent_folder_id);
+    for (TrackerIDSet::const_iterator itr = parent_trackers.begin();
+         itr != parent_trackers.end(); ++itr) {
+      const FileTracker* parent_tracker = index_->GetFileTracker(*itr);
       if (!parent_tracker->active())
         continue;
 
-      if (ContainsKey(parents_to_exclude, parent_tracker_id))
+      if (ContainsKey(parents_to_exclude, parent_tracker->tracker_id()))
         continue;
 
       CreateTrackerForParentAndFileMetadata(
           *parent_tracker, metadata, option, batch);
     }
   }
 }
 
-void MetadataDatabase::RemoveAllDescendantTrackers(int64 root_tracker_id,
-                                                   leveldb::WriteBatch* batch) {
-  std::vector<int64> pending_trackers;
-  PushChildTrackersToContainer(trackers_by_parent_and_title_,
-                               root_tracker_id,
-                               std::back_inserter(pending_trackers));
-
-  while (!pending_trackers.empty()) {
-    int64 tracker_id = pending_trackers.back();
-    pending_trackers.pop_back();
-    PushChildTrackersToContainer(trackers_by_parent_and_title_,
-                                 tracker_id,
-                                 std::back_inserter(pending_trackers));
-    RemoveTrackerIgnoringSameTitle(tracker_id, batch);
-  }
-}
-
-void MetadataDatabase::EraseTrackerFromFileIDIndex(FileTracker* tracker,
-                                                   leveldb::WriteBatch* batch) {
-  TrackerIDsByFileID::iterator found =
-      trackers_by_file_id_.find(tracker->file_id());
-  if (found == trackers_by_file_id_.end())
-    return;
-
-  TrackerIDSet* trackers = &found->second;
-  trackers->Erase(tracker->tracker_id());
-  if (!trackers->empty())
-    return;
-  trackers_by_file_id_.erase(found);
-  EraseFileFromDatabase(tracker->file_id(), batch);
-}
-
-void MetadataDatabase::EraseFileFromDatabase(const std::string& file_id,
-                                             leveldb::WriteBatch* batch) {
-  scoped_ptr<FileMetadata> file(metadata_by_id_.take_and_erase(file_id));
-  if (file)
-    PutFileMetadataDeletionToBatch(file_id, batch);
-}
-
-void MetadataDatabase::EraseTrackerFromPathIndex(FileTracker* tracker) {
-  TrackerIDsByParentAndTitle::iterator found =
-      trackers_by_parent_and_title_.find(tracker->parent_tracker_id());
-  if (found == trackers_by_parent_and_title_.end())
-    return;
-
-  std::string title = GetTrackerTitle(*tracker);
-  TrackerIDsByTitle* trackers_by_title = &found->second;
-  TrackerIDsByTitle::iterator found_by_title = trackers_by_title->find(title);
-  TrackerIDSet* conflicting_trackers = &found_by_title->second;
-  conflicting_trackers->Erase(tracker->tracker_id());
-
-  if (conflicting_trackers->empty()) {
-    trackers_by_title->erase(found_by_title);
-    if (trackers_by_title->empty())
-      trackers_by_parent_and_title_.erase(found);
-  }
-}
-
-void MetadataDatabase::MarkSingleTrackerAsDirty(FileTracker* tracker,
-                                                leveldb::WriteBatch* batch) {
-  if (!tracker->dirty()) {
-    tracker->set_dirty(true);
-    PutFileTrackerToBatch(*tracker, batch);
-  }
-  dirty_trackers_.insert(tracker);
-  low_priority_dirty_trackers_.erase(tracker);
-}
-
-void MetadataDatabase::ClearDirty(FileTracker* tracker,
-                                  leveldb::WriteBatch* batch) {
-  if (tracker->dirty()) {
-    tracker->set_dirty(false);
-    PutFileTrackerToBatch(*tracker, batch);
-  }
-
-  dirty_trackers_.erase(tracker);
-  low_priority_dirty_trackers_.erase(tracker);
-}
-
-void MetadataDatabase::MarkTrackerSetDirty(
-    TrackerIDSet* trackers,
-    leveldb::WriteBatch* batch) {
-  for (TrackerIDSet::iterator itr = trackers->begin();
-       itr != trackers->end(); ++itr) {
-    MarkSingleTrackerAsDirty(tracker_by_id_.get(*itr), batch);
-  }
-}
-
-void MetadataDatabase::MarkTrackersDirtyByFileID(
-    const std::string& file_id,
-    leveldb::WriteBatch* batch) {
-  TrackerIDsByFileID::iterator found = trackers_by_file_id_.find(file_id);
-  if (found != trackers_by_file_id_.end())
-    MarkTrackerSetDirty(&found->second, batch);
-}
-
-void MetadataDatabase::MarkTrackersDirtyByPath(int64 parent_tracker_id,
-                                               const std::string& title,
-                                               leveldb::WriteBatch* batch) {
-  TrackerIDsByParentAndTitle::iterator found =
-      trackers_by_parent_and_title_.find(parent_tracker_id);
-  if (found == trackers_by_parent_and_title_.end())
-    return;
-
-  TrackerIDsByTitle::iterator itr = found->second.find(title);
-  if (itr != found->second.end())
-    MarkTrackerSetDirty(&itr->second, batch);
-}
-
 int64 MetadataDatabase::IncrementTrackerID(leveldb::WriteBatch* batch) {
   int64 tracker_id = service_metadata_->next_tracker_id();
   service_metadata_->set_next_tracker_id(tracker_id + 1);
   PutServiceMetadataToBatch(*service_metadata_, batch);
   DCHECK_GT(tracker_id, 0);
   return tracker_id;
 }
 
-void MetadataDatabase::RecursiveMarkTrackerAsDirty(int64 root_tracker_id,
-                                                   leveldb::WriteBatch* batch) {
-  std::vector<int64> stack;
-  stack.push_back(root_tracker_id);
-  while (!stack.empty()) {
-    int64 tracker_id = stack.back();
-    stack.pop_back();
-    PushChildTrackersToContainer(
-        trackers_by_parent_and_title_, tracker_id, std::back_inserter(stack));
-
-    MarkSingleTrackerAsDirty(tracker_by_id_.get(tracker_id), batch);
-  }
-}
-
 bool MetadataDatabase::CanActivateTracker(const FileTracker& tracker) {
   DCHECK(!tracker.active());
   DCHECK_NE(service_metadata_->sync_root_tracker_id(), tracker.tracker_id());
 
   if (HasActiveTrackerForFileID(tracker.file_id()))
     return false;
 
   if (tracker.app_id().empty() &&
       tracker.tracker_id() != GetSyncRootTrackerID()) {
     return false;
@@ skipping 12 matching lines @@
 }
 
 bool MetadataDatabase::ShouldKeepDirty(const FileTracker& tracker) const {
   if (HasDisabledAppRoot(tracker))
     return false;
 
   DCHECK(tracker.dirty());
   if (!tracker.has_synced_details())
     return true;
 
-  MetadataByID::const_iterator found = metadata_by_id_.find(tracker.file_id());
-  if (found == metadata_by_id_.end())
+  const FileMetadata* metadata = index_->GetFileMetadata(tracker.file_id());
+  if (!metadata)
     return true;
-  const FileMetadata* metadata = found->second;
   DCHECK(metadata);
   DCHECK(metadata->has_details());
 
   const FileDetails& local_details = tracker.synced_details();
   const FileDetails& remote_details = metadata->details();
 
   if (tracker.active()) {
     if (tracker.needs_folder_listing())
       return true;
     if (local_details.md5() != remote_details.md5())
       return true;
     if (local_details.missing() != remote_details.missing())
       return true;
   }
 
   if (local_details.title() != remote_details.title())
     return true;
 
   return false;
 }
 
 bool MetadataDatabase::HasDisabledAppRoot(const FileTracker& tracker) const {
-  TrackerIDByAppID::const_iterator found =
-      app_root_by_app_id_.find(tracker.app_id());
-  if (found == app_root_by_app_id_.end())
+  int64 app_root_tracker_id = index_->GetAppRootTracker(tracker.app_id());
+  if (app_root_tracker_id == kInvalidTrackerID)
     return false;
 
-  const FileTracker* app_root_tracker = tracker_by_id_.get(found->second);
-  DCHECK(app_root_tracker);
+  const FileTracker* app_root_tracker =
+      index_->GetFileTracker(app_root_tracker_id);
+  if (!app_root_tracker) {
+    NOTREACHED();
+    return false;
+  }
   return app_root_tracker->tracker_kind() == TRACKER_KIND_DISABLED_APP_ROOT;
 }
 
 bool MetadataDatabase::HasActiveTrackerForFileID(
     const std::string& file_id) const {
-  TrackerIDsByFileID::const_iterator found = trackers_by_file_id_.find(file_id);
-  return found != trackers_by_file_id_.end() && found->second.has_active();
+  return index_->GetFileTrackerIDsByFileID(file_id).has_active();
 }
 
 bool MetadataDatabase::HasActiveTrackerForPath(int64 parent_tracker_id,
                                                const std::string& title) const {
-  TrackerIDsByParentAndTitle::const_iterator found_by_parent =
-      trackers_by_parent_and_title_.find(parent_tracker_id);
-  if (found_by_parent == trackers_by_parent_and_title_.end())
-    return false;
-
-  const TrackerIDsByTitle& trackers_by_title = found_by_parent->second;
-  TrackerIDsByTitle::const_iterator found = trackers_by_title.find(title);
-  return found != trackers_by_title.end() && found->second.has_active();
+  return index_->GetFileTrackerIDsByParentAndTitle(parent_tracker_id, title)
+      .has_active();
 }
 
 void MetadataDatabase::RemoveUnneededTrackersForMissingFile(
     const std::string& file_id,
     leveldb::WriteBatch* batch) {
-  TrackerIDSet trackers;
-  FindTrackersByFileID(file_id, &trackers);
+  TrackerIDSet trackers = index_->GetFileTrackerIDsByFileID(file_id);
   for (TrackerIDSet::const_iterator itr = trackers.begin();
        itr != trackers.end(); ++itr) {
-    const FileTracker& tracker = *tracker_by_id_.get(*itr);
-    if (!tracker.has_synced_details() ||
-        tracker.synced_details().missing()) {
-      RemoveTracker(tracker.tracker_id(), batch);
+    const FileTracker* tracker = index_->GetFileTracker(*itr);
+    if (!tracker) {
+      NOTREACHED();
+      continue;
+    }
+
+    if (!tracker->has_synced_details() ||
+        tracker->synced_details().missing()) {
+      RemoveFileTracker(*itr, MARK_NOTHING_DIRTY, index_.get(), batch);
     }
   }
 }
 
 void MetadataDatabase::UpdateByFileMetadata(
     const tracked_objects::Location& from_where,
     scoped_ptr<FileMetadata> metadata,
     UpdateOption option,
     leveldb::WriteBatch* batch) {
   DCHECK(metadata);
   DCHECK(metadata->has_details());
 
   DVLOG(1) << from_where.function_name() << ": "
            << metadata->file_id() << " ("
            << metadata->details().title() << ")"
            << (metadata->details().missing() ? " deleted" : "");
 
   std::string file_id = metadata->file_id();
   if (metadata->details().missing())
     RemoveUnneededTrackersForMissingFile(file_id, batch);
   else
     MaybeAddTrackersForNewFile(*metadata, option, batch);
 
-  if (FindTrackersByFileID(file_id, NULL)) {
+  TrackerIDSet trackers = index_->GetFileTrackerIDsByFileID(file_id);
+  if (!trackers.empty()) {
+    PutFileMetadataToBatch(*metadata, batch);
+    index_->StoreFileMetadata(metadata.Pass());
+
     if (option != UPDATE_TRACKER_FOR_SYNCED_FILE)
-      MarkTrackersDirtyByFileID(file_id, batch);
-    PutFileMetadataToBatch(*metadata, batch);
-    StoreFileMetadata(metadata.Pass());
+      MarkTrackerSetDirty(trackers, index_.get(), batch);
   }
 }
 
 void MetadataDatabase::WriteToDatabase(scoped_ptr<leveldb::WriteBatch> batch,
                                        const SyncStatusCallback& callback) {
   if (!batch) {
     RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
     return;
   }
 
   base::PostTaskAndReplyWithResult(
       task_runner_.get(),
       FROM_HERE,
       base::Bind(&leveldb::DB::Write,
                  base::Unretained(db_.get()),
                  leveldb::WriteOptions(),
                  base::Owned(batch.release())),
       base::Bind(&AdaptLevelDBStatusToSyncStatusCode, callback));
 }
 
 scoped_ptr<base::ListValue> MetadataDatabase::DumpFiles(
     const std::string& app_id) {
   scoped_ptr<base::ListValue> files(new base::ListValue);
 
   FileTracker app_root_tracker;
   if (!FindAppRootTracker(app_id, &app_root_tracker))
     return files.Pass();
 
   std::vector<int64> stack;
-  PushChildTrackersToContainer(
-        trackers_by_parent_and_title_,
-        app_root_tracker.tracker_id(),
-        std::back_inserter(stack));
+  AppendContents(
+      index_->GetFileTrackerIDsByParent(app_root_tracker.tracker_id()), &stack);
   while (!stack.empty()) {
     int64 tracker_id = stack.back();
     stack.pop_back();
-    PushChildTrackersToContainer(
-        trackers_by_parent_and_title_, tracker_id, std::back_inserter(stack));
+    AppendContents(index_->GetFileTrackerIDsByParent(tracker_id), &stack);
 
-    const FileTracker* tracker = tracker_by_id_.get(tracker_id);
+    const FileTracker* tracker = index_->GetFileTracker(tracker_id);
+    if (!tracker) {
+      NOTREACHED();
+      continue;
+    }
     base::DictionaryValue* file = new base::DictionaryValue;
 
     base::FilePath path = BuildDisplayPathForTracker(*tracker);
     file->SetString("path", path.AsUTF8Unsafe());
     if (tracker->has_synced_details()) {
       file->SetString("title", tracker->synced_details().title());
       file->SetString("type",
                       FileKindToString(tracker->synced_details().file_kind()));
     }
 
@@ skipping 15 matching lines @@
 
 scoped_ptr<base::ListValue> MetadataDatabase::DumpDatabase() {
   scoped_ptr<base::ListValue> list(new base::ListValue);
   list->Append(DumpTrackers().release());
   list->Append(DumpMetadata().release());
   return list.Pass();
 }
 
 bool MetadataDatabase::HasNewerFileMetadata(const std::string& file_id,
                                             int64 change_id) {
-  MetadataByID::const_iterator found = metadata_by_id_.find(file_id);
-  if (found == metadata_by_id_.end())
+  const FileMetadata* metadata = index_->GetFileMetadata(file_id);
+  if (!metadata)
     return false;
-  DCHECK(found->second->has_details());
-  return found->second->details().change_id() >= change_id;
+  DCHECK(metadata->has_details());
+  return metadata->details().change_id() >= change_id;
 }
 
 scoped_ptr<base::ListValue> MetadataDatabase::DumpTrackers() {
   scoped_ptr<base::ListValue> trackers(new base::ListValue);
 
   // Append the first element for metadata.
   base::DictionaryValue* metadata = new base::DictionaryValue;
   const char *trackerKeys[] = {
     "tracker_id", "path", "file_id", "tracker_kind", "app_id",
     "active", "dirty", "folder_listing",
     "title", "kind", "md5", "etag", "missing", "change_id",
   };
   std::vector<std::string> key_strings(
       trackerKeys, trackerKeys + ARRAYSIZE_UNSAFE(trackerKeys));
   base::ListValue* keys = new base::ListValue;
   keys->AppendStrings(key_strings);
   metadata->SetString("title", "Trackers");
   metadata->Set("keys", keys);
   trackers->Append(metadata);
 
   // Append tracker data.
-  for (TrackerByID::const_iterator itr = tracker_by_id_.begin();
-       itr != tracker_by_id_.end(); ++itr) {
+  for (MetadataDatabaseIndex::TrackerByID::const_iterator itr =
+           index_->tracker_by_id_.begin();
+       itr != index_->tracker_by_id_.end(); ++itr) {
     const FileTracker& tracker = *itr->second;
     base::DictionaryValue* dict = new base::DictionaryValue;
     base::FilePath path = BuildDisplayPathForTracker(tracker);
     dict->SetString("tracker_id", base::Int64ToString(tracker.tracker_id()));
     dict->SetString("path", path.AsUTF8Unsafe());
     dict->SetString("file_id", tracker.file_id());
     TrackerKind tracker_kind = tracker.tracker_kind();
     dict->SetString(
         "tracker_kind",
         tracker_kind == TRACKER_KIND_APP_ROOT ? "AppRoot" :
@@ skipping 30 matching lines @@
   };
   std::vector<std::string> key_strings(
       fileKeys, fileKeys + ARRAYSIZE_UNSAFE(fileKeys));
   base::ListValue* keys = new base::ListValue;
   keys->AppendStrings(key_strings);
   metadata->SetString("title", "Metadata");
   metadata->Set("keys", keys);
   files->Append(metadata);
 
   // Append metadata data.
-  for (MetadataByID::const_iterator itr = metadata_by_id_.begin();
-       itr != metadata_by_id_.end(); ++itr) {
+  for (MetadataDatabaseIndex::MetadataByID::const_iterator itr =
+           index_->metadata_by_id_.begin();
+       itr != index_->metadata_by_id_.end(); ++itr) {
     const FileMetadata& file = *itr->second;
 
     base::DictionaryValue* dict = new base::DictionaryValue;
     dict->SetString("file_id", file.file_id());
     if (file.has_details()) {
       const FileDetails& details = file.details();
       dict->SetString("title", details.title());
       dict->SetString("type", FileKindToString(details.file_kind()));
       dict->SetString("md5", details.md5());
       dict->SetString("etag", details.etag());
       dict->SetString("missing", details.missing() ? "true" : "false");
       dict->SetString("change_id", base::Int64ToString(details.change_id()));
 
       std::vector<std::string> parents;
       for (int i = 0; i < details.parent_folder_ids_size(); ++i)
         parents.push_back(details.parent_folder_ids(i));
       dict->SetString("parents", JoinString(parents, ","));
     }
     files->Append(dict);
   }
   return files.Pass();
 }
 
-void MetadataDatabase::StoreFileMetadata(
-    scoped_ptr<FileMetadata> file_metadata) {
-  DCHECK(file_metadata);
-
-  std::string file_id = file_metadata->file_id();
-  metadata_by_id_.set(file_id, file_metadata.Pass());
-}
-
-void MetadataDatabase::StoreFileTracker(scoped_ptr<FileTracker> file_tracker) {
-  DCHECK(file_tracker);
-
-  int64 tracker_id = file_tracker->tracker_id();
-  DCHECK(!ContainsKey(tracker_by_id_, tracker_id));
-  tracker_by_id_.set(tracker_id, file_tracker.Pass());
-}
-
 void MetadataDatabase::AttachSyncRoot(
     const google_apis::FileResource& sync_root_folder,
     leveldb::WriteBatch* batch) {
   scoped_ptr<FileMetadata> sync_root_metadata =
       CreateFileMetadataFromFileResource(
           GetLargestKnownChangeID(), sync_root_folder);
   scoped_ptr<FileTracker> sync_root_tracker =
       CreateSyncRootTracker(IncrementTrackerID(batch), *sync_root_metadata);
 
   PutFileMetadataToBatch(*sync_root_metadata, batch);
   PutFileTrackerToBatch(*sync_root_tracker, batch);
 
   service_metadata_->set_sync_root_tracker_id(sync_root_tracker->tracker_id());
   PutServiceMetadataToBatch(*service_metadata_, batch);
 
-  InsertFileTrackerToIndex(sync_root_tracker.get());
-
-  StoreFileMetadata(sync_root_metadata.Pass());
-  StoreFileTracker(sync_root_tracker.Pass());
+  index_->StoreFileMetadata(sync_root_metadata.Pass());
+  index_->StoreFileTracker(sync_root_tracker.Pass());
 }
 
 void MetadataDatabase::AttachInitialAppRoot(
     const google_apis::FileResource& app_root_folder,
     leveldb::WriteBatch* batch) {
   scoped_ptr<FileMetadata> app_root_metadata =
       CreateFileMetadataFromFileResource(
           GetLargestKnownChangeID(), app_root_folder);
   scoped_ptr<FileTracker> app_root_tracker =
       CreateInitialAppRootTracker(IncrementTrackerID(batch),
                                   GetSyncRootTrackerID(),
                                   *app_root_metadata);
 
   PutFileMetadataToBatch(*app_root_metadata, batch);
   PutFileTrackerToBatch(*app_root_tracker, batch);
 
-  InsertFileTrackerToIndex(app_root_tracker.get());
-
-  StoreFileMetadata(app_root_metadata.Pass());
-  StoreFileTracker(app_root_tracker.Pass());
-}
-
-void MetadataDatabase::InsertFileTrackerToIndex(FileTracker* tracker) {
-  trackers_by_file_id_[tracker->file_id()].Insert(*tracker);
-  if (IsAppRoot(*tracker)) {
-    DCHECK(!ContainsKey(app_root_by_app_id_, tracker->app_id()));
-    app_root_by_app_id_[tracker->app_id()] = tracker->tracker_id();
-  }
-
-  int64 parent_tracker_id = tracker->parent_tracker_id();
-  if (parent_tracker_id) {
-    std::string title = GetTrackerTitle(*tracker);
-    trackers_by_parent_and_title_[parent_tracker_id][title].Insert(*tracker);
-  }
-
-  if (tracker->dirty()) {
-    dirty_trackers_.insert(tracker);
-    low_priority_dirty_trackers_.erase(tracker);
-  }
-}
-
-void MetadataDatabase::ForceActivateTrackerByPath(int64 parent_tracker_id,
-                                                  const std::string& title,
-                                                  const std::string& file_id,
-                                                  leveldb::WriteBatch* batch) {
-  DCHECK(ContainsKey(trackers_by_parent_and_title_, parent_tracker_id));
-  DCHECK(ContainsKey(trackers_by_parent_and_title_[parent_tracker_id], title));
-  DCHECK(!trackers_by_file_id_[file_id].has_active());
-
-  TrackerIDSet* same_path_trackers =
-      &trackers_by_parent_and_title_[parent_tracker_id][title];
-
-  for (TrackerIDSet::iterator itr = same_path_trackers->begin();
-       itr != same_path_trackers->end(); ++itr) {
-    FileTracker* tracker = tracker_by_id_.get(*itr);
-    if (tracker->file_id() != file_id)
-      continue;
-
-    if (same_path_trackers->has_active()) {
-      MakeTrackerInactive(same_path_trackers->active_tracker(), batch);
-    }
-    MakeTrackerActive(tracker->tracker_id(), batch);
-    ClearDirty(tracker, batch);
-    return;
-  }
-
-  NOTREACHED();
+  index_->StoreFileMetadata(app_root_metadata.Pass());
+  index_->StoreFileTracker(app_root_tracker.Pass());
 }
 
 }  // namespace drive_backend
 }  // namespace sync_file_system