Is éard atá i B-tree ná crann cuardaigh féin-chothromaithe ina bhfuil go leor eochracha i ngach nód agus go leor leanaí aige (fanout ard). Coimeádann sé an crann foluain, ag íoslaghdú an líon léamh dhiosca — sin díreach a bhíonn de dhíth ar bhunachais shonraí agus ar chórais fhaisnéise.
Binary BST over 1,000,000 keys -> height ~20 (20 disk seeks)
B-tree, 100 keys/node -> height ~3 (3 disk seeks)
Each node = one disk block/page read.
[ 17 | 35 ]
/ | \
[4|9|12] [20|28] [40|50|60]
each node packs many keys -> few levels
I B+ tree, bíonn gach luach sna duilleoga agus bíonn na duilleoga nasctha, mar sin siúlann scanainn raoin liosta nasctha duilleoga — iontach do ghrequest ar nós WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Oibríonn | Am | Léamh Dhiosca |
|---|---|---|
| cuardach | O(log n) | O(airde) |
| ionsáint / scrios | O(log n) | O(airde) |
| scan raoin | O(log n + k) | duilleoga seicheamhiúil |
Tá rochtain ar dhiosca agus SSD ildhream níos mall ná cuimhne, mar sin is é líon I/O, ní comparáidí an méadracht atá tábhachtach.
Laghdaíonn fanout ard I/O go mór trí an crann a choimeád ach cupla leibhéal domhain.
Is é seo an fáth gur bhunaithe ar B+ trees a bhíonn beagnach gach innéacs bunachair dhonraí choibhneasa (agus go leor córas faisnéise) seachas ar chrainn cuardaigh dhénártha.
Leabharlann de cheisteanna agallaimh TF le freagraí mionsonraithe — ó Shóisearach go Sinsearach.
Síntiús