diff --git a/src/file/fileindexscheduler.h b/src/file/fileindexscheduler.h
--- a/src/file/fileindexscheduler.h
+++ b/src/file/fileindexscheduler.h
@@ -77,10 +77,15 @@
     void scheduleIndexing();
     void halt();
 
+    /** Schedule new file indexing and missing file deindexing */
+    Q_SCRIPTABLE void updateIndex();
+
+    /** Schedule new file indexing only */
+    Q_SCRIPTABLE void checkUnindexedFiles();
+
     Q_SCRIPTABLE void suspend() { suspendContentIndexer(true); }
     Q_SCRIPTABLE void resume() { suspendContentIndexer(false); }
     Q_SCRIPTABLE uint getRemainingTime();
-    Q_SCRIPTABLE void checkUnindexedFiles();
     Q_SCRIPTABLE uint getBatchSize();
 
 private Q_SLOTS:
@@ -106,6 +111,7 @@
     TimeEstimator m_timeEstimator;
 
     bool m_checkUnindexedFiles;
+    bool m_purgeDeindexableFiles;
 };
 
 }
diff --git a/src/file/fileindexscheduler.cpp b/src/file/fileindexscheduler.cpp
--- a/src/file/fileindexscheduler.cpp
+++ b/src/file/fileindexscheduler.cpp
@@ -26,6 +26,7 @@
 #include "filecontentindexer.h"
 #include "filecontentindexerprovider.h"
 #include "unindexedfileindexer.h"
+#include "indexcleaner.h"
 
 #include "fileindexerconfig.h"
 
@@ -94,6 +95,17 @@
         return;
     }
 
+    if (m_purgeDeindexableFiles && !m_indexerStates.contains(DeindexingFileCheck)) {
+        auto runnable = new IndexCleaner(m_db, m_config);
+        connect(runnable, &IndexCleaner::done, this, [=] () {
+            m_purgeDeindexableFiles = false;
+            runnableStopped(DeindexingFileCheck);
+        });
+
+        m_threadPool.start(runnable);
+        runnableStarted(DeindexingFileCheck);
+    }
+
     if (m_checkUnindexedFiles
       && !m_indexerStates.contains(NewFiles)
       && !m_indexerStates.contains(UnindexedFileCheck)) {
@@ -205,6 +217,13 @@
     return m_timeEstimator.calculateTimeLeft(m_provider.size());
 }
 
+void FileIndexScheduler::updateIndex()
+{
+    m_purgeDeindexableFiles = true;
+    m_checkUnindexedFiles = true;
+    scheduleIndexing();
+}
+
 void FileIndexScheduler::checkUnindexedFiles()
 {
     m_checkUnindexedFiles = true;
diff --git a/src/file/indexcleaner.cpp b/src/file/indexcleaner.cpp
--- a/src/file/indexcleaner.cpp
+++ b/src/file/indexcleaner.cpp
@@ -19,6 +19,7 @@
 
 #include "indexcleaner.h"
 #include "fileindexerconfig.h"
+#include "storagedevices.h"
 
 #include "database.h"
 #include "transaction.h"
@@ -50,8 +51,9 @@
         }
 
         QString url = tr.documentUrl(id);
+        QFile file(url);
 
-        if (!QFile::exists(url)) {
+        if (!file.exists() && file.symLinkTarget().isEmpty()) {
             qDebug() << "not exists: " << url;
             return true;
         }
@@ -71,10 +73,19 @@
         return false;
     };
 
-    const auto includeFolders = m_config->includeFolders();
-    for (const QString& folder : includeFolders) {
-        quint64 id = filePathToId(QFile::encodeName(folder));
-        tr.removeRecursively(id, shouldDelete);
+    for (const auto& device: m_config->storageDevices()->allMedia()) {
+        if (!device.isMounted()) {
+            qDebug() << "skipping device:" << device.udi();
+        } else {
+            QString devicePath(device.mountPath() + QLatin1Char('/'));
+
+            for (const QString& folder : m_config->includeFolders()) {
+                if (folder.startsWith(devicePath)) {
+                    quint64 id = filePathToId(QFile::encodeName(folder));
+                    tr.removeRecursively(id, shouldDelete);
+                }
+            }
+        }
     }
     tr.commit();
 
diff --git a/src/file/indexerstate.h b/src/file/indexerstate.h
--- a/src/file/indexerstate.h
+++ b/src/file/indexerstate.h
@@ -34,7 +34,8 @@
         ModifiedFiles,
         XAttrFiles,
         ContentIndexing,
-        UnindexedFileCheck
+        UnindexedFileCheck,
+        DeindexingFileCheck
 };
 
 inline QString stateString(IndexerState state)
@@ -64,6 +65,9 @@
         break;
     case UnindexedFileCheck:
         status = i18n("Checking for unindexed files");
+        break;
+    case DeindexingFileCheck:
+        status = i18n("Checking for deindexable files");
     }
     return status;
 }
diff --git a/src/file/mainhub.cpp b/src/file/mainhub.cpp
--- a/src/file/mainhub.cpp
+++ b/src/file/mainhub.cpp
@@ -42,7 +42,7 @@
     connect(&m_fileWatcher, &FileWatch::indexXAttr, &m_fileIndexScheduler, &FileIndexScheduler::indexXAttrFile);
     connect(&m_fileWatcher, &FileWatch::fileRemoved, &m_fileIndexScheduler, &FileIndexScheduler::handleFileRemoved);
 
-    connect(&m_fileWatcher, &FileWatch::installedWatches, &m_fileIndexScheduler, &FileIndexScheduler::checkUnindexedFiles);
+    connect(&m_fileWatcher, &FileWatch::installedWatches, &m_fileIndexScheduler, &FileIndexScheduler::updateIndex);
 
     connect(QCoreApplication::instance(), &QCoreApplication::aboutToQuit, &m_fileIndexScheduler, &FileIndexScheduler::halt);
 
diff --git a/src/tools/balooctl/main.cpp b/src/tools/balooctl/main.cpp
--- a/src/tools/balooctl/main.cpp
+++ b/src/tools/balooctl/main.cpp
@@ -82,7 +82,7 @@
     parser.addPositionalArgument(QStringLiteral("restart"), i18n("Restart the file indexer"));
     parser.addPositionalArgument(QStringLiteral("suspend"), i18n("Suspend content indexing"));
     parser.addPositionalArgument(QStringLiteral("resume"), i18n("Resume content indexing"));
-    parser.addPositionalArgument(QStringLiteral("check"), i18n("Check for any unindexed files and index them"));
+    parser.addPositionalArgument(QStringLiteral("check"), i18n("Check for changes in the monitored folders"));
     parser.addPositionalArgument(QStringLiteral("index"), i18n("Index the specified files"));
     parser.addPositionalArgument(QStringLiteral("clear"), i18n("Forget the specified files"));
     parser.addPositionalArgument(QStringLiteral("config"), i18n("Modify the Baloo configuration"));
@@ -192,8 +192,8 @@
     }
 
     if (command == QStringLiteral("check")) {
-        schedulerinterface.checkUnindexedFiles();
-        out << "Started search for unindexed files\n";
+        schedulerinterface.updateIndex();
+        out << "Started search for changes in monitored folders\n";
         return 0;
     }