為什麼要有二叉樹，假如有一個數字列表，我想找出一個數字，直接拿出來就可以了。但是計算機不會，它很笨，這麼簡單的問題它都不會，它蠢蛋挨個的看，直到最終找出我要的數字，這個蠢辦法太費力了，於是它想出一個演算法，就是二叉樹查詢法，這樣它就快點了不必挨個的看了(掃表)。不知道我的理解對不對。還有為什麼它這麼笨，是不是它只有比較數字大小的指令，而沒有像人一樣看一眼，就知道有沒有，直接就拿出目標數字的能力。求解惑。
mysql的主鍵索引就是二叉樹好像，索引上查詢也比較快，原因就是沒有索引會掃整個表是嗎。
比如，我在一個查詢id為1的文章，而這個欄位沒有索引的話，mysql會掃表，從0開始，直到找到位置。是這樣嗎？為什麼它這麼蠢，不能直接拿到我要的行呢？
回覆列表
-
1 # 此生唯一
-
2 # 西域巡檢司
二叉樹是資料遍歷用時最少的的演算法結構，如果資料庫中的資料只有一兩個，直接比較就會快速找出你要的資料，但是資料如果是成百上千呢？不是說電腦蠢，給你一張有一千個大小不同的數字，你需要多長時間才能找出最小的數字？對於簡單的資料而言，計算查詢都很簡單，對於複雜的資料呢？既然是資料庫，那就不可能只是簡單的幾組資料，而二叉樹的遍歷是對龐大的資料而言的，它比冒泡演算法、遞迴演算法、迭代演算法以及圖的遍歷來說，較為快速，就你的描述來看，資料庫，你還沒有完全的搞懂，你還需更多的理論知識！
看了題目，覺得很好！看了題目描述，忍不住想打人。。。
什麼叫做像人一樣，直接就拿出來？百萬級，千萬級的數量你怎麼看一下就拿出來？你能做到秒級甚至毫秒級拿出資料？
我先吃顆降火藥，然後這個題目我分兩個來答:
1，為什麼二叉樹效率高？
我們都知道，現在是一個數據爆炸的時代，每天產生的資料以PB級計量，而查詢資料就成了最基本的需求！
原始的查資料的方法就是順序的比較，直到找到符合條件的資料，比如說1073741824（十億多）這麼多的資料量，順序比較然後查找出來的次數平均為這個數的一半也就是五億多次，而使用二叉樹查詢只需要log以2為底1073741824的對數，也就是30次，換句話說你只需要比較30次就可以拿到你想要的資料，五億次和30次，你說怎麼選？我們來看下兩種方式的查詢效率，數學表達和大O表示法
順序查詢:y＝x/2; O(N);
二叉樹查詢:y＝2^N;O(log2(n))
可以看到二叉樹的效率為對數級別，在數學效率圖上表示，就是數量級越大，效率越明顯（斜率低）！
當然，二叉樹只是一個普通的樹結構，還有紅黑樹，B樹等特殊二叉樹！本文因為篇幅原因暫且不提！
2，為什麼資料庫要建索引以提高效率？
資料庫建索引，其實是一種以空間換時間的方式，流量時代，速度為王！
看個栗子:
加入一張表，每行的資料大約100k，而主鍵的大小為0.1K，在主鍵上建立索引之後，除了原始資料，還需要維護一份索引資料，比如資料是100萬，那麼原始資料為10萬m，也就是1000G，而索引大小為1G，查詢索引的速度只有原始資料的1/1000，然後從索引中取出對應的原始資料所在的地址，直接定址得到資料，可以看出用少量的索引資料換得了查詢效率的大幅度提升！
①，所以資料庫建索引，基本是必選的最佳化策略！
②，索引並不是越多越好，比如你選擇了每個欄位都建索引，相當於你每一行的資料都額外維護了一份，而且加上定址地址等，資料量變為原來的2倍以上，除此之外，每次新建資料都要重新維護索引，大量的索引絕對會把系統磨死。。。
④，索引方式有b＋，hash等很多種方式，根據儲存引擎和資料型別選擇合適的索引！
關於二叉樹和索引只能粗略的講解到這了，更為詳細的講解改天挑時間再說吧，敬請關注。。。