--- a/browser/components/places/content/treeView.js
+++ b/browser/components/places/content/treeView.js
@@ -5,23 +5,49 @@
 Components.utils.import("resource://gre/modules/XPCOMUtils.jsm");
 Components.utils.import("resource://gre/modules/Services.jsm");
 
 const PTV_interfaces = [Ci.nsITreeView,
                         Ci.nsINavHistoryResultObserver,
                         Ci.nsINavHistoryResultTreeViewer,
                         Ci.nsISupportsWeakReference];
 
+/**
+ * This returns the key for any node/details object.
+ *
+ * @param nodeOrDetails
+ *        A node, or an object containing the following properties:
+ *        - uri
+ *        - time
+ *        - itemId
+ *        In case any of these is missing, an empty string will be returned. This is
+ *        to facilitate easy delete statements which occur due to assignment to items in `this._rows`,
+ *        since the item we are deleting may be undefined in the array.
+ *
+ * @return key or empty string.
+ */
+function makeNodeDetailsKey(nodeOrDetails) {
+  if (nodeOrDetails &&
+      typeof nodeOrDetails === "object" &&
+      "uri" in nodeOrDetails &&
+      "time" in nodeOrDetails &&
+      "itemId" in nodeOrDetails) {
+    return `${nodeOrDetails.uri}*${nodeOrDetails.time}*${nodeOrDetails.itemId}`;
+  }
+  return "";
+}
+
 function PlacesTreeView(aFlatList, aOnOpenFlatContainer, aController) {
   this._tree = null;
   this._result = null;
   this._selection = null;
   this._rootNode = null;
   this._rows = [];
   this._flatList = aFlatList;
+  this._nodeDetails = new Map();
   this._openContainerCallback = aOnOpenFlatContainer;
   this._controller = aController;
 }
 
 PlacesTreeView.prototype = {
   get wrappedJSObject() {
     return this;
   },
@@ -182,18 +208,21 @@ PlacesTreeView.prototype = {
       row = this._rows.indexOf(aNode, aParentRow);
       if (row == -1 && aForceBuild) {
         let parentRow = typeof(aParentRow) == "number" ? aParentRow
                                                        : this._getRowForNode(parent);
         row = parentRow + parent.getChildIndex(aNode) + 1;
       }
     }
 
-    if (row != -1)
+    if (row != -1) {
+      this._nodeDetails.delete(makeNodeDetailsKey(this._rows[row]));
+      this._nodeDetails.set(makeNodeDetailsKey(aNode), aNode);
       this._rows[row] = aNode;
+    }
 
     return row;
   },
 
   /**
    * Given a row, finds and returns the parent details of the associated node.
    *
    * @param aChildRow
@@ -228,26 +257,37 @@ PlacesTreeView.prototype = {
     let rowNode, row;
     for (let i = aRow - 1; i >= 0 && rowNode === undefined; i--) {
       rowNode = this._rows[i];
       row = i;
     }
 
     // If there's no container prior to the given row, it's a child of
     // the root node (remember: all containers are listed in the rows array).
-    if (!rowNode)
-      return this._rows[aRow] = this._rootNode.getChild(aRow);
+    if (!rowNode) {
+      let newNode = this._rootNode.getChild(aRow);
+      this._nodeDetails.delete(makeNodeDetailsKey(this._rows[aRow]));
+      this._nodeDetails.set(makeNodeDetailsKey(newNode), newNode);
+      return this._rows[aRow] = newNode;
+    }
 
     // Unset elements may exist only in plain containers.  Thus, if the nearest
     // node is a container, it's the row's parent, otherwise, it's a sibling.
-    if (rowNode instanceof Ci.nsINavHistoryContainerResultNode)
-      return this._rows[aRow] = rowNode.getChild(aRow - row - 1);
+    if (rowNode instanceof Ci.nsINavHistoryContainerResultNode) {
+      let newNode = rowNode.getChild(aRow - row - 1);
+      this._nodeDetails.delete(makeNodeDetailsKey(this._rows[aRow]));
+      this._nodeDetails.set(makeNodeDetailsKey(newNode), newNode);
+      return this._rows[aRow] = newNode;
+    }
 
     let [parent, parentRow] = this._getParentByChildRow(row);
-    return this._rows[aRow] = parent.getChild(aRow - parentRow - 1);
+    let newNode = parent.getChild(aRow - parentRow - 1);
+    this._nodeDetails.delete(makeNodeDetailsKey(this._rows[aRow]));
+    this._nodeDetails.set(makeNodeDetailsKey(newNode), newNode);
+    return this._rows[aRow] = newNode;
   },
 
   /**
    * This takes a container and recursively appends our rows array per its
    * contents.  Assumes that the rows arrays has no rows for the given
    * container.
    *
    * @param [in] aContainer
@@ -266,16 +306,20 @@ PlacesTreeView.prototype = {
     if (!aContainer.containerOpen)
       return 0;
 
     // Inserting the new elements into the rows array in one shot (by
     // Array.prototype.concat) is faster than resizing the array (by splice) on each loop
     // iteration.
     let cc = aContainer.childCount;
     let newElements = new Array(cc);
+    // We need to clean up the node details from aFirstChildRow + 1 to the end of rows.
+    for (let i = aFirstChildRow + 1; i < this._rows.length; i++) {
+      this._nodeDetails.delete(makeNodeDetailsKey(this._rows[i]));
+    }
     this._rows = this._rows.splice(0, aFirstChildRow)
                      .concat(newElements, this._rows);
 
     if (this._isPlainContainer(aContainer))
       return cc;
 
     let sortingMode = this._result.sortingMode;
 
@@ -287,21 +331,24 @@ PlacesTreeView.prototype = {
       let row = aFirstChildRow + rowsInserted;
 
       // Don't display separators when sorted.
       if (curChildType == Ci.nsINavHistoryResultNode.RESULT_TYPE_SEPARATOR) {
         if (sortingMode != Ci.nsINavHistoryQueryOptions.SORT_BY_NONE) {
           // Remove the element for the filtered separator.
           // Notice that the rows array was initially resized to include all
           // children.
+          this._nodeDetails.delete(makeNodeDetailsKey(this._rows[row]));
           this._rows.splice(row, 1);
           continue;
         }
       }
 
+      this._nodeDetails.delete(makeNodeDetailsKey(this._rows[row]));
+      this._nodeDetails.set(makeNodeDetailsKey(curChild), curChild);
       this._rows[row] = curChild;
       rowsInserted++;
 
       // Recursively do containers.
       if (!this._flatList &&
           curChild instanceof Ci.nsINavHistoryContainerResultNode &&
           !this._controller.hasCachedLivemarkInfo(curChild)) {
         let uri = curChild.uri;
@@ -402,32 +449,31 @@ PlacesTreeView.prototype = {
     let parent = aOldNode.parent;
     if (parent) {
       // If the node's parent is still set, the node is not obsolete
       // and we should just find out its new position.
       // However, if any of the node's ancestor is closed, the node is
       // invisible.
       let ancestors = PlacesUtils.nodeAncestors(aOldNode);
       for (let ancestor of ancestors) {
-        if (!ancestor.containerOpen)
+        if (!ancestor.containerOpen) {
           return -1;
+        }
       }
 
       return this._getRowForNode(aOldNode, true);
     }
 
     // There's a broken edge case here.
     // If a visit appears in two queries, and the second one was
     // the old node, we'll select the first one after refresh.  There's
     // nothing we could do about that, because aOldNode.parent is
     // gone by the time invalidateContainer is called.
-    let newNode = aUpdatedContainer.findNodeByDetails(aOldNode.uri,
-                                                      aOldNode.time,
-                                                      aOldNode.itemId,
-                                                      true);
+    let newNode = this._nodeDetails.get(makeNodeDetailsKey(aOldNode));
+
     if (!newNode)
       return -1;
 
     return this._getRowForNode(newNode, true);
   },
 
   /**
    * Restores a given selection state as near as possible to the original
@@ -644,16 +690,17 @@ PlacesTreeView.prototype = {
         // in our list takes up (it could be a container with many children).
         let prevChild = aParentNode.getChild(aNewIndex - 1);
         let prevIndex = this._getRowForNode(prevChild, false, parentRow,
                                             aNewIndex - 1);
         row = prevIndex + this._countVisibleRowsForNodeAtRow(prevIndex);
       }
     }
 
+    this._nodeDetails.set(makeNodeDetailsKey(aNode), aNode);
     this._rows.splice(row, 0, aNode);
     this._tree.rowCountChanged(row, 1);
 
     if (PlacesUtils.nodeIsContainer(aNode) &&
         PlacesUtils.asContainer(aNode).containerOpen) {
       this.invalidateContainer(aNode);
     }
   },
@@ -695,17 +742,19 @@ PlacesTreeView.prototype = {
       selection.getRangeAt(0, min, max);
       if (min.value == max.value &&
           this.nodeForTreeIndex(min.value) == aNode)
         selectNext = true;
     }
 
     // Remove the node and its children, if any.
     let count = this._countVisibleRowsForNodeAtRow(oldRow);
-    this._rows.splice(oldRow, count);
+    for (let splicedNode of this._rows.splice(oldRow, count)) {
+      this._nodeDetails.delete(makeNodeDetailsKey(splicedNode));
+    }
     this._tree.rowCountChanged(oldRow, -count);
 
     // Redraw the parent if its twisty state has changed.
     if (aParentNode != this._rootNode && !aParentNode.hasChildren) {
       parentRow = oldRow - 1;
       this._tree.invalidateRow(parentRow);
     }
 
@@ -748,17 +797,19 @@ PlacesTreeView.prototype = {
 
     // Redraw the parent if its twisty state has changed.
     if (aOldParent != this._rootNode && !aOldParent.hasChildren) {
       let parentRow = oldRow - 1;
       this._tree.invalidateRow(parentRow);
     }
 
     // Remove node and its children, if any, from the old position.
-    this._rows.splice(oldRow, count);
+    for (let splicedNode of this._rows.splice(oldRow, count)) {
+      this._nodeDetails.delete(makeNodeDetailsKey(splicedNode));
+    }
     this._tree.rowCountChanged(oldRow, -count);
 
     // Insert the node into the new position.
     this.nodeInserted(aNewParent, aNode, aNewIndex);
 
     // Restore selection.
     if (nodesToReselect.length > 0) {
       this._restoreSelection(nodesToReselect, aNewParent);
@@ -812,26 +863,34 @@ PlacesTreeView.prototype = {
       }, Components.utils.reportError);
   },
 
   nodeTitleChanged: function PTV_nodeTitleChanged(aNode, aNewTitle) {
     this._invalidateCellValue(aNode, this.COLUMN_TYPE_TITLE);
   },
 
   nodeURIChanged: function PTV_nodeURIChanged(aNode, aOldURI) {
+    this._nodeDetails.delete(makeNodeDetailsKey({uri: aOldURI,
+                                                 itemId: aNode.itemId,
+                                                 time: aNode.time}));
+    this._nodeDetails.set(makeNodeDetailsKey(aNode), aNode);
     this._invalidateCellValue(aNode, this.COLUMN_TYPE_URI);
   },
 
   nodeIconChanged: function PTV_nodeIconChanged(aNode) {
     this._invalidateCellValue(aNode, this.COLUMN_TYPE_TITLE);
   },
 
   nodeHistoryDetailsChanged:
   function PTV_nodeHistoryDetailsChanged(aNode, aOldVisitDate,
                                          aOldVisitCount) {
+    this._nodeDetails.delete(makeNodeDetailsKey({uri: aNode.uri,
+                                                 itemId: aNode.itemId,
+                                                 time: aOldVisitDate}));
+    this._nodeDetails.set(makeNodeDetailsKey(aNode), aNode);
     if (aNode.parent && this._controller.hasCachedLivemarkInfo(aNode.parent)) {
       // Find the node in the parent.
       let parentRow = this._flatList ? 0 : this._getRowForNode(aNode.parent);
       for (let i = parentRow; i < this._rows.length; i++) {
         let child = this.nodeForTreeIndex(i);
         if (child.uri == aNode.uri) {
           this._cellProperties.delete(child);
           this._invalidateCellValue(child, this.COLUMN_TYPE_TITLE);
@@ -913,16 +972,17 @@ PlacesTreeView.prototype = {
 
     let startReplacement, replaceCount;
     if (aContainer == this._rootNode) {
       startReplacement = 0;
       replaceCount = this._rows.length;
 
       // If the root node is now closed, the tree is empty.
       if (!this._rootNode.containerOpen) {
+        this._nodeDetails.clear();
         this._rows = [];
         if (replaceCount)
           this._tree.rowCountChanged(startReplacement, -replaceCount);
 
         return;
       }
     } else {
       // Update the twisty state.
@@ -939,17 +999,19 @@ PlacesTreeView.prototype = {
     let nodesToReselect =
       this._getSelectedNodesInRange(startReplacement,
                                     startReplacement + replaceCount);
 
     // Now update the number of elements.
     this.selection.selectEventsSuppressed = true;
 
     // First remove the old elements
-    this._rows.splice(startReplacement, replaceCount);
+    for (let splicedNode of this._rows.splice(startReplacement, replaceCount)) {
+      this._nodeDetails.delete(makeNodeDetailsKey(splicedNode));
+    }
 
     // If the container is now closed, we're done.
     if (!aContainer.containerOpen) {
       let oldSelectionCount = this.selection.count;
       if (replaceCount)
         this._tree.rowCountChanged(startReplacement, -replaceCount);
 
       // Select the row next to the closed container if any of its

--- a/toolkit/components/places/nsINavHistoryService.idl
+++ b/toolkit/components/places/nsINavHistoryService.idl
@@ -248,38 +248,16 @@ interface nsINavHistoryContainerResultNo
    *        a result node.
    *
    * @return aNode's index in this container.
    * @throws NS_ERROR_NOT_AVAILABLE if containerOpen is false.
    * @throws NS_ERROR_INVALID_ARG if aNode isn't a direct child of this
    * container.
    */
   unsigned long getChildIndex(in nsINavHistoryResultNode aNode);
