{"action":"created","issue":{"url":"https://api.github.com/repos/carney520/notepad/issues/7","repository_url":"https://api.github.com/repos/carney520/notepad","labels_url":"https://api.github.com/repos/carney520/notepad/issues/7/labels{/name}","comments_url":"https://api.github.com/repos/carney520/notepad/issues/7/comments","events_url":"https://api.github.com/repos/carney520/notepad/issues/7/events","html_url":"https://github.com/carney520/notepad/issues/7","id":301638907,"number":7,"title":"数据库索引","user":{"login":"carney520","id":6149975,"avatar_url":"https://avatars2.githubusercontent.com/u/6149975?v=4","gravatar_id":"","url":"https://api.github.com/users/carney520","html_url":"https://github.com/carney520","followers_url":"https://api.github.com/users/carney520/followers","following_url":"https://api.github.com/users/carney520/following{/other_user}","gists_url":"https://api.github.com/users/carney520/gists{/gist_id}","starred_url":"https://api.github.com/users/carney520/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/carney520/subscriptions","organizations_url":"https://api.github.com/users/carney520/orgs","repos_url":"https://api.github.com/users/carney520/repos","events_url":"https://api.github.com/users/carney520/events{/privacy}","received_events_url":"https://api.github.com/users/carney520/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2018-03-02T03:12:02Z","updated_at":"2018-03-02T06:09:23Z","closed_at":null,"author_association":"OWNER","body":"索引是用来提交获取数据效率的数据结构。目前而言数据库是不完美的，所以需要我们去关心性能的优化，以便在不同的查询场景选择合适的优化方案(或者说索引类型)。\r\n\r\n## 1. 查询算法与数据结构\r\n\r\n### 1.1 顺序查找(linear search)\r\n这是最简单也是最低效的查找方式。所有数据查找整个表，即使这个数据不存在。\r\n在没有添加索引时，数据库一般是使用这个方式进行检索的。\r\n> 算法复杂度： O(n)\r\n\r\n### 1.2 二分查找(binary search)\r\n二分查找的原理是从一个有序数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。\r\n\r\n二叉查找树也使用二分查找的方法。如红黑树， AVL树，其搜索效率和树的深度有关。\r\n> 算法复杂度： O(logn)\r\n\r\n### 1.3 哈希表查找\r\n通过哈希函数可以将一个key值映射一个具体的存储位置， 算法复杂度是O(n)\r\n\r\n### 1.4 分块查找\r\n这是对顺序查找和二分查找的一种改进方法。 又称为索引顺序查找。其算法思想是将n个数据元素”按块有序”划分为m块（m ≤ n）。分块查找由于只要求索引表是有序的，对块内节点没有排序要求；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，依次类推。 \r\n性能介于顺序查找和二分查找之间，且不要求数据有序。但是维护多个块也许要一定的成本。\r\n\r\n### 1.5 B树\r\n查找树的效率跟树的深度相关，压缩树的深度， 第一种方式是使其平衡， 第二种方式是采用多叉树。这就产生了平衡多叉树的思想。\r\n\r\n#### 1.5.1 B树\r\nB树（Balance Tree）是一种平衡多路查找树， 如：\r\n\r\n![image](https://user-images.githubusercontent.com/6149975/36885174-626bb8b0-1e20-11e8-9d95-b74bca10d553.png)\r\n\r\nB树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统\r\n\r\n#### 1.5.2 B+树\r\n这是B树的变种， B-Tree相比，B+Tree有以下不同点：\r\n* 每个节点的指针上限为2d而不是2d+1；\r\n* 内节点不存储data，只存储key；\r\n* 叶子节点不存储指针；\r\n一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。做这个优化的目的是为了提高区间范围访问的性能。 \r\n\r\n![image](https://user-images.githubusercontent.com/6149975/36885464-07bc54cc-1e22-11e8-93d3-6e90c9823ab9.png)\r\n\r\n\r\n## 参考文献\r\n* [数据库索引原理及优化](https://yq.aliyun.com/articles/65126)\r\n* [七大查找算法](http://www.cnblogs.com/maybe2030/p/4715035.html#top)"},"comment":{"url":"https://api.github.com/repos/carney520/notepad/issues/comments/369831137","html_url":"https://github.com/carney520/notepad/issues/7#issuecomment-369831137","issue_url":"https://api.github.com/repos/carney520/notepad/issues/7","id":369831137,"user":{"login":"carney520","id":6149975,"avatar_url":"https://avatars2.githubusercontent.com/u/6149975?v=4","gravatar_id":"","url":"https://api.github.com/users/carney520","html_url":"https://github.com/carney520","followers_url":"https://api.github.com/users/carney520/followers","following_url":"https://api.github.com/users/carney520/following{/other_user}","gists_url":"https://api.github.com/users/carney520/gists{/gist_id}","starred_url":"https://api.github.com/users/carney520/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/carney520/subscriptions","organizations_url":"https://api.github.com/users/carney520/orgs","repos_url":"https://api.github.com/users/carney520/repos","events_url":"https://api.github.com/users/carney520/events{/privacy}","received_events_url":"https://api.github.com/users/carney520/received_events","type":"User","site_admin":false},"created_at":"2018-03-02T06:09:23Z","updated_at":"2018-03-02T06:09:23Z","author_association":"OWNER","body":"## 索引类型"}}
{"actor":{"display_login":"carney520"}}