b樹、b+樹：關系型數據庫核心存儲結構
1、為什么磁盤數據存儲結構用B+樹、而不用紅黑樹
?磁盤每次讀取不是讀一個節(jié)點、是返回一頁數據。
紅黑樹每次遍歷一個節(jié)點排除一半數據。
B樹通常映射相鄰的磁盤頁數據。4K
mysql索引一個節(jié)點隱射16k故而映射4倍，故可以存儲更多信息。
紅黑樹相對平衡，平衡黑節(jié)點故搜索時間復雜度不穩(wěn)定。而B+樹絕對平衡搜索穩(wěn)定，數據都在葉子節(jié)點方便范圍查詢，遍歷。
B+樹高度更低，層次越到磁盤io次數就越多。如何降低：減少次數，化為順序IO。
時間輪：海量定時任務檢測
多線程環(huán)境下定時器設計
定時器：
1、以時間序來組織 按照過期時間排序數據結構。
如使用：紅黑樹 nginx、workfllow
????????????????最小堆? libuv、go? ：當前時間與最小過期節(jié)點比較
2、以執(zhí)行序來組織
兩個結構：
a、指針數組
b、時間指針
一個規(guī)則：
時間指針按照最小時間精度移動
1s size = 16? 一秒移動一次，添加過期時間移動到哪，就把鏈表數據都取出來執(zhí)行。
由于時間精度和最大時間范圍?
多層級時間輪：支持更大時間范圍
?比如：鐘表秒針精確存儲，分針時針稀疏存儲
每個小時，都會有時針層級的任務映射到分針層級...
?多線程 加鎖 并發(fā)度
紅黑樹 時間復雜度logN時間越長，等待時間越長。
1、時間輪O（1）時間短
2、加鎖粒度?
跳表:高并發(fā)有序存儲 redis
概率型數據結構logN? 二分查找 每次比較排除一半節(jié)點
多層級有序鏈表??文章來源：http://www.zghlxwxcb.cn/news/detail-679285.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-679285.html
到了這里，關于b樹/b+樹、時間輪、跳表、LSM-Tree的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