-
-  /**
-   * Look for a node in the container by some of its details.  Does not search
-   * closed containers.
-   *
-   * @param aURI
-   *        the node's uri attribute value
-   * @param aTime
-   *        the node's time attribute value.
-   * @param aItemId
-   *        the node's itemId attribute value.
-   * @param aRecursive
-   *        whether or not to search recursively.
-   *
-   * @throws NS_ERROR_NOT_AVAILABLE if this container is closed.
-   * @return a result node that matches the given details if any, null
-   *         otherwise.
-   */
-  nsINavHistoryResultNode findNodeByDetails(in AUTF8String aURIString,
-                                            in PRTime aTime,
-                                            in long long aItemId,
-                                            in boolean aRecursive);
 };
 
 
 /**
  * Used for places queries and as a base for bookmark folders.
  *
  * Note that if you request places to *not* be expanded in the options that
  * generated this node, this item will report it has no children and never try

--- a/toolkit/components/places/nsNavHistoryResult.cpp
+++ b/toolkit/components/places/nsNavHistoryResult.cpp
@@ -1703,53 +1703,16 @@ nsNavHistoryContainerResultNode::GetChil
   int32_t nodeIndex = FindChild(static_cast<nsNavHistoryResultNode*>(aNode));
   if (nodeIndex == -1)
     return NS_ERROR_INVALID_ARG;
 
   *_retval = nodeIndex;
   return NS_OK;
 }
 
-
-NS_IMETHODIMP
-nsNavHistoryContainerResultNode::FindNodeByDetails(const nsACString& aURIString,
-                                                   PRTime aTime,
-                                                   int64_t aItemId,
-                                                   bool aRecursive,
-                                                   nsINavHistoryResultNode** _retval) {
-  if (!mExpanded)
-    return NS_ERROR_NOT_AVAILABLE;
-
-  *_retval = nullptr;
-  for (int32_t i = 0; i < mChildren.Count(); ++i) {
-    if (mChildren[i]->mURI.Equals(aURIString) &&
-        mChildren[i]->mTime == aTime &&
-        mChildren[i]->mItemId == aItemId) {
-      *_retval = mChildren[i];
-      break;
-    }
-
-    if (aRecursive && mChildren[i]->IsContainer()) {
-      nsNavHistoryContainerResultNode* asContainer =
-        mChildren[i]->GetAsContainer();
-      if (asContainer->mExpanded) {
-        nsresult rv = asContainer->FindNodeByDetails(aURIString, aTime,
-                                                     aItemId,
-                                                     aRecursive,
-                                                     _retval);
-
-        if (NS_SUCCEEDED(rv) && _retval)
-          break;
-      }
-    }
-  }
-  NS_IF_ADDREF(*_retval);
-  return NS_OK;
-}
-
 /**
  * HOW QUERY UPDATING WORKS
  *
  * Queries are different than bookmark folders in that we can not always do
  * dynamic updates (easily) and updates are more expensive.  Therefore, we do
  * NOT query if we are not open and want to see if we have any children (for
  * drawing a twisty) and always assume we will.
  *

--- a/toolkit/components/places/nsNavHistoryResult.h
+++ b/toolkit/components/places/nsNavHistoryResult.h
@@ -414,21 +414,16 @@ NS_DEFINE_STATIC_IID_ACCESSOR(nsNavHisto
   NS_IMETHOD SetContainerOpen(bool aContainerOpen) override \
     { return nsNavHistoryContainerResultNode::SetContainerOpen(aContainerOpen); } \
   NS_IMETHOD GetChildCount(uint32_t *aChildCount) override \
     { return nsNavHistoryContainerResultNode::GetChildCount(aChildCount); } \
   NS_IMETHOD GetChild(uint32_t index, nsINavHistoryResultNode **_retval) override \
     { return nsNavHistoryContainerResultNode::GetChild(index, _retval); } \
   NS_IMETHOD GetChildIndex(nsINavHistoryResultNode* aNode, uint32_t* _retval) override \
     { return nsNavHistoryContainerResultNode::GetChildIndex(aNode, _retval); } \
-  NS_IMETHOD FindNodeByDetails(const nsACString& aURIString, PRTime aTime, \
-                               int64_t aItemId, bool aRecursive, \
-                               nsINavHistoryResultNode** _retval) override \
-    { return nsNavHistoryContainerResultNode::FindNodeByDetails(aURIString, aTime, aItemId, \
-                                                                aRecursive, _retval); }
 
 #define NS_NAVHISTORYCONTAINERRESULTNODE_IID \
   { 0x6e3bf8d3, 0x22aa, 0x4065, { 0x86, 0xbc, 0x37, 0x46, 0xb5, 0xb3, 0x2c, 0xe8 } }
 
 class nsNavHistoryContainerResultNode : public nsNavHistoryResultNode,
                                         public nsINavHistoryContainerResultNode
 {
 public: