为什么使用 B-Tree(B+Tree)

由于机械磁盘的特性,磁盘的存取速度比主存慢很多,往往是其的 几百分分之一,因此为了提高效率及减少磁盘 I/O,往往每次读取都会预读,即使读取一个字节,也需要从此往后读取一定长度的数据放入内存,预读的长度一般为页(page)的整数倍。而 B Tree 之所以高效,根据 B-Tree 的定义,可知检索一次最多需要访问 h 个节点,一次检索最多需要 h-1 次 I/O,渐进复杂度为 O(h) = O(logdN)。一般实际应用中,出度 d 是非常大的数字,通常超过 100, 因此 h 非常小(通常不超过3),所以 B-Tree 作为索引结构效率非常高

为什么使用 B-Tree(B+Tree)

comments powered by Disqus

Tags

abcs accept acid activemq affinity algorithm allocation android array async aws b+tree b-tree backoff benchmark best-practices bfs big-o bigquery bind bitcount blog break broker bubble buffer cache cap cert cgroups channel citus class classmethod closure closures cluster concurrency config consumer container context cookie cors crawler cronjob csrf ctr data-science data-structure database datadog dataflow datascience decorator defer dfs distributed django dns docker double-shipping drf ecosia elastic-search enumerate epoll errgroup escaping extra fabric2 facebook-pixel financial-report flask flutter forward-proxy freelance frontend frp garbage-collector gc gcp generator gesture get gil git golang goroutine graphql ha handbook haproxy hash hash-slot hashring hashtable hpa http http-auth http-proxy http_proxy https index init innodb instagram intergration interview ios javascript jinja2 jobboard jwt k8s kafka kibana kqueue label lambda layer4 layer7 lean levels.io linked-list linux list listen loadbalancer logs long-tail lru marketing master matplotlib memory merge metaclass metaprogramming metrics metrics-server microservices mitm mobile model mq myisam mysql namespace nat netflix network network-extension nginx nodejs nomad nosql npm oodesign openssl optimization orm osi pandas parallelism paramiko parkinglot patroni permission pg pipeline pixelme post postgresql postresql prefetch_related prerender private-key process proxy proxycommand put pvm python queue rabbitmq rbac react-native reactive reactjs rebase redis redis-cluster replication resource rest restfulapi retargeting retry revenue reverse-proxy rocketmq rsa rxswift saas scaffold scaleable search-engine security select seo serverless service session set shadosocks shadowsocks shard sharding shell shopify sigint signal sigterm slack slave slow-query sniper sns socket socks5 source-code spa sql sqlalchemy sqs ssh ssl ssl-pinning stack startup state stateful stateless staticmethod string struct swift swiftui switch syscall system-design systemctl tcp tcp-proxy thread tmpreaper token traefik trustkit tunning type typeform udp userdefaults variable vc voidcallback vpn vuejs weak web web-development where widget yarn zset 削峰 宽索引 异步 看源码学-golang 窄索引 解耦 跨域 跳板机



Archives

2020 (1)
2019 (157)