上图就是一棵B+树,每个部分有3个主要概念:物理磁盘块、数据项(蓝色)、指针(红色) 如磁盘块1,包含数据项 17、35,包含指针 P1、P2、P3,P1指向小于17的磁盘块,P2指向在17和35之间的磁盘块,P3指向大于35的磁盘块 真实的数据存于叶子节点中,即 3、5、9、10、13、15、28、29、36、60、75、79、90、99 非叶子节点中并不存放真实数据项,只存放指引搜索方向的数据项,如 17、35 并不真实存在于数据表中 B+树查找过程 如果要查找数据项29 1. 首先会把磁盘块1由磁盘加载到内存,此时发生一次IO 2. 在内存中用二分查找确定29在17和35之间,锁定磁盘块1的P2指针,通过P2指向的磁盘地址,把磁盘块3由磁盘加载到内存,发生第二次IO 3. 29在26和30之间,锁定磁盘块3的P2指针,通过指针加载磁盘块8到内存,发生第三次IO 4. 内存中做二分查找找到29,结束查询 总计三次IO,即可找到目标数据项 3层的B+树可以表示上百万的数据,对查询性能的提高是巨大的