Innodb-------Binary Search算法

發(fā)布時(shí)間：2020-07-19 02:45:25 來源：網(wǎng)絡(luò) 閱讀：1204 作者：asd1123509133 欄目：MySQL數(shù)據(jù)庫

1. 背景

? ? * Binary Search(二分查找法)也稱為折半查找法，用來查找一組有序記錄數(shù)組中某一項(xiàng)記錄。

? ? * 其基本思想是：將記錄按有序化(遞增或遞減)排列

? ? * 查找過程中用跳躍式方式查找。

2. 優(yōu)點(diǎn)

? ? *?比較次數(shù)少

? ? *?查找速度快

? ? *?平均性能好

? ? *?占用系統(tǒng)內(nèi)存較少

3. 缺點(diǎn)

? ? * 數(shù)據(jù)源必須有序(遞增或遞減)

? ? *?插入刪除困難

4. 例子

? ? 例如對(duì)于[5、10、19、21、31、37、42、48、50、52]這十個(gè)數(shù)，從中查找48這條記錄，如圖

Innodb-------Binary Search算法

? ? 從圖中可以看出，3次就找到了48這個(gè)數(shù)。

? ? 如果是順序查找，則需要8次。

? ? 因此二分查找法的效率比順序查找法要好(平均來說)。

? ? 順序查找平均次數(shù)為：(1+2+3+4+5+6+7+8+9+10)/10=5.5次

? ? 二分查找平均次數(shù)為：(4+3+2+4+3+1+4+3+2+3)/10 = 2.9次

向AI問一下細(xì)節(jié)

猜你喜歡