データベース深堀りガイド①

# はじめに
この記事は[Yamato Advent Calendar 2023](https://qiita.com/advent-calendar/2023/yamato) 1日目の記事です。

このAdventCalendarでは、自分自身が気になっている技術やGoのキャッチアップを備忘録として書き殴っていきます。

**個人完走賞**目指して頑張ります!

# 概要

DBって便利ですよね...
DBは様々なシステムに使用されているものだと思います。
自分も今までWebアプリだったりAPIだったりを作る際によくRDBMSを使用してきました。

ただ、簡単なCRUD(select, insert, update, delete)だったり、RDBにおけるリレーションだったり、基礎的な部分はわかるけど、もっともっとDBに対する理解を増やしたい!という意気込みでこの記事を書いています。

これを読めば、あなたもDB中級者くらいにはなれんるんじゃないでしょうか？知らんけど

# DBの種類
DBにも様々な種類がありますよね。
- SQL
- NoSQL
- NewSQL

## SQL
sqlは```structured query language```で、RDBMSを操作するクエリ言語です。
### メリット
- 表形式のデータ
- リレーションによるデータの整合性
- ACIDなトランザクション
ACIDとトランザクションに関しては、明日投稿されるAdventCalendarで書く予定です。

### デメリット
- スキーマレスなデータの扱いが難しい
- スケールがやりにくい

### 代表例
- PostgreSQL
- MySQL
- Aurora
- Alloy


## NoSQL
NoSQLは```not only sql```で非リレーショナルなDBを操作するクエリ言語です。
### メリット
- 非構造化データ
- スキーマレス
- スケーラビリティが高い

### デメリット
- ACIDがSQLほど強くない
- 型制約


### 代表例
- MongoDB
- DynamoDB
- CosmosDB


## NewSQL
NewSQLはリレーショナルデータベース（RDBMS）のトランザクション性と整合性を保持しつつ、分散型システムのスケーラビリティとパフォーマンスを兼ね備えた新しいデータベースシステムです。

### メリット
- ACIDトランザクション
- スケーラビリティが高い

### デメリット
- 非構造化データを扱うことのが難しい

### 代表例
- Google Spanner
- TiDB
- CockroachDB

TiDBかなり興味があって、触ってみたいんですよね。
めちゃくちゃ高いらしいですけど..

https://pingcap.co.jp/tidb-overview/

## インデックス

**インデックス**という言葉を聞いたことがありますか？

### インデックスとは
インデックスは「索引」とも呼ばれたりしますが、テーブル内の特定の列を識別できる値（キー値）と、キー値によって特定された列のデータが格納されている位置を示すポインタで成り立っています。

SQLはインデックスがないとフルスキャンと言って、テーブルのはじめから終わりまでを順に見ていき、特定のデータを見つけます。データ数が少ない場合は大丈夫かもしれませんが、テーブルのレコード数が多くなるほどフルスキャンでは時間がかかってしまいます。

このインデックスを使うことでテーブルすべてのデータを見る必要がなくなるということなんですね。

> Most MySQL indexes (PRIMARY KEY, UNIQUE, INDEX, and FULLTEXT) are stored in B-trees. 

https://dev.mysql.com/doc/refman/5.7/en/mysql-indexes.html

MySQLのほとんどには、**B-tree**と呼ばれる木構造が使用されているそうです。

### B-treeとB+tree
B-treeとB+treeという二つの構造があるようです。違いはなんでしょうか？
B-treeをvisualizeできるサイトを見つけました。

https://www.cs.usfca.edu/~galles/visualization/BTree.html

試しにMaxDegreeを3として、[2,3,5,7,11,13,17,19]のデータで B-treeを作ってみます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2086809/4b4d9a73-451e-5065-9099-aa5e5c28ab77.png)

このようになりました。

次に同じDegreeとデータでB+treeも作ってみます。

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2086809/efb3b2e2-7969-a3f2-f4de-b0ce10b243bd.png)

ほほう

描画してみてわかったのが、
B-treeは**ノードがデータになっている**
B+treeは**データをリーフノードに持っていること**と**末端ノードはポインタで結ばれていること**がわかりますね。

#### B-tree
- 子ノードもデータを持つので、**探索途中でヒットすればレスポンスが早い**。
- mongoDBのインデックスに使用されている。

#### B+tree
- リーフノードがポインタでつながっているので、**範囲検索に強い**
- mysqlのインデックスに使用されている。

こういったデータ構造を駆使してDBの高速化を図っているのですね。

### カーディナリティ
DBのカラムに存在する異なる種類の数のことです。

例えば、DBのカラムにbool型の```isPublished```(公開されたかを判定するフラグ)があったとします。これはbool型なので、値でいうとtrue(1)とfalse(0)の二種類しかありませんよね。これはカーディナリティが低いとなります。

逆に、RDBの**PrimaryKey**のようなデータを一意に特定できるカラムはレコードの数だけ種類があるため、カーディナリティが高いです。

インデックスをつける際には、高いカーディナリティのカラムにインデックスを付与するとクエリ速度が改善される可能性があります。
ただし、高いカーディナリティであっても、データの偏りが大きい場合などにインデックスが使用されないというケースもあります。
インデックス対象のカラムを選ぶ際は、**カーディナリティが高く**、**値が偏りが少ない**カラムが良いです。


### インデックスのデメリット

インデックスは先ほど紹介したB-treeやB+treeのようなデータ構造をDBの内部で持つため、インデックスを貼りすぎるとDBを圧迫してしまうことやInsertやDeleteを行う際にDBのテーブルだけでなくインデックスの更新も行う必要があるため、InsertやDeleteのコストが上がってしまうという点に気をつけなければいけません。

## 参考文献
大いに参考になった記事です。ありがたや

https://zenn.dev/umi_mori/books/331c0c9ef9e5f0/viewer/992632

https://zenn.dev/m_yamashii/articles/mysql-index-cardinality

https://products.sint.co.jp/siob/blog/index

### まとめ
DBの種類やインデックスについてまとめました。

明日の[Yamato Advent Calendar 2023](https://qiita.com/advent-calendar/2023/yamato)は「データベース深堀りガイド②」です。DBのトランザクションについてやスケーラビリティのまとめをやろうと思います。お楽しみに！