概述

?上一篇主要減少了預(yù)處理和簡單索引推薦部分，這篇主要介紹復(fù)雜索引推薦和MCTS的具體實現(xiàn)。

代碼解析

?index_advisor_workload()

??1：復(fù)雜索引推薦

???①：生成原子索引：一條query的所有索引會進(jìn)行1到k的組合C${K \choose n}$，n為索引數(shù)，k為1到n。一個原子索引包含普通索引和聯(lián)合索引。

????①-①：

????①-②:把所有query的索引組合去重后放入atomic_config_total中，is_same_config的判斷依據(jù)是：首先判斷列表的長度是否相等，然后兩個列表的每個元素依次對比（表名，列名，索引類型是否相等），但凡有一個不相等，這兩個列表就不相等。

???②：遍歷每個原子索引，計算增加該原子索引后的cost

???③：基于蒙特卡洛搜索樹推薦索引。用蒙特卡洛方法估算每一種走法的勝率。通過不斷的模擬每一種走法，直至終局，該走法的模擬總次數(shù)N，與勝局次數(shù)W，即可推算出該走法的勝率為 W/N。通過隨機(jī)的對游戲進(jìn)行推演來逐漸建立一棵不對稱的搜索樹的過程。

????③-①:蒙特卡洛搜索樹實現(xiàn)。

????③-①-①：選擇和擴(kuò)展：

????③-①-②：隨機(jī)選擇未執(zhí)行的動作計算獎勵

????③-①-③：回溯：自下而上將模擬的結(jié)果反向傳播到父結(jié)點(diǎn)中

????③-①-④：使用UCB算法，權(quán)衡探索和開發(fā)選擇得分最高的子節(jié)點(diǎn)。

???③：貪婪決策算法推薦索引

?以上就是基于負(fù)載的索引推薦的代碼解析，有一些細(xì)節(jié)被省略了，更細(xì)節(jié)的部分可以去看源碼。前幾天dbmind更新了異常檢測和報警模塊，后面我也會把該模塊的源碼解析更新出來。