很可惜 T 。T 您現(xiàn)在還不是作者身份，不能自主發(fā)稿哦～
如有投稿需求，請(qǐng)把文章發(fā)送到郵箱tougao@appcpx.com，一經(jīng)錄用會(huì)有專人和您聯(lián)系
咨詢?nèi)绾纬蔀榇河鹱髡哒?qǐng)聯(lián)系：鳥(niǎo)哥筆記小羽毛（ngbjxym）
這是彭文華的第163篇原創(chuàng)
今天是初三，恰逢情人節(jié)，也沒(méi)提前準(zhǔn)備啥禮物，就陪媳婦回娘家探親。老丈人家一堆的小朋友，非常熱鬧。
我家娃是個(gè)孩子王，往年都用暴力征服小朋友，今年居然動(dòng)腦筋了。他給一堆孩子出了一個(gè)題，是這樣的：
隨便來(lái)一個(gè)小朋友，心里想一個(gè)1-1000的數(shù)，他通過(guò)10個(gè)問(wèn)題，猜出心中的那個(gè)數(shù)是多少。如果10個(gè)問(wèn)題問(wèn)完，猜中了，就得給他捶背5分鐘。
過(guò)年做客么，除了聊天也沒(méi)啥事，我就在旁邊觀察了半天，發(fā)現(xiàn)我家娃用一招搞定了所有小朋友，不僅享受了很久的“捶背”服務(wù)，還成為新晉“孩子王”。
他用的是啥招呢？其實(shí)是一個(gè)非常簡(jiǎn)單的方法-二分法。有些算法基礎(chǔ)比較好的同學(xué)已經(jīng)知道怎么回事了。你聽(tīng)我慢慢講。
對(duì)了，我在挑戰(zhàn)春節(jié)不打烊，每天都分享原創(chuàng)文章，歡迎加我個(gè)人微信：shirenpengwh，加入催更群，小鞭子催我快快寫(xiě)稿
二分查找
二分查找，也叫折半查找，是一個(gè)非常高效的查找方法。簡(jiǎn)單來(lái)說(shuō)，就是通過(guò)多次減半查找，縮小數(shù)據(jù)范圍，最終找到想找的那個(gè)數(shù)據(jù)。
就拿我兒子的那道題來(lái)說(shuō)，目標(biāo)是在10個(gè)問(wèn)題之后，準(zhǔn)確得知你心中想的那個(gè)1-1000之間的那個(gè)數(shù)字，具體操作方法如下：
問(wèn)題1：這個(gè)數(shù)字是大于500對(duì)嗎？無(wú)論答案是“是”還是“否”，都直接排除掉另外500個(gè)數(shù)字，這是第一次“折半”。咱假設(shè)是小于500.
問(wèn)題2：這個(gè)數(shù)字是在1-250之間對(duì)嗎？同樣，無(wú)論答案是什么，都再次排除掉250個(gè)數(shù)字。這是第二次“折半”。
以此類推，10個(gè)問(wèn)題問(wèn)完，答案自然就出來(lái)了。為了節(jié)省篇幅，我編了一個(gè)excel表，你應(yīng)該能快速看明白。
因?yàn)榛卮鹗鞘裁炊紵o(wú)所謂，我們都可以排除掉相應(yīng)數(shù)量的錯(cuò)誤答案。經(jīng)過(guò)10個(gè)問(wèn)題之后，就能排除999個(gè)答案，剩下那個(gè)自然就是正確答案了。
如果你數(shù)字足夠敏感，就會(huì)發(fā)現(xiàn)，其實(shí)1000這個(gè)數(shù)字其實(shí)可以擴(kuò)展到1024，也一樣能達(dá)到效果，因?yàn)?的10次方就等于1024啊。1024對(duì)半砍10次，就能確定某個(gè)數(shù)字。
這個(gè)回答好像很簡(jiǎn)單？其實(shí)這是非常厲害的方法。一般人會(huì)怎么做？基本上就一個(gè)方法：瞎猜。因?yàn)榱硗庖粋€(gè)方法基本沒(méi)人用，就是從1開(kāi)始，挨個(gè)猜，就是窮舉法，感覺(jué)太笨了。
但是這兩種方法效率都非常慢，因此非常不推薦。其實(shí)按個(gè)猜的這種窮舉法，其實(shí)就是數(shù)據(jù)庫(kù)中的全表掃描，速度自然是非常非常慢的。
而二分法這種思想，拓展一下就是跳表，也就是索引的核心思想。
跳表其實(shí)就是一個(gè)不斷問(wèn)數(shù)據(jù)庫(kù)問(wèn)題的方法，能夠快速鎖定數(shù)據(jù)所在的位置。
你看，這個(gè)跳表跟我兒子玩的那個(gè)猜數(shù)字的游戲多像啊？其實(shí)就是因?yàn)楹诵乃枷胧且粯拥?。?duì)于海量數(shù)據(jù)，我們只需要對(duì)序號(hào)進(jìn)行多層級(jí)的“折半查找”，就能快速鎖定數(shù)據(jù)所在的地方，而不用挨個(gè)找。
不過(guò)我這張圖畫(huà)的不好，有人會(huì)問(wèn)，這從1開(kāi)始找不是第二條就找到了么？咱看圖看意哈，這個(gè)思想可以搞定千萬(wàn)、億級(jí)甚至更多數(shù)據(jù)的快速查找和鎖定。
這種方法耗費(fèi)的存儲(chǔ)量也很小，因?yàn)橹恍枰鎯?chǔ)id就行，而且層級(jí)越往上，存儲(chǔ)的數(shù)據(jù)就越少。
這個(gè)解決方案其實(shí)就是我們說(shuō)的“索引”。而那么多問(wèn)題其實(shí)就是一級(jí)索引、二級(jí)索引、三級(jí)索引。
當(dāng)然，在數(shù)據(jù)庫(kù)實(shí)際的使用中，還會(huì)遇到各種問(wèn)題，比如插入新數(shù)據(jù)了，刪掉老數(shù)據(jù)了。當(dāng)某個(gè)老區(qū)域中的數(shù)據(jù)插入過(guò)多之后，這個(gè)區(qū)域的索引就不好使了，查詢到這邊的時(shí)候速度就會(huì)變慢。這就是插入、刪除數(shù)據(jù)頻繁的表，我們需要過(guò)一些時(shí)間就重建索引的原因。
跳表思想廣泛應(yīng)用于各個(gè)領(lǐng)域，當(dāng)然應(yīng)用最多的當(dāng)然是數(shù)據(jù)領(lǐng)域了。別的不說(shuō)，關(guān)系型數(shù)據(jù)庫(kù)的索引就是跳表思想，MySQL面試題中肯定有這個(gè)的。算法題里也有大量跳表思想的題，實(shí)現(xiàn)方式也很簡(jiǎn)單，寫(xiě)個(gè)循環(huán)，不斷/2就行了。
熟悉Redis的同學(xué)，應(yīng)該知道對(duì)有序集合額（zset）的操作中國(guó)，就有按照范圍區(qū)間查找元素的操作，這就是用跳表搞定的，效率非常高。
另外，HBase MemStore的內(nèi)部存儲(chǔ)就是用跳表思想搞定的。HBase實(shí)時(shí)寫(xiě)數(shù)據(jù)會(huì)先扔到內(nèi)存里，然后再通過(guò)flush機(jī)制刷寫(xiě)到磁盤(pán)，生成StoreFile有序文件。跳表天然有序，并且查找、插入、刪除性能都非常高，HBase當(dāng)然就拿來(lái)就用了。這也是HBase查詢效率超高的原因之一。
如果你想搞定女朋友，也可以用這個(gè)方法，讓她心中想一個(gè)數(shù)字，然后用二分法，十次鎖定答案，然后你就可以嘿嘿嘿...
二分法進(jìn)一步擴(kuò)展，就是跳表思想，對(duì)一個(gè)順序鏈表提取多層索引，通過(guò)少量存儲(chǔ)消耗，極強(qiáng)的增加查詢效率。二分法30層就可以覆蓋10億條數(shù)據(jù)，這個(gè)量級(jí)就很恐怖了。
跳表思想廣泛應(yīng)用于各種查詢領(lǐng)域，傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)的索引就用了跳表思想。內(nèi)存（緩存）數(shù)據(jù)庫(kù)Redis也用了跳表實(shí)現(xiàn)查找元素的操作。大數(shù)據(jù)組件中專攻快速查詢的HBase組件的MemStore內(nèi)部存儲(chǔ)也用的跳表思想，這也是HBase查詢速度超遠(yuǎn)的原因之一。
今天的分享就是這樣。歡迎大家加我個(gè)人微信號(hào)：shirenpengwh ，一起探討大數(shù)據(jù)、數(shù)據(jù)分析相關(guān)知識(shí)。每天分享一篇原創(chuàng)內(nèi)容給大家，我們一起學(xué)習(xí)，共同進(jìn)步。
配合以下文章享受更佳
【詳解】 | MapReduce環(huán)形緩沖區(qū)
【詳解】 | Flink的Checkpoints機(jī)制詳解
【干貨】架構(gòu)師帶你細(xì)細(xì)的捋一遍MapReduce全流程
【全解】一口氣說(shuō)完MR、Storm、Spark、SparkStreaming和Flink
本文為作者獨(dú)立觀點(diǎn)，不代表鳥(niǎo)哥筆記立場(chǎng)，未經(jīng)允許不得轉(zhuǎn)載。
《鳥(niǎo)哥筆記版權(quán)及免責(zé)申明》 如對(duì)文章、圖片、字體等版權(quán)有疑問(wèn)，請(qǐng)點(diǎn)擊 反饋舉報(bào)
我們致力于提供一個(gè)高質(zhì)量?jī)?nèi)容的交流平臺(tái)。為落實(shí)國(guó)家互聯(lián)網(wǎng)信息辦公室“依法管網(wǎng)、依法辦網(wǎng)、依法上網(wǎng)”的要求，為完善跟帖評(píng)論自律管理，為了保護(hù)用戶創(chuàng)造的內(nèi)容、維護(hù)開(kāi)放、真實(shí)、專業(yè)的平臺(tái)氛圍，我們團(tuán)隊(duì)將依據(jù)本公約中的條款對(duì)注冊(cè)用戶和發(fā)布在本平臺(tái)的內(nèi)容進(jìn)行管理。平臺(tái)鼓勵(lì)用戶創(chuàng)作、發(fā)布優(yōu)質(zhì)內(nèi)容，同時(shí)也將采取必要措施管理違法、侵權(quán)或有其他不良影響的網(wǎng)絡(luò)信息。
一、根據(jù)《網(wǎng)絡(luò)信息內(nèi)容生態(tài)治理規(guī)定》《中華人民共和國(guó)未成年人保護(hù)法》等法律法規(guī)，對(duì)以下違法、不良信息或存在危害的行為進(jìn)行處理。
1. 違反法律法規(guī)的信息，主要表現(xiàn)為：
1)反對(duì)憲法所確定的基本原則；
2)危害國(guó)家安全，泄露國(guó)家秘密，顛覆國(guó)家政權(quán)，破壞國(guó)家統(tǒng)一，損害國(guó)家榮譽(yù)和利益；
3)侮辱、濫用英烈形象，歪曲、丑化、褻瀆、否定英雄烈士事跡和精神，以侮辱、誹謗或者其他方式侵害英雄烈士的姓名、肖像、名譽(yù)、榮譽(yù)；
4)宣揚(yáng)恐怖主義、極端主義或者煽動(dòng)實(shí)施恐怖活動(dòng)、極端主義活動(dòng)；
5)煽動(dòng)民族仇恨、民族歧視，破壞民族團(tuán)結(jié)；
6)破壞國(guó)家宗教政策，宣揚(yáng)邪教和封建迷信；
7)散布謠言，擾亂社會(huì)秩序，破壞社會(huì)穩(wěn)定；
8)宣揚(yáng)淫穢、色情、賭博、暴力、兇殺、恐怖或者教唆犯罪；
9)煽動(dòng)非法集會(huì)、結(jié)社、游行、示威、聚眾擾亂社會(huì)秩序；
10)侮辱或者誹謗他人，侵害他人名譽(yù)、隱私和其他合法權(quán)益；
11)通過(guò)網(wǎng)絡(luò)以文字、圖片、音視頻等形式，對(duì)未成年人實(shí)施侮辱、誹謗、威脅或者惡意損害未成年人形象進(jìn)行網(wǎng)絡(luò)欺凌的；
12)危害未成年人身心健康的；
13)含有法律、行政法規(guī)禁止的其他內(nèi)容；
2. 不友善：不尊重用戶及其所貢獻(xiàn)內(nèi)容的信息或行為。主要表現(xiàn)為：
1)輕蔑：貶低、輕視他人及其勞動(dòng)成果；
2)誹謗：捏造、散布虛假事實(shí)，損害他人名譽(yù)；
3)嘲諷：以比喻、夸張、侮辱性的手法對(duì)他人或其行為進(jìn)行揭露或描述，以此來(lái)激怒他人；
4)挑釁：以不友好的方式激怒他人，意圖使對(duì)方對(duì)自己的言論作出回應(yīng)，蓄意制造事端；
5)羞辱：貶低他人的能力、行為、生理或身份特征，讓對(duì)方難堪；
6)謾罵：以不文明的語(yǔ)言對(duì)他人進(jìn)行負(fù)面評(píng)價(jià)；
7)歧視：煽動(dòng)人群歧視、地域歧視等，針對(duì)他人的民族、種族、宗教、性取向、性別、年齡、地域、生理特征等身份或者歸類的攻擊；
8)威脅：許諾以不良的后果來(lái)迫使他人服從自己的意志；
3. 發(fā)布垃圾廣告信息：以推廣曝光為目的，發(fā)布影響用戶體驗(yàn)、擾亂本網(wǎng)站秩序的內(nèi)容，或進(jìn)行相關(guān)行為。主要表現(xiàn)為：
1)多次發(fā)布包含售賣(mài)產(chǎn)品、提供服務(wù)、宣傳推廣內(nèi)容的垃圾廣告。包括但不限于以下幾種形式：
2)單個(gè)帳號(hào)多次發(fā)布包含垃圾廣告的內(nèi)容；
3)多個(gè)廣告帳號(hào)互相配合發(fā)布、傳播包含垃圾廣告的內(nèi)容；
4)多次發(fā)布包含欺騙性外鏈的內(nèi)容，如未注明的淘寶客鏈接、跳轉(zhuǎn)網(wǎng)站等，誘騙用戶點(diǎn)擊鏈接
5)發(fā)布大量包含推廣鏈接、產(chǎn)品、品牌等內(nèi)容獲取搜索引擎中的不正當(dāng)曝光；
6)購(gòu)買(mǎi)或出售帳號(hào)之間虛假地互動(dòng)，發(fā)布干擾網(wǎng)站秩序的推廣內(nèi)容及相關(guān)交易。
7)發(fā)布包含欺騙性的惡意營(yíng)銷(xiāo)內(nèi)容，如通過(guò)偽造經(jīng)歷、冒充他人等方式進(jìn)行惡意營(yíng)銷(xiāo)；
8)使用特殊符號(hào)、圖片等方式規(guī)避垃圾廣告內(nèi)容審核的廣告內(nèi)容。
4. 色情低俗信息，主要表現(xiàn)為：
1)包含自己或他人性經(jīng)驗(yàn)的細(xì)節(jié)描述或露骨的感受描述；
2)涉及色情段子、兩性笑話的低俗內(nèi)容；
3)配圖、頭圖中包含庸俗或挑逗性圖片的內(nèi)容；
4)帶有性暗示、性挑逗等易使人產(chǎn)生性聯(lián)想；
5)展現(xiàn)血腥、驚悚、殘忍等致人身心不適；
6)炒作緋聞、丑聞、劣跡等；
7)宣揚(yáng)低俗、庸俗、媚俗內(nèi)容。
5. 不實(shí)信息，主要表現(xiàn)為：
1)可能存在事實(shí)性錯(cuò)誤或者造謠等內(nèi)容；
2)存在事實(shí)夸大、偽造虛假經(jīng)歷等誤導(dǎo)他人的內(nèi)容；
3)偽造身份、冒充他人，通過(guò)頭像、用戶名等個(gè)人信息暗示自己具有特定身份，或與特定機(jī)構(gòu)或個(gè)人存在關(guān)聯(lián)。
6. 傳播封建迷信，主要表現(xiàn)為：
1)找人算命、測(cè)字、占卜、解夢(mèng)、化解厄運(yùn)、使用迷信方式治?。?br /> 2)求推薦算命看相大師；
3)針對(duì)具體風(fēng)水等問(wèn)題進(jìn)行求助或咨詢；
4)問(wèn)自己或他人的八字、六爻、星盤(pán)、手相、面相、五行缺失，包括通過(guò)占卜方法問(wèn)婚姻、前程、運(yùn)勢(shì)，東西寵物丟了能不能找回、取名改名等；
7. 文章標(biāo)題黨，主要表現(xiàn)為：
1)以各種夸張、獵奇、不合常理的表現(xiàn)手法等行為來(lái)誘導(dǎo)用戶；
2)內(nèi)容與標(biāo)題之間存在嚴(yán)重不實(shí)或者原意扭曲；
3)使用夸張標(biāo)題，內(nèi)容與標(biāo)題嚴(yán)重不符的。
8.「飯圈」亂象行為，主要表現(xiàn)為：
1)誘導(dǎo)未成年人應(yīng)援集資、高額消費(fèi)、投票打榜
2)粉絲互撕謾罵、拉踩引戰(zhàn)、造謠攻擊、人肉搜索、侵犯隱私
3)鼓動(dòng)「飯圈」粉絲攀比炫富、奢靡享樂(lè)等行為
4)以號(hào)召粉絲、雇用網(wǎng)絡(luò)水軍、「養(yǎng)號(hào)」形式刷量控評(píng)等行為
5)通過(guò)「蹭熱點(diǎn)」、制造話題等形式干擾輿論，影響傳播秩序
9. 其他危害行為或內(nèi)容，主要表現(xiàn)為：
1)可能引發(fā)未成年人模仿不安全行為和違反社會(huì)公德行為、誘導(dǎo)未成年人不良嗜好影響未成年人身心健康的；
2)不當(dāng)評(píng)述自然災(zāi)害、重大事故等災(zāi)難的；
3)美化、粉飾侵略戰(zhàn)爭(zhēng)行為的；
4)法律、行政法規(guī)禁止，或可能對(duì)網(wǎng)絡(luò)生態(tài)造成不良影響的其他內(nèi)容。
二、違規(guī)處罰
本網(wǎng)站通過(guò)主動(dòng)發(fā)現(xiàn)和接受用戶舉報(bào)兩種方式收集違規(guī)行為信息。所有有意的降低內(nèi)容質(zhì)量、傷害平臺(tái)氛圍及欺凌未成年人或危害未成年人身心健康的行為都是不能容忍的。
當(dāng)一個(gè)用戶發(fā)布違規(guī)內(nèi)容時(shí)，本網(wǎng)站將依據(jù)相關(guān)用戶違規(guī)情節(jié)嚴(yán)重程度，對(duì)帳號(hào)進(jìn)行禁言 1 天、7 天、15 天直至永久禁言或封停賬號(hào)的處罰。當(dāng)涉及欺凌未成年人、危害未成年人身心健康、通過(guò)作弊手段注冊(cè)、使用帳號(hào)，或者濫用多個(gè)帳號(hào)發(fā)布違規(guī)內(nèi)容時(shí)，本網(wǎng)站將加重處罰。
三、申訴
隨著平臺(tái)管理經(jīng)驗(yàn)的不斷豐富，本網(wǎng)站出于維護(hù)本網(wǎng)站氛圍和秩序的目的，將不斷完善本公約。
如果本網(wǎng)站用戶對(duì)本網(wǎng)站基于本公約規(guī)定做出的處理有異議，可以通過(guò)「建議反饋」功能向本網(wǎng)站進(jìn)行反饋。
(規(guī)則的最終解釋權(quán)歸屬本網(wǎng)站所有)